思维导图:
要实现二叉树的非递归遍历,就必须要借助栈的结构特点来实现;
我们根据遍历的顺序,然后对入栈的结点进行分析遍历即可;
就以这个二叉树为例吧!
1,先序遍历;
对于任一结点P: 1,将结点P入栈,并访问结点P; 2,判断结点P的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点P,循环执行;若不为空,则将P的左孩子置为当前的结点P; 3,直到P为null并且栈为空,则遍历结束。
//二叉树先序遍历(非递归)
public void XBTNotRecursion(BinaryTreeNode root){
BinaryTreeNode temp = root;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
while (temp != null || !stack.isEmpty()) {
//遇到一个结点,就把它入栈并访问它,然后去遍历它的左子树;
while (temp != null) {
stack.push(temp);
//输出当前结点
System.out.print(temp.ch + " ");
temp = temp.lchild;
}
if(!stack.isEmpty()) {
//当左子树遍历结束后,从栈顶弹出这个结点;
temp = stack.pop();
//然后按其右指针再去先序遍历该结点的右子树
temp = temp.rchild;
}
}
}
2,中序遍历;
对于任一结点P: 1,若其左孩子不为空,则将P入栈并将P的左孩子置为当前的P,然后对当前结点P再进行相同的处理; 2,若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的P置为栈顶结点的右孩子; 3,直到P为null并且栈为空则遍历结束;
//二叉树中序遍历(非递归)
public void ZBTNotRecursion(BinaryTreeNode root){
BinaryTreeNode temp = root;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
while (temp != null || !stack.isEmpty()) {
//遇到一个结点,就把它入栈并访问它,然后去遍历它的左子树;
while (temp != null) {
stack.push(temp);
temp = temp.lchild;
}
if(!stack.isEmpty()) {
//当左子树遍历结束后,从栈顶弹出这个结点;
temp = stack.pop();
//输出当前结点
System.out.print(temp.ch + " ");
//然后按其右指针再去中序遍历该结点的右子树
temp = temp.rchild;
}
}
}
3,后序遍历;
后序遍历的非递归算法是三种顺序中最复杂的,原因在于: 1,后序遍历是先访问左、右子树,再访问根节点,而在非递归算法中,利用栈回退到时,并不知道是从左子树回退到根节点,还是从右子树回退到根节点,; 2,如果从左子树回退到根节点,此时就应该去访问右子树,而如果从右子树回退到根节点,此时就应该访问根节点,; 3,所以相比先序和中序,必须得在压栈时添加信息,以便在退栈时可以知道是从左子树返回,还是从右子树返回进而决定下一步的操作。
这里采取的做法为:
引入一个pre指针,标记访问当前节点的之前访问的节点; 如果root.right为pre,或者root.right为null,则可以判断已经从右子树访问返回。
//二叉树后序遍历(非递归)
public void HBTNotRecursion(BinaryTreeNode root){
BinaryTreeNode temp = root;
//标记访问序列中前一个二叉树节点(当前节点的之前访问的节点)
BinaryTreeNode pre = null;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
while (temp != null || !stack.isEmpty()) {
//遇到一个结点,就把它入栈并访问它,然后去遍历它的左子树;
while (temp != null) {
stack.push(temp);
temp = temp.lchild;
}
if(!stack.isEmpty()) {
//先查看栈顶结点
temp = stack.peek();
//如果一个结点右孩子是空,或者右孩子刚被访问过,那么就访问该节点。否则就往右孩子走。
if(temp.rchild == null || temp.rchild == pre) {
//输出当前结点
System.out.print(temp.ch + " ");
//出栈
stack.pop();
pre = temp;
temp = null;
}else {
temp = temp.rchild;
}
}
}
}
测试函数:
public static void main(String[] args) {
BTNotRecursionDao btNotRecursionDao=new BTNotRecursionDao();
//创建树结点
BinaryTreeNode node1=new BinaryTreeNode('A',null,null);
BinaryTreeNode node2=new BinaryTreeNode('B',null,null);
BinaryTreeNode node3=new BinaryTreeNode('C',null,null);
BinaryTreeNode node4=new BinaryTreeNode('D',null,null);
BinaryTreeNode node5=new BinaryTreeNode('E',null,null);
BinaryTreeNode node6=new BinaryTreeNode('F',null,null);
BinaryTreeNode node7=new BinaryTreeNode('G',null,null);
BinaryTreeNode node8=new BinaryTreeNode('H',null,null);
//建立结点间的关系
node1.lchild=node2; /* node1就是A,结点A的左孩子是B(node2),右孩子是F(node6) */
node1.rchild=node6;
node2.rchild=node3; /* node2就是B,结点B的左孩子为null(初始化就是null,所以不用管),右孩子是C(node3) */
node3.lchild=node4;
node3.rchild=node5;
node6.rchild=node7;
node7.lchild=node8;
//非递归遍历
System.out.println("先序遍历结果:");
btNotRecursionDao.XBTNotRecursion(node1); /* 根结点为A */
System.out.println();
System.out.println("中序遍历结果:");
btNotRecursionDao.ZBTNotRecursion(node1);
System.out.println();
System.out.println("后序遍历结果:");
btNotRecursionDao.HBTNotRecursion(node1);
}
测试结果:
后序遍历的实现思路还是有些复杂,请读者们好好捋一捋。。