基本概念

  • 前序遍历:先访问根节点,再访问左子节点,最后访问右子节点
  • 中序遍历:先访问左子节点,再访问跟节点,最后访问右子节点
  • 后序遍历:先访问左子节点,再访问右子节点,最好访问根节点

前序遍历

要想用非递归的方式解决问题,几乎都是采用栈的方式解决。前序遍历是先访问根节点,再访问左子节点,最后访问右子节点,对应图中顺序1->2->4->5->3->6->7.所以我们可以采用以下方式来做:

  • 假设cur=head,将cur入栈
  • 不断从栈中弹出栈顶节点,然后把右子节点和左子节点放入栈中(因为先访问左子节点,栈为先进后出的数据结构,所以先放左子节点)
  • 当栈不为空,不断重复上一步骤

代码如下

public void preOrderUnRecur(Node node){
        System.out.println("非递归前序遍历");
        if (node == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while (!stack.empty()){
            Node curNode = stack.pop();
            System.out.print(curNode.value+" ");
            if (curNode.right != null) stack.push(curNode.right);
            if (curNode.left != null) stack.push(curNode.left);
        }
        System.out.println();
    }

中序遍历

中序遍历的顺序是先左子节点,再当前节点,再右子节点,对应图中4->2->5->1->6->3->7.解题思路如下

  • 初始化cur=head
  • 将cur入栈,不断将cur=cur.left(不断取左子节点),重复当前过程
  • 如果发现cur为空,则说明已经访问到“最左“节点,出栈并打印当前节点的值,将其右子节点赋值给cur,重复上一步

代码如下:

public void inOrderUnRecur(Node node){
        if (node == null) return;
        Stack<Node> stack = new Stack<>();
        while (!stack.empty() || node != null){
            if (node != null){
                stack.push(node);
                node = node.left;
            }else {
                node = stack.pop();
                System.out.println(node.value);
                node = node.right;
            }
        }
    }

后序遍历

后序遍历的访问顺序为先左子节点,再右子节点,最后访问当前节点,对应于图中的4->5->2->6->7->3->1,后序遍历比较难,我这里提供一种双栈的解决思路。想一下怎么能做到先左再右最后中呢?要想做到这一点,根节点要在栈底,然后是右子节点,最后是左子节点。我们可以采用如下方式做到这一点

  • 申请两个栈s1,s2,将头节点压入s1
  • 从s1中弹出节点cur依次将cur的做孩子右孩子压入s1,同时将cur压入栈s2中
  • 最后s2的栈即为访问顺序,不断弹出打印即可

代码如下

public void posOrderUnRecur(Node node){
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();

        stack1.push(node);

        while (!stack1.empty()){
            node = stack1.pop();
            stack2.push(node);
            if (node.left != null){
                stack1.push(node.left);
            }
            if (node.right != null){
                stack1.push(node.right);
            }
        }
        while (!stack2.empty()){
            System.out.println(stack2.pop().value);
        }
    }