首页 计算机学科 java 数据结构与算法 二叉树

# 二叉树 - 深度优先遍历

对于 二叉树 而言它的 深度优先遍历 而 又可以分成 三种 分别是:

  1. pre-order: 前序遍历
  2. in-order: 中序遍历
  3. post-order: 后序遍历

而这三种遍历方式 它们 又有 各自的规则，除了各自规则以外 它们有一个共同特点，就是要 遍历的过程中 深入到 叶子节点

也就是深入到 离 跟节点 更远的 叶子节点

# 下面演示 每一种遍历 是怎样工作的:

下面是一个使用数组来表示的二叉树

image-20240125205457243

树中的每一个节点 有两种颜色 一种就是 灰色的 表示这个节点在遍历的时候还没有访问过，还有一种是 绿色的 表示这个节点是被访问过了

# 我们先看遍历规则:

# 前序遍历规则:

  1. 先访问该节点
  2. 然后是左子树
  3. 最后是右子树

我们先从根节点开始，先访问根节点的值

image-20240125210317581

访问了根节点后，然后是 左子树 访问 2 节点

image-20240125210419966

下面再访问 2 的 左子树，也就是 4

image-20240125210441701

4 没有 左右子树 说明 4 已经走完了，4 走完了 相当于 2 的左子树完成了 而 2 的右子树 是 null 所以 也算是完成了 至此 2 和 4 它俩作为 1 的左子树就 遍历完成了

image-20240125210653199

跟节点的 左子树 完成了，就轮到 根节点的 右子树了

先访问 根节点的 右子树 打印 3

image-20240125210741366

3 访问完成就 访问 3 的左子树 5 , 5 由于没有左右子树 所以就算访问完成了

image-20240125210818485

然后再 访问 3 的右子树 6 的左右子树也没有 也算访问完成了

image-20240125210900629

最后 根节点的 左右子树 都完成了 那么 1 也算是完整的结束了

image-20240125210942582

所以整个 前序遍历打印出来的值为: 1,2,4,3,5,6

# 中序遍历:

  1. 先访问左子树
  2. 然后是该节点
  3. 最后是右子树

从根节点开始，第一个拿到的就是根节点 但是不能打印根节点的值，因为规则是 先得访问完根节点的 左子树 然后才能打印 根节点的值 也就是 2

image-20240126153317899

但是到了 2 也不能着急打印 2 的值，得先 访问 当前节点的左子树 也就是 4, 而 4 也不能直接打印类似的我们需要访问 4 的左子树 然而 4 没有左子树 那么 就打印 4 这个左子树就算完成了 接着访问 4 的右子树 但是 4 没有右子树 所以 4 就算访问完了

image-20240126153602094

4 完成了 那么就 意味着 上一个节点 2 它的左子树遍历完成了，左子树 遍历完成了 就是 第二步了 可以打印 当前的 2 的值了

2 没有 右子树 所以 2 整个 也算是完成了

image-20240126192423383

2 跟 4 作为 1 的左子树 完成了

image-20240126192444669

1 的左子树完成了 就可以打印 1 节点的值了

image-20240126192512137

接下来访问 1 的右子树，它不会直接打印 3 因为 它先进入 3 (右子树) 而 3 还有 左右子树 并没有结束 因此它需要先找到 3 的左子树

image-20240126192629421

5 没有左右子树 就算是遍历完成了，打印 5 的值

image-20240126192701205

5 完成了 回到 3 打印 3

image-20240126192724301

接下来访问 3 的右子树，同样的 先看 6 有没有左子树 没有就打印 6 然后再看 6 的右子树 也没有 直接结束

image-20240126192740086

最终结果就是: 4, 2, 1, 5, 3, 6

# 后序遍历:

  1. 先访问左子树
  2. 然后是右子树
  3. 最后是该节点

首先它不能直接打印 根节点 所以先看 根节点的左子树 再看 当前节点是否有左右子树 如何有 就先访问 左子树 直到深部

如下图就是：根节点 1 它有左子树 2 而 2 又有左子树 4 所以访问左子树直到节点 4 的位置 为止 4 没有左子树就看右子树 也没有右子树那么直接打印 4 的值

image-20240126193244860

4 打印完成了 它作为 2 的左子树就完成了 回到 节点 2 看 2 的右子树 却没有 右子树 那么就打印 2 的值

image-20240126193338410

2 和 4 完成了 就相当于 1 的左子树完成了

image-20240126193359413

接着访问 1 的右子树 进入 3 而 3 有左右子树 所以 进入 左子树 5 而 5 没有左右子树那么就 打印 5 的值，3 的左子树就算完成了

image-20240126193529967

5 打印了 看 3 的右子树 6 而 6 没有左右子树 那么直接打印 6 的值，那么 3 的右子树也算完成了

image-20240126193610941

3 的左右字数完成了 就可以 打印 3 的值了

image-20240126193902502

3 , 5 , 6 它们是 1 的右子树，那么 1 的左右子树 都打印完成 就该 打印 1 的值了

image-20240126193946876

最终结果: 4, 2, 5, 6, 3, 1

# 代码实现 - 递归实现：前序遍历，中序遍历，后序遍历

我们要遍历的 二叉树 如下图所示

image-20240126233751871

@SuppressWarnings("all")
public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 创建一个二叉树
        BinaryTree binaryTree = new BinaryTree();
        // 创建节点
        HeroNode root = new HeroNode(1);
        HeroNode node = new HeroNode(2);
        HeroNode node1 = new HeroNode(3);
        HeroNode node2 = new HeroNode(6);
        HeroNode node3 = new HeroNode(5);
        HeroNode node4 = new HeroNode(4);
        // 手动创建二叉树 (后面使用递归方式创建二叉树)
        root.setLeft(node);
        root.setRight(node1);
        node.setLeft(node4);
        node1.setRight(node2);
        node1.setLeft(node3);
        binaryTree.setRoot(root);
        // 测试
        System.out.println("===前序遍历===");// 1 2 4 3 5 6
        binaryTree.preOrder();
        System.out.println("===中序遍历===");// 4 2 1 5 3 6
        binaryTree.infixOrder();
        System.out.println("===后序遍历===");// 4 2 5 6 3 1
        binaryTree.postOrder();
    }
}
@SuppressWarnings("all")
// 定义 BinaryTree 二叉树
class BinaryTree {
    private HeroNode root;
    public void setRoot(HeroNode root) {
        this.root = root;
    }
    // 前序遍历，遍历是从根节点 (root) 开始的
    public void preOrder(){
        if(this.root != null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空");
        }
    }
    // 中序遍历
    public void infixOrder(){
        if(this.root != null){
            this.root.infixOrder();
        }else{
            System.out.println("二叉树为空");
        }
    }
    // 后序遍历
    public void postOrder(){
        if(this.root != null){
            this.root.postOrder();
        }else{
            System.out.println("二叉树为空");
        }
    }
}
@SuppressWarnings("all")
// 创建 HeroNode 节点
class HeroNode {
    private int no;
    private HeroNode left;
    private HeroNode right;
    public HeroNode(int no) {
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public HeroNode getLeft() {
        return left;
    }
    public void setLeft(HeroNode left) {
        this.left = left;
    }
    public HeroNode getRight() {
        return right;
    }
    public void setRight(HeroNode right) {
        this.right = right;
    }
    @Override
    public String toString() {
        return no + "";
    }
    // 前序遍历方法
    public void preOrder(){
        // 先输出父节点
        System.out.println(this);
        // 递归向左子树前序遍历
        if(this.left != null){
            this.left.preOrder();
        }
        // 递归向右子树前序遍历
        if(this.right != null){
            this.right.preOrder();
        }
    }
    // 中序遍历方法
    public void infixOrder(){
        // 递归向左子树中序遍历
        if(this.left != null){
            this.left.infixOrder();
        }
        // 输出父节点
        System.out.println(this);
        // 递归向右子树中序遍历
        if(this.right != null){
            this.right.infixOrder();
        }
    }
    // 后序遍历方法
    public void postOrder(){
        // 递归向左子树后序遍历
        if(this.left != null){
            this.left.postOrder();
        }
        // 递归向右子树后序遍历
        if(this.right != null){
            this.right.postOrder();
        }
        // 输出父节点
        System.out.println(this);
    }
}
打印结果:
===前序遍历===
1
2
4
3
5
6
===中序遍历===
4
2
1
5
3
6
===后序遍历===
4
2
5
6
3
1

# 非递归实现：前序遍历，中序遍历
三种遍历的共同规律:
image-20240127001714441
前序遍历打印的值是：1，2，4，3，5，6
中序遍历打印的值是：4，2，1，5，3，6
后序遍历打印的值是：4，2，5，6，3，1
它们好像也没啥规律啊，打印的值也不一样
虽然它们打印值的顺序是有先有后，但是它们走的路径是一样的。这三种遍历方式在树中走的路径是一样的，它们都需要从根节点出发，先走左边。左边发现没有了 该回头走了 2 发现没有右子树 所以又从 2 回到 1
image-20240127002213528
这是左边子树走完了，那么接下来走右边从 1 到 3 然后 3 到 5 ，5 发现没路了，那么从 5 回到 3 再看右边有没有 结果 右边有就从 3 到 6 ，6 发现没路了 就 回到 3 最后从 3 回到 1
image-20240127002357606
这就走完了 一圈了
根据上图分析得出 它们打印的值 不一样 但是 它们走的路径却是 一样的，我们就从这点出发来看 非递归的实现方式
我们先编写让 遍历 沿着左边路径 走
HeroNode cur = root; // 代表当前节点
while(cur != null) {
   System.out.println(cur.getNo());
   // 把当前节点 更新成 当前节点的左孩子
   cur = cur.getLeft();
}
打印结果：
1
2
4

现在它可以沿着 左边路径 走了 但是问题 来了我们怎么让 它 把这颗二叉树 走全呢？
这里有一个很关键的步骤就是我得沿着 4 向回走了，因为我们来的时候 1，2，4 向回走 才能找到 它右边后续的节点
向回走就引出一个新的问题了，就是我们需要让它记住来时的路
比如说我们已经走到 4 了，我们向回走就需要知道 2，但是 4 并没有一个属性来记录它的父节点是谁因此它找不到父节点 2，也就是找不到来时的路，那怎么办呢？但是我们可以考虑使用一种数据结构来记录 每个节点来时的路
什么数据结构比较合适呢？答案是 使用 栈 比较合适
我们 走的时候 经过一个节点 就把 这个节点记录到 栈里，比如说 先经过的是 1 那就在循环结束前把 1 存入到栈里
image-20240127004429521
然后继续向左走，走到 2 了 那么就把 2 也放到 栈里
image-20240127004520894
然后走到 4 了最后把 4 也记录到 栈里
image-20240127004559737
4 左边的路不通了 没有左孩子了，说明走到头了 该向回走了，那么 来的时候 1，2，4 这个顺序 回的时候我就从 栈 弹出 4，2，1 的每个元素就可以了，这样就通过栈就记录了它来时的路
LinkedList<HeroNode> stack = new LinkedList<>();
HeroNode cur = root; // 代表当前节点
// 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
while(cur != null || ! stack.isEmpty()) {
   // 判断 去的路是否还有
   if(cur != null) {
      System.out.println("经过的路：" + cur.getNo());
      stack.push(cur); // 压入栈 ， 为了记住回来的路
      cur = cur.getLeft();
      // 打印 回去的路
   }else {
      HeroNode pop = stack.pop();
      System.out.println("回来的路：" + pop);
   }
}
打印结果：
经过的路：1
经过的路：2
经过的路：4
回来的路：4
回来的路：2
回来的路：1

这样我们就解决了 左边半个路 的问题了 那右边半个呢？
我们只需要将 回去的路的 右边节点赋值给当前的 cur 此时 cur 就不等于 null 了就会继续执行 右边的操作了
LinkedList<HeroNode> stack = new LinkedList<>();
HeroNode cur = root; // 代表当前节点
// 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
while(cur != null || ! stack.isEmpty()) {
   // 判断 去的路是否还有
   if(cur != null) {
      System.out.println("经过的路：" + cur.getNo());
      stack.push(cur); // 压入栈 ， 为了记住回来的路
      cur = cur.getLeft();
      // 打印 回去的路
   }else {
      HeroNode pop = stack.pop();
      System.out.println("回来的路：" + pop);
      cur = pop.getRight();
   }
}
打印结果：
经过的路：1
经过的路：2
经过的路：4
回来的路：4
回来的路：2
回来的路：1
经过的路：3
经过的路：5
回来的路：5
回来的路：3
经过的路：6
回来的路：6

上面的代码就可以完成绕树一圈，而上面的代码同样可以解决两个问题别分是 前序遍历 和 中序遍历
将代码稍作修改 你就会发现这就是 前序遍历 的值
LinkedList<HeroNode> stack = new LinkedList<>();
HeroNode cur = root; // 代表当前节点
// 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
while(cur != null || ! stack.isEmpty()) {
   // 判断 去的路是否还有
   if(cur != null) {
      System.out.println("经过的路：" + cur.getNo());
      stack.push(cur); // 压入栈 ， 为了记住回来的路
      cur = cur.getLeft();
      // 打印 回去的路
   }else {
      HeroNode pop = stack.pop();
      // System.out.println ("回来的路：" + pop);
      cur = pop.getRight();
   }
}
打印结果：
经过的路：1
经过的路：2
经过的路：4
经过的路：3
经过的路：5
经过的路：6

再稍作修改打印的就是中序遍历了
LinkedList<HeroNode> stack = new LinkedList<>();
HeroNode cur = root; // 代表当前节点
// 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
while(cur != null || ! stack.isEmpty()) {
   // 判断 去的路是否还有
   if(cur != null) {
      // System.out.println ("经过的路：" + cur.getNo ());
      stack.push(cur); // 压入栈 ， 为了记住回来的路
      cur = cur.getLeft();
      // 打印 回去的路
   }else {
      HeroNode pop = stack.pop();
      System.out.println("回来的路：" + pop);
      cur = pop.getRight();
   }
}
打印结果：
回来的路：4
回来的路：2
回来的路：1
回来的路：5
回来的路：3
回来的路：6

所以上面的代码既可以处理前序遍历 又 可以处理中序遍历
# 图解非递归前序遍历
下面通过图解的方式来理解上述的非递归实现 深度优先遍历 的代码：
image-20240127084704473
图中 橙色背景 的 节点 代表着 cur 节点，前序遍历 是 该值，左值，右值 的打印顺序 所以当前的 cur 也就是 root 节点可以先打印，打印完了就 压入栈中
PS：上面是二叉树，下面是 栈 用于存储来时的路
image-20240127084853485
上述操作 代表了 <--- 所指向的代码
LinkedList<HeroNode> stack = new LinkedList<>();
HeroNode cur = root; // 代表当前节点
// 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
while(cur != null || ! stack.isEmpty()) {
   // 判断 去的路是否还有
   if(cur != null) {
      System.out.println("经过的路：" + cur.getNo());//   <---
      stack.push(cur); // 压入栈 ， 为了记住回来的路       <---
      cur = cur.getLeft();
      // 打印 回去的路
   }else {
      HeroNode pop = stack.pop();
      System.out.println("回来的路：" + pop);
      cur = pop.getRight();
   }
}
image-20240127085115429
按照 值，左，右的顺序接下来我们就要处理它的左孩子，找到当前节点的左孩子 将来 把左孩子 作为下一轮的 循环节点 也就是 2
上述操作 代表了 <--- 所指向的代码
LinkedList<HeroNode> stack = new LinkedList<>();
HeroNode cur = root; // 代表当前节点
// 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
while(cur != null || ! stack.isEmpty()) {
   // 判断 去的路是否还有
   if(cur != null) {
      System.out.println("经过的路：" + cur.getNo());
      stack.push(cur); // 压入栈 ， 为了记住回来的路
      cur = cur.getLeft();//         <---
      // 打印 回去的路
   }else {
      HeroNode pop = stack.pop();
      System.out.println("回来的路：" + pop);
      cur = pop.getRight();
   }
}
接着打印 2 当前的值并压入栈中
image-20240127085341229
然后接着处理 左孩子
image-20240127085421291
同样的 打印它的值并压入栈中
image-20240127085456653
再处理 4 的左孩子时发现 左孩子是 null 了，也就是这条路走到头了 此时代码中 if 条件已经不成立了 就会进入 else 中 意味着该往回走了
image-20240127085632013
此时它就需要 弹栈 处理右孩子了，接下来 就将 4 弹出 往回走
image-20240127085741090
弹出之后检查它有没有 右孩子，如果是 null 的话 那么就继续向上走 继续走来时的路
上述操作 代表了 <--- 所指向的代码
LinkedList<HeroNode> stack = new LinkedList<>();
HeroNode cur = root; // 代表当前节点
// 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
while(cur != null || ! stack.isEmpty()) {
   // 判断 去的路是否还有
   if(cur != null) {
      System.out.println("经过的路：" + cur.getNo());
      stack.push(cur); // 压入栈 ， 为了记住回来的路
      cur = cur.getLeft();
      // 打印 回去的路
   }else {//         <--- 左孩子 访问到头了就执行 else 操作
      HeroNode pop = stack.pop();//     <---  弹出来时的路，也就是来时的上个节点 (往回走)
      System.out.println("回来的路：" + pop);
      cur = pop.getRight();//      <---  获取当前节点的 右孩子如果没有就是 null
   }
}
如果 4 没有右孩子那么就 继续弹栈把 2 给弹出栈
image-20240127090337979
然后看下 2 有没有 右孩子，而 2 也没有 右孩子 那就打印值 之后继续 向回走，把 1 弹出栈，此时栈中没有来时的路了
image-20240127090424356
1 弹出之后 1 有右孩子，下面把 1 的右孩子 赋值给了 cur ，cur 再次进入循环，准备处理 3 ，先打印 3 的值并且把 3 入栈
image-20240127090600563
LinkedList<HeroNode> stack = new LinkedList<>();
HeroNode cur = root; // 代表当前节点
// 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
while(cur != null || ! stack.isEmpty()) { // 下次循环 cur 就是 3 它不是 null 了而 栈是 空的 满足了一个条件继续操作
   // 判断 去的路是否还有
   if(cur != null) { //cur 不为 null 而是 3
      System.out.println("经过的路：" + cur.getNo());// 打印 3 的值
      stack.push(cur); // 压入栈 ， 为了记住回来的路
      cur = cur.getLeft();
      // 打印 回去的路
   }else {//         <--- 左孩子 访问到头了就执行 else 操作
      HeroNode pop = stack.pop();//     <---  1
      System.out.println("回来的路：" + pop);
      cur = pop.getRight();//      <---  pop.getRight () = 3 ===>  1 <= 赋值 = 3
   }
}
值，左，右的顺序处理 左孩子
image-20240127090826908
同样打印 5 的值 并且 入栈，然后处理 左孩子 但是 5 没有左孩子
没有左孩子那么 cur 就是 null 了，就可以操作 else 往回走了，把 5 弹出栈 再看 5 有没有 右孩子
image-20240127091046740
结果 5 也没有右孩子 可处理 那就继续 往回走 弹出 3 再看 3 是否有 右孩子 可处理
image-20240127091133714
3 有右孩子，那么就将 3 的右孩子 作为 cur 继续下一轮的循环操作，下轮循环 将 6 打印 并 入栈
image-20240127091245472
同样的 6 接着 处理 左孩子 没有 左孩子那么 cur 为 null 执行 else 弹出 6 并 打印 6 然后看有没有右孩子 结果没有 右孩子那么 cur 为 null 栈也为空 循环停止 程序结束！
image-20240127091438611
上面就是整个，前序遍历的 执行流程
# 图解非递归中序遍历
中序遍历打印值的操作 跟 前序遍历不同 我们先看下 中序遍历打印值的 规则：
  1. 左孩子
  2. 值
  3. 右孩子
从上面规则可以看出我们 在进入 while 循环 进入 if 判断时我们不能直接就打印 当前值 而是 需要先打印 左孩子的值
因此 打印值的 操作 我们需要 放到 回来的时候再打印，因为回来的时候意味着它的左子树 都完成了
刚开始让它按照我们规划的路线沿着左边走到头
image-20240127113608322
走到头之后 cur 就等于 null 了，之后进入到 else 往回走，弹出 4 并打印
image-20240127113714829
4 没有右孩子 算是完成了，接着弹出 2 并 打印 2
image-20240127113754415
2 也没有 右孩子 那么就 弹出 1 打印 1
image-20240127113836904
处理 1 的右孩子，1 的右孩子是 3 同样不能立刻打印 先沿着左边路走到头，没有左孩子了 回来的时候再打印
image-20240127114001864
走到 5 没有左子树了 回来的时候 弹出 5 并 打印 5 的值
image-20240127114044174
5 也没有 右孩子 接着弹出 3 打印 3 的值 并 找 3 的右孩子
image-20240127114144345
3 有右孩子 是 6 那么 打印 6 的值 并 入栈，然后 看 6 有没有 左孩子 没有就走 else 弹出 6 并打印然后看 6 有没有 右孩子 没有就 结束循环了
image-20240127114329817
# 非递归实现：后序遍历
后序遍历的 while 循环里面的 if 判断是和 前序 和 中序 是一样的 不用改，只有在 else 回来的时候需要改一下
为了把 这个问题解释清楚 先用 中序遍历 举个例子
下面二叉树 给 2 的右孩子 多加了一个 节点 7
image-20240127114604689
我们主要看一下回来的时候的一些注意事项，去的就不用说了，反正沿着左边的路走到头
走到头并且到经到过的节点 入栈中 就可以了
image-20240127114713129
那我们看 它回去的时候会做什么
每次回去的时候 都会把 栈中的 节点 要弹出
比如说 4 这个节点 进行弹出 并打印 4 的值
image-20240127114922771
接下来从 4 回到 2 ，2 也被弹出
那 2 还有 右孩子啊 ，将来 从 7 回来的时候 难道 用不着这个 2 了吗？
注意：上面的前序和中序 这两种情况确实用不着 2 了
image-20240127115032673
为什么呢？原因如下：
我们分析一下 中序遍历的 情况 是怎么样的
中序遍历：左，值，右
所以它把 2 打印完了 接下来就 遍历 右节点 也就是 7 既然 2 已经打印完了 那么 它 回来的时候 就不会再 经过 2 了
image-20240127144217040
上图中 7 处理完成后 回来时就直接到 1 节点了
上面 分析的中序情况就是 前序 ，中序 和 后序 不一样的地方。
比如还是刚才这个情况
image-20240127144511300
比如说 我要向回走了 从 4 走到 2，如果我将 2 从 栈中弹出来 那就不对了，因为后序遍历 它的规则是 左，右，值。
它需要把 2 的左子树和 右子树 处理完了 才能 打印 2 的值，如果把 2 弹出了 将来 7 回来的时候就找不到 2 的值了，这是后序遍历跟前面的 遍历不一样的地方
所以我们需要在弹栈的时候多加一些条件，不是在所有的情况下都需要在回来时立马弹栈。
我们可能需要让这个 2 节点在栈里面多留一会儿，等它的右子树处理完了我们才能弹栈，这是后序 跟 前两者的区别
代码实现如下：
LinkedList<HeroNode> stack = new LinkedList<>();
HeroNode cur = root; // 代表当前节点
// 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
while(cur != null || ! stack.isEmpty()) {
   // 判断 去的路是否还有
   if(cur != null) {
      // System.out.println ("经过的路：" + cur.getNo ());
      stack.push(cur); // 压入栈 ， 为了记住回来的路
      cur = cur.getLeft();
      // 打印 回去的路
   }else {
      HeroNode peek = stack.peek();// 判断右子树是否完成了，因为走到 else 左子树肯定是完成了不然不会走到 else　里
      if(peek.getRight() == null) {// 当 当前节点的右子树为 null 时，表示右子树处理完成了
         HeroNode pop = stack.pop();
         System.out.println("回来的路：" + pop);
      }else {// 如果当右子树不为 null 的时候，我们应该进入 右子树进行下一轮的处理
         cur = peek.getRight();
      }
   }
}
当进入到 else 时肯定是 左子树已经 处理完了 没有右子树了，当进入 else 时 获取 栈顶元素 判断它有没有 右子树，如果没有那就弹出 栈顶元素并 打印 继续下一论循环，如果有右子树那么就 进入到右子树进行下一轮的循环
但是光是上面这么写只是满足了一个条件而已如果你直接 Run 就会发现死循环了如下图所示：
recording
但是还有一个条件，不光是这一个条件，我们看如下的 二叉树进行分析：
image-20240127150018953
上面代码是 符合 栈顶 元素 它的 右子树 是否为 null ，如果为 null 就等于没有右子树 也就意味着 右子树算是处理完了
那符合这种情况的都有哪些节点呢？
根据上图中：4，7，5，6 都是符合的，但是呢 还有几个节点比如说 1，2，3。比如说 将来 我的 栈顶 是 2 了
image-20240127150355001
2 有右孩子 它的 right 不为 null ，这个时候我们怎么判断它的右子树是否处理完成了呢？
这里需要用到一个技巧：
首先我去记录一下 最近 一次 弹栈 的元素，比如说 4 已经处理完了 弹栈了，那我就用一个变量将它记录起来
记录下来后我们用在 比如说 4 往 2 走，从 4 回来 说明 2 的右孩子 还没处理呢，这时 2 应该保留在 栈里不要弹栈
如果是上次弹栈是 7 从 7 往回走这时就需要弹栈了，因为 7 是 2 的右孩子 都从 7 开始往回走了就说明右孩子处理完了，这时 2 这个节点是可以弹栈的
那我们就可以 用一个临时变量记录 上次 弹栈的 元素，记录下来 我每次去判断栈顶元素的 右孩子看看它是不是跟上一次 记录下来的临时变量 是相等的，如果它俩相等就说明 右子树处理完了
# 最终实现代码如下：
@SuppressWarnings("all")
public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 创建一个二叉树
        BinaryTree binaryTree = new BinaryTree();
        // 创建节点
        HeroNode root = new HeroNode(1);
        HeroNode node = new HeroNode(2);
        HeroNode node1 = new HeroNode(3);
        HeroNode node2 = new HeroNode(6);
        HeroNode node3 = new HeroNode(5);
        HeroNode node4 = new HeroNode(4);
        HeroNode node5 = new HeroNode(7);
        // 手动创建二叉树 (后面使用递归方式创建二叉树)
        root.setLeft(node);
        root.setRight(node1);
        node.setLeft(node4);
        node.setRight(node5);
        node1.setRight(node2);
        node1.setLeft(node3);
        binaryTree.setRoot(root);
        LinkedList<HeroNode> stack = new LinkedList<>();
        HeroNode cur = root; // 代表当前节点
        HeroNode pop = null; // 最近一次弹栈的元素
        // 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
        while(cur != null || ! stack.isEmpty()) {
            // 判断 去的路是否还有
            if(cur != null) {
                // System.out.println ("经过的路：" + cur.getNo ());
                stack.push(cur); // 压入栈 ， 为了记住回来的路
                cur = cur.getLeft();
                // 打印 回去的路
            }else {
                HeroNode peek = stack.peek();// 判断右子树是否完成了，因为走到 else 左子树肯定是完成了不然不会走到 else　里
                if(peek.getRight() == null || peek.getRight() == pop) {// 当 当前节点的右子树为 null 时，表示右子树处理完成了
                    pop = stack.pop();
                    System.out.println("回来的路：" + pop);
                }else {// 如果当右子树不为 null 的时候，我们应该进入 右子树进行下一轮的处理
                    cur = peek.getRight();
                }
            }
        }
    }
}
@SuppressWarnings("all")
// 定义 BinaryTree 二叉树
class BinaryTree {
    private HeroNode root;
    public void setRoot(HeroNode root) {
        this.root = root;
    }
}
@SuppressWarnings("all")
// 创建 HeroNode 节点
class HeroNode {
    private int no;
    private HeroNode left;
    private HeroNode right;
    public HeroNode(int no) {
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public HeroNode getLeft() {
        return left;
    }
    public void setLeft(HeroNode left) {
        this.left = left;
    }
    public HeroNode getRight() {
        return right;
    }
    public void setRight(HeroNode right) {
        this.right = right;
    }
    @Override
    public String toString() {
        return no + "";
    }
}
打印结果：
回来的路：4
回来的路：7
回来的路：2
回来的路：5
回来的路：6
回来的路：3
回来的路：1

# 优化非递归遍历 - 记忆一套代码模板 - 基于后序遍历修改
我们发现 它们的代码还是非常接近的 尤其是 前序 和 中序，就是打印的位置不同，后序其实也跟前两种差不多 只是在 向回走的时候多了 一些条件检查
那能不能将这三份代码结合起来，写一个统一的模板 能够同时处理三种遍历呢？答案是 可以的！
这样的好处是，将来记忆一套代码模板 就不能去记 三份了
我们基于后序遍历的代码来进行修改，因为后序遍历它走的路是最全的，它其实是 绕着所有节点走一圈，而对于前序中序呢 它会提前去吧栈顶元素 弹出，所以它会少走几步路，所以我们从后序遍历代码的基础上进行修改
最终代码如下：
@SuppressWarnings("all")
public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 创建一个二叉树
        BinaryTree binaryTree = new BinaryTree();
        // 创建节点
        HeroNode root = new HeroNode(1);
        HeroNode node = new HeroNode(2);
        HeroNode node1 = new HeroNode(3);
        HeroNode node2 = new HeroNode(6);
        HeroNode node3 = new HeroNode(5);
        HeroNode node4 = new HeroNode(4);
        HeroNode node5 = new HeroNode(7);
        // 手动创建二叉树 (后面使用递归方式创建二叉树)
        root.setLeft(node);
        root.setRight(node1);
        node.setLeft(node4);
        node.setRight(node5);
        node1.setRight(node2);
        node1.setLeft(node3);
        binaryTree.setRoot(root);
        LinkedList<HeroNode> stack = new LinkedList<>();
        HeroNode cur = root; // 代表当前节点
        HeroNode pop = null; // 最近一次弹栈的元素
        // 如果 沿着 左边的路还没走完 或者 栈中回去的路还没走完 那么就进行循环操作
        while(cur != null || ! stack.isEmpty()) {
            // 判断 去的路是否还有
            if(cur != null) {
                stack.push(cur); // 压入栈 ， 为了记住回来的路
                System.out.println("前：" + cur.getNo());
                // 待处理左子树
                cur = cur.getLeft();
            }else {
                HeroNode peek = stack.peek();// 判断右子树是否完成了，因为走到 else 左子树肯定是完成了不然不会走到 else　里
                if(peek.getRight() == null) {// 当 当前节点的右子树为 null 时，表示右子树处理完成了
                    System.out.println("中：" + peek.getNo());
                    pop = stack.pop();
                    System.out.println("后：" + pop.getNo());
                    // 右子树 处理完成
                }
               if(peek.getRight() == pop) {
                    pop = stack.pop();
                    System.out.println("后：" + pop.getNo());
                    // 待处理 右子树
                } else {// 如果当右子树不为 null 的时候，我们应该进入 右子树进行下一轮的处理
                    System.out.println("中：" + peek.getNo());
                    // 我要处理右子树
                    cur = peek.getRight();
                }
            }
        }
    }
}
@SuppressWarnings("all")
// 定义 BinaryTree 二叉树
class BinaryTree {
    private HeroNode root;
    public void setRoot(HeroNode root) {
        this.root = root;
    }
}
@SuppressWarnings("all")
// 创建 HeroNode 节点
class HeroNode {
    private int no;
    private HeroNode left;
    private HeroNode right;
    public HeroNode(int no) {
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public HeroNode getLeft() {
        return left;
    }
    public void setLeft(HeroNode left) {
        this.left = left;
    }
    public HeroNode getRight() {
        return right;
    }
    public void setRight(HeroNode right) {
        this.right = right;
    }
    @Override
    public String toString() {
        return no + "";
    }
}
打印结果：
前：1
前：2
前：4
中：4
后：4
中：4
中：2
前：7
中：7
后：7
中：7
后：2
中：1
前：3
前：5
中：5
后：5
中：5
中：3
前：6
中：6
后：6
中：6
后：3
后：1

这样我们就是用一套代码实现了 通用的 非递归 - 前，中，后序遍历了。