当前位置：首页 > article >正文

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

article 2024/12/4 10:37:05

前序遍历

我们先来看代码

 public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6))
        );

        LinkListStack<TreeNode> stack=new LinkListStack<>(100);

        TreeNode curr =root;//代表当前节点
        while (curr != null||!stack.isEmpty()) {
            if (curr!= null) {
                System.out.println("去："+curr.val);
                stack.push(curr);// 压入栈，为了记住来时的路
                curr = curr.left;
            }else {
                TreeNode pop=stack.pop();
       
                curr=pop.right;
            }
        }

按照逻辑是 值左右

先打印再压入栈，因为我们遍历完左边的时候，需要一步一步寻找遍历的路径找回去，为了记住来时路，我们需要通过栈来存储。

我们将遍历的值直接打印并存储在栈里

如图所示，我们先将1压入栈，然后陆续遍历2,4，接着我们当遍历到4之后发现left为null，我们再从栈中退出4去查找4的right，因为符合值左右，发现right没有，我们继续pop，发现2也没有right，直到pop到1有right然后进行右边的遍历，规则一样

中序遍历

思路和前序相像，先压入栈，当left为null的时候进入else循环开始打印

因为4的left=null已经算是处理好了，所以先打印4，然后4.right=null所以不做处理，再pop取出2，因为4已经完全处理好了，再去处理2的right，接着再回到1，处理1.right，访问到3不能直接打印，先压入栈再依次处理左节点即可

我们来看代码，其实就是打印的位置不一样

TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6))
        );

        LinkListStack<TreeNode> stack=new LinkListStack<>(100);

        TreeNode curr =root;//代表当前节点
        while (curr != null||!stack.isEmpty()) {
            if (curr!= null) {
                System.out.println("去："+curr.val);
                
                curr = curr.left;
            }else {
                TreeNode pop=stack.pop();
                System.out.println("回："+pop.val);
                curr=pop.right;
            }
        }
    }

后序遍历

        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6))
        );

        LinkListStack<TreeNode> stack=new LinkListStack<>(100);
        TreeNode curr =root;//代表当前节点
        TreeNode pop=null;
        while (curr != null||!stack.isEmpty()) {
            if (curr!= null) {
                System.out.println("去："+curr.val);
                stack.push(curr);// 压入栈，为了记住来时的路
                curr = curr.left;
            }else {
                TreeNode peek=stack.peek();
                if(peek.right==null||peek.right==pop) {
                    pop=stack.pop();
                    System.out.println("回："+pop.val);
                }else
                curr=peek.right;
            }
        }

我们更具代码，发现在遍历完左子树之后的处理的条件判断变多，并且将pop的元素设置成了全局变量

思路是先遍历左子树，因为打印的顺序是左右值，所以左子树处理完之后先peek判断右子树是否处理好，如果右子树是null或者是之前pop的值说明已经处理完毕，我们可以将值取出打印，如果没有处理完成我们就将curr设置为右子树进行处理

还是先遍历到4发现left=null，于是去处理右节点，发现right=null，然后从栈中打印，结束后发现curr=null，然后在peek取到2，发现右节点不为空于是将7进行处理，先压入栈此时7没有左子树于是直接进入处理并且pop掉，然后再peek到之前的二，发现它的右子树正好是之前pop的7，代表右子树已经处理完成，所以我们可以将2pop处理打印，接着取peek=1然后处理右子树