对于二叉树这种数据结构的Java实现，首先我们要了解二叉树的前序，中序以及后序的区别，所谓的前序、中序、后续，就是对根节点而言的，左右的遍历顺序不变，前序就是根节点最先遍历，然后左右；中序就是把根节点放在中间遍历；后序则是把根节点放在最后遍历。
中序遍历（非递归实现）：
二叉树的中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
代码实现：
import java.util.Stack;
public class Main
{
public static void main(String[] args)初始化生成一颗完全二叉树以数组形式
{
TreeNode[] node = new TreeNode[10];
for(int i = 0; i < 10; i++)
{
node[i] = new TreeNode(i);
}
for(int i = 0; i < 10; i++)
{
if(i*2+1 < 10)
node[i].left = node[i*2+1];
if(i*2+2 < 10)
node[i].right = node[i*2+2];
}
System.out.println();
midOrder(node[0]);
}
class TreeNode//初始化定义节点结构
{
int value;
TreeNode left;
TreeNode right;
TreeNode(int value)
{
this.value = value;
}
}
public static void midOrder(TreeNode biTree)//非递归实现遍历
{
Stack<TreeNode> stack = new Stack<TreeNode>();//new一个栈来存储
while(!stack.isEmpty() || biTree != null)//判断栈或节点是否为空
{
while(biTree != null)//当节点不为空时，入栈并向左子树判断
{
stack.push(biTree);
biTree = biTree.left;
}
if(!stack.isEmpty())//当栈不为空时，出栈且输出结果并且向右子树判断
{
biTree = stack.pop();
System.out.println(biTree.value);
biTree = biTree.right;
}
}
}
}
输出结果：
先序遍历（非递归实现）：
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问 根结点，然后遍历左子树，最后遍历右子树。
代码实现：
import java.util.Stack;
public class Main
{
public static void main(String[] args)
{
TreeNode[] node = new TreeNode[10];//初始化生成一棵完全二叉树以数组形式
for(int i = 0; i < 10; i++)
{
node[i] = new TreeNode(i);
}
for(int i = 0; i < 10; i++)
{
if(i*2+1 < 10)
node[i].left = node[i*2+1];
if(i*2+2 < 10)
node[i].right = node[i*2+2];
}
preOrder(node[0]);
}
static class TreeNode//初始化节点结构
{
int value;
TreeNode left;
TreeNode right;
TreeNode(int value)
{
this.value = value;
}
}
public static void preOrder(TreeNode biTree)
{
Stack<TreeNode> stack = new Stack<TreeNode>();//初始化创建栈
while(biTree != null || !stack.isEmpty())//判断节点不为空且栈也不为空时
{
while(biTree != null)//当节点不为空时输出节点的值并且入栈且向左子树移动
{
System.out.println(biTree.value);
stack.push(biTree);
biTree = biTree.left;
}
if(!stack.isEmpty())//当栈不为空时入栈且向右子树移动
{
biTree = stack.pop();
biTree = biTree.right;
}
}
}
}
输出结果：
后序遍历（非递归实现）：
后序遍历是最复杂的一种，后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后再遍历根结点。
代码实现：
import java.util.Stack;
public class Main
{
public static void main(String[] args)
{
TreeNode[] node = new TreeNode[10];//初始化生成一棵完全二叉树以数组形态
for(int i = 0; i < 10; i++)
{
node[i] = new TreeNode(i);
}
for(int i = 0; i < 10; i++)
{
if(i*2+1 < 10)
node[i].left = node[i*2+1];
if(i*2+2 < 10)
node[i].right = node[i*2+2];
}
postOrder(node[0]);
}
static class TreeNode//初始化节点结构
{
int value;
TreeNode left;
TreeNode right;
TreeNode(int value)
{
this.value = value;
}
}
public static void postOrder(TreeNode biTree)
{
int left = 1;//在辅助栈里表示左节点
int right = 2;//在辅助栈里表示右节点
Stack<TreeNode> stack = new Stack<TreeNode>();//初始化创建栈
Stack<Integer> stack2 = new Stack<Integer>();//辅助栈，用来判断子节点返回父节点时处于左节点还是右节点
while(biTree != null || !stack.empty())
{
while(biTree != null)
{
//将节点压入栈1，并在栈2将节点标记为左节点
stack.push(biTree);
stack2.push(left);
biTree = biTree.left;
}
while(!stack.empty() && stack2.peek() == right)
{
//如果是从右子节点返回父节点，则任务完成，将两个栈的栈顶弹出
stack2.pop();
System.out.println(stack.pop().value);
}
if(!stack.empty() && stack2.peek() == left)
{
//如果是从左子节点返回父节点，则将标记改为右子节点
stack2.pop();
stack2.push(right);
biTree = stack.peek().right;
}
}
}
}
输出结果：
