二叉树非递归遍历

2022-11-09

字数统计: 1.2k字 | 阅读时长: 5分

前言

不积跬步，无以至千里。

用Java写一下二叉树的非递归遍历，用print表示操作了，主要关注算法。

树定义如下：

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
        }
    }

先序遍历（直觉版）

思路：根左右，从根节点开始先走到最左下节点，然后依次出栈，如果出栈的节点有右子节点则对右子节点再走到最左下，直至栈空。

步骤：

对当前节点走到最左下，每次对当前节点操作+入栈。
元素出栈，若有右子节点则重复1，若无则重复2。
栈空结束。

public void preorderTraversal(TreeNode root){
        Stack<TreeNode> nodeStack = new Stack<>();
        if(root == null){
            System.out.println("Null root error!");
        }else {
            TreeNode temp = root;

            while (temp!=null){
                // 操作
                System.out.println(temp.val);
                nodeStack.add(temp);
                temp = temp.left;
            }

            while (!nodeStack.isEmpty()){
                temp = nodeStack.pop();
                if (temp.right!=null){
                    temp = temp.right;
                    while (temp!=null){
                        // 操作
                        System.out.println(temp.val);
                        nodeStack.add(temp);
                        temp = temp.left;
                    }
                }
            }
        }
    }

这个版本的基础上可以进行各种优化。

中序遍历（直觉版）

思路：左根右，从根节点走到最左下节点，然后依次出栈并操作，如果出栈的节点有右节点则对右节点再走到最左下，直至栈空。

步骤：

对当前节点走到最左下，每次对当前节点入栈。
元素出栈，操作当前节点，若有右子节点则重复1，若无则重复2。
栈空结束。

public void inorderTraversal(TreeNode root){
        Stack<TreeNode> nodeStack = new Stack<>();
        if(root == null){
            System.out.println("Null root error!");
        }else {
            TreeNode temp = root;
            while (temp!=null){
                nodeStack.add(temp);
                temp = temp.left;
            }

            temp = nodeStack.pop();
            while (temp!=null){
                // 操作
                System.out.println(temp.val);
                if(temp.right!=null){
                    temp = temp.right;
                    while (temp!=null){
                        nodeStack.add(temp);
                        temp = temp.left;
                    }
                }

                if (nodeStack.isEmpty()){
                    break;
                }

                temp = nodeStack.pop();
            }
        }
    }

这个版本的基础上可以进行各种优化。

后序遍历（直觉版）

思路：左右根，后序不能采用先序和中序的同款算法的主要原因是判断到当前节点存在右子树时，则不能对当前节点进行操作，而需要先对右子树做后序遍历，而即便是保留当前节点，并把右子树遍历完毕后，再对当前节点进行操作，仍然需要对当前节点的右子树是否已被遍历的状态进行判断，判断的依据是上一次操作的节点是否是右子节点。

步骤：

对当前节点走到最左下，每次对当前节点入栈。
元素出栈，判断当前节点，若无右子树则操作并标记当前节点，若有右子树则判断右子树是否被访问过，若未被访问则保留当前节点状态，并依次入栈右子树左支，标记右子节点；若已访问过则操作当前节点，并标记当前节点。重复2。
栈空结束。

public void postorderTraversal(TreeNode root){
        Stack<TreeNode> nodeStack = new Stack<>();
        if(root == null){
            System.out.println("Null root error!");
        }else {
            TreeNode temp = root;
            TreeNode mark = null;
            while (temp!=null){
                nodeStack.add(temp);
                temp = temp.left;
            }

            temp = nodeStack.pop();
            while (temp!=null){
                if(temp.right==null){
                    // 操作
                    System.out.println(temp.val);
                    // 标记当前节点
                    mark = temp;
                }else{
                    // 当前节点含右子树的情况，判断前次处理节点是否是右子节点。
                    if(temp.right==mark){
                        // 操作
                        System.out.println(temp.val);
                        // 标记当前节点
                        mark = temp;
                    }else {
                        // 保留状态
                        nodeStack.add(temp);
                        // 入栈右子树的左支，并标记右子节点。
                        temp = temp.right;
                        mark = temp;
                        while (temp!=null){
                            nodeStack.add(temp);
                            temp = temp.left;
                        }
                    }
                }

                if (nodeStack.isEmpty()){
                    break;
                }

                temp = nodeStack.pop();
            }
        }
    }

这个版本的基础上可以进行各种优化。

层序遍历

思路：按从上到下，从左到右的顺序遍历。用队列实现，先入当前节点，出队再入左、右两子节点，然后每出一个就入队该节点的左、右子节点，直到队空。

步骤：

入队当前节点。
出队一个节点，入队该节点的左、右子节点，重复2。
队空结束。

public void layerSequenceTraversal(TreeNode root){
        LinkedBlockingQueue<TreeNode> que =  new LinkedBlockingQueue<>();

        if(root == null){
            System.out.println("Null root error!");
        }else {
            que.offer(root);
            TreeNode temp = null;
            while (!que.isEmpty()){
                temp = que.poll();
                System.out.println(temp.val);

                if (temp.left!=null){
                    que.offer(temp.left);
                }

                if (temp.right!=null){
                    que.offer(temp.right);
                }
            }
        }
    }

后记

先把我个人认为符合直觉的遍历方法写一下，看起来比较复杂但是容易理解，后面再进行优化补充。

首发于 silencezheng.top。