二叉树的非递归遍历（非递归先序遍历，中序遍历，后序遍历）

约定不等于承诺〃 2023-02-26 02:28 48阅读 0赞

### 主要利用栈的后进先出的特性 ###

public class TraversalNonRecursive { 
    
        /** * 先压头节点并弹出，然后先压右，后压左。这样弹出的顺序就是先左后右 * @param head */
        public static void preOrder(TreeNode head){ 
            System.out.println("preOrder");
            if(head!=null){ 
                Stack<TreeNode> stack = new Stack<>();
                stack.push(head);
                while (!stack.isEmpty()){ 
                    head=stack.pop();
                    System.out.print(head.val+" ");
                    if(head.right!=null){ 
                        stack.push(head.right);
                    }
                    if(head.left!=null){ 
                        stack.push(head.left);
                    }
                }
            }
        }
    
        /** * 将二叉树左边界依次入栈，直到为空，弹出，并使head等于右节点，此时如果head不为空，则压栈，为空则弹出。弹出的顺序刚好是中序遍历 * @param head */
        public static void inOrder(TreeNode head){ 
            System.out.println("inOrder");
            if(head!=null){ 
                Stack<TreeNode> stack = new Stack<>();
                while (!stack.isEmpty()||head!=null){ 
                    if(head!=null){ 
                        stack.push(head);
                        head=head.left;
                    }else { 
                        head=stack.pop();
                        System.out.print(head.val+" ");
                        head=head.right;
                    }
                }
            }
        }
    
        /** * 1.后序遍历顺序是左右中，而中右左的遍历很容易构造，跟先序遍历差不多，只是左右节点压栈顺序调换 * 2.将中右左遍历压入一个辅助栈，再弹出，也就是后序的左右中遍历 * @param head */
        public static void posOrder(TreeNode head){ 
            System.out.println("posOrder");
            if(head!=null){ 
                Stack<TreeNode> stack = new Stack<>();
                Stack<TreeNode> stackHelp = new Stack<>();
    
                stack.push(head);
                while (!stack.isEmpty()){ 
                    head=stack.pop();
                    stackHelp.push(head);
                    if(head.left!=null){ 
                        stack.push(head.left);
                    }
                    if(head.right!=null){ 
                        stack.push(head.right);
                    }
                }
    
                while (!stackHelp.isEmpty()){ 
                    System.out.print(stackHelp.pop().val+" ");
                }
            }
        }
    
        
        public static void main(String[] args) { 
            TreeNode treeNode1=new TreeNode(1);
            TreeNode treeNode2=new TreeNode(2);
            TreeNode treeNode3=new TreeNode(3);
            TreeNode treeNode4=new TreeNode(4);
            TreeNode treeNode5=new TreeNode(5);
            TreeNode treeNode6=new TreeNode(6);
            TreeNode treeNode7=new TreeNode(7);
    
            treeNode1.left=treeNode2;
            treeNode1.right=treeNode3;
            treeNode1.left.left=treeNode4;
            treeNode1.left.right=treeNode5;
            treeNode1.right.left=treeNode6;
            treeNode1.right.right=treeNode7;
    
            preOrder(treeNode1);
            System.out.println("\n");
            inOrder(treeNode1);
            System.out.println("\n");
            posOrder(treeNode1);
    
        }
    }

示例二叉树

![format_png][]

打印结果

![format_png 1][]

[format_png]: /images/20230209/6e4395dcd08043e8924e2955f58d9614.png
[format_png 1]: /images/20230209/3586de86b09640e2a3d67c5c33ee33d5.png