java_非递归遍历二叉树

先序遍历，由于栈是后进先出(FIFO),所以我们先让s.right进入，再让s.left进入

public static void pre_order(node root){
Stack<node> s=new Stack<>();
s.push(root);
while(!s.isEmpty()){
node cur=s.pop();
System.out.println(cur.data);    //由于先序，所以头节点先打印
if(s.right!=null){
s.push(s.right);
}
if(s.left!=null){
s.push(s.left);
}
}
}

中序

思路：

有左，则优先压栈左，当前元素为null时，则弹出，立即处理弹出的数据，然后跳到该元素的右孩子

public static void in_order(node root){
Stack<node> stack=new Stack<>();
stack.push(root);
node cur=null;
while(!stack.isEmpty()||cur!=null){
if(cur!=null){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
}
else{
cur=stack.pop();
System.out.println(cur.data);
}
}
} 

后序 两种实现方法

/*需要两个栈，基于前面的pre_order 中 左 右 改造为 中 右 左 再倒序(具体实现是再次进栈)为 左 右 中*/
public static void last_order1(node h){
Stack<node> stack=new Stack<>(),collect=new Stack<>();
stack.push(h);
while(!stack.isEmpty()){
node cur=stack.pop();        //并不直接处理，而是存储起来，因为是要倒序一边的
collect.push(cur);
if(cur.left!=null){     //目的是 中 右 左，所以左先进
stack.push(cur.left);
}
if(cur.right!=null){
stack.push(cur.right);
}
}
while(!collect.isEmpty()){
System.out.println(collect.pop());
}
}

//只需要一个栈就可以的，比第一种好一些
public static void last_order2(node h){
Stack<node> stack=new Stack<>(); //这个方法比较绕的，h总指向上一次弹出的元素，除了第一次不是，h的目的是判断前节点的左右孩子是否遍历完
while(!stack.isEmpty()){
node cur=stack.peek();
if(cur.left!=h&&cur.right!=h&&cur!=null){ //说明连最基础的左孩子都没有处理
stack.push(cur.left);
}
else if(cur.right!=h&&cur!=null){           //说明左孩子处理了，但是右孩子还没有处理
stack.push(cur.right);
}
else{                   //说明stack最后一个元素的左右都处理完了
h=stack.pop();
System.out.println(h.data);
}
}
}

原文地址：https://blog.csdn.net/2303_78983004/article/details/143661268

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！