关于后端:五分钟让你彻底理解二叉树的非递归遍历

什么是二叉树

在计算机科学中二叉树，binary tree，是一种数据结构，在该数据结构中每个节点最多有两个子节点，如图所示：

二叉树的定义就是这样简略，但这种看起来很简略的数据结构遍历起来一点都不简略。

如何遍历二叉树

所谓遍历简略的讲就好比在迷宫中寻宝，宝物就藏在某一个树节点当中，但咱们并不知道具体在哪个节点上，因而要找到宝物就须要将全副的树节点 系统性的搜寻一遍。

那么该怎么系统性的搜寻一遍二叉树呢？

给定一个单链表你简直不须要思考就能晓得该如何遍历，很简略，拿到头节点后处理以后节点，而后拿到头节点的下一个节点 (next) 反复上述过程直到节点为空。

你会看到遍历链表的 规定 很简略，起因就在于链表自身足够简略，就是一条线，然而二叉树不一样，二叉树不是一条简略的 ” 线 ”，而是一张三角形的 ” 网 ”。

那么给定一棵二叉树，你该如何遍历呢？以上图为例，你该如何系统性的搜寻一遍所有的节点呢(1,2,3,4,5,6)？

有的同学可能曾经看进去了，咱们能够一层一层的搜寻，顺次从左到右遍历每一层节点，直到以后层没有节点为止，这是二叉树的一种遍历办法。树的这种层级遍历办法利用了树的深度这一信息(绝对于根节点来说)，同一层的节点其深度雷同，那么咱们是不是能够利用树有左右子树这一特点来进行遍历呢？答案是必定的。

如上图所示 1 的左子树是 2，2 的左子树是 3，2 的右子树是 4。。。

假如咱们首先遍历根节点 1，而后呢，你可能会想而后遍历 2 的左子树吧，也就是 2，当咱们到了 2 这个节点之后再怎么办呢？要遍历 2 的右子树吗？显然咱们不应该去遍历 2 的右子树，为什么？起因很简略，因为从节点 1 到节点 2 咱们是沿着左子树的方向来遍历的，咱们没有理由到节点 2 的时候扭转这一 规定，接下来咱们持续沿用这一规定，也就是首先遍历左子树。

咱们来到了节点 3，节点 3 的左子树为空，因而无需遍历，而后呢？显然咱们应该遍历节点 3 的右子树，然而 3 的右子树也为空，这时以 3 为根节点的树全副遍历结束。

当遍历完节点 3 后该怎么办呢？如果你在迷宫中位于节点 3，此时节点 3 曾经是死胡同了，因而你须要做的就是 沿着来时的路原路返回 ，回退到上一个节点也就是 3 的父节点 2，这在计算机算法中被称为 回溯 ，这是系统性搜寻过程中常见的操作，回到 2 后咱们发现 2 的左子树曾经搜寻结束，因而接下来须要搜寻的就是 2 的右子树也就是节点 4，因为节点 4 还没有被搜寻过，当来到节点 4 后咱们能够持续应用上述 规定 直到这颗树种所有的节点搜寻结束为止，为什么到节点 4 的时候能够持续沿用之前的规定，起因很简略，因为以 4 为根节点的子树自身也是一棵树，因而上述规定同样实用。

因而总结一下该规定就是：

解决以后节点；搜寻以后节点的左子树；左子树搜寻结束后搜寻以后节点的右子树；复制代码

这种先解决以后节点，而后再解决以后节点的左子树和右子树的遍历形式被称为先序遍历(pre_order)；当然咱们也能够先遍历左子树，而后解决以后节点再遍历右子树，这种遍历程序被称为中序遍历(in_order)；也能够先遍历左子树再遍历右子树，最初解决以后节点，这种遍历程序被称为后序遍历(post_order)。

递归实现遍历二叉树

在解说递归遍历二叉树前咱们首先用代码示意一下二叉树的构造：

struct tree {
struct tree* left;
struct tree* right;
int value;
};
复制代码

从定义上咱们能够看出树自身就是递归定义的，二叉树的左子树是二叉树(struct tree left)，二叉树的右子树也是二叉树(struct tree right)。假如给定一颗二叉树 t，咱们该如何遍历这颗二叉树呢？

struct tree* t;  // 给定一颗二叉树
复制代码

有的同学可能会感觉二叉树的遍历是一个非常复杂的过程，真的是这样的吗？

咱们再来看一下上一节中遍历二叉树的规定：

解决以后节点；搜寻以后节点的左子树；左子树搜寻结束后搜寻以后节点的右子树；复制代码

假如咱们曾经实现了树的遍历函数，这个函数是这样定义的：

void search_tree(struct tree* t);
复制代码

只有调用 search_tree 函数咱们就能把一棵树的所有节点打印进去：

struct tree* t;   // 给定一颗二叉树
search_tree(t);   // 打印二叉树所有节点
复制代码

要是真的有这样一个函数实际上咱们的工作就实现了，如果我问你用这个函数把树 t 的左子树节点都打印进去该怎么写代码你必定会感觉羞辱智商，很简略啊，不就是把树 t 的左子树传给 search_tree 这个函数吗？

seartch_tree(t->left);   // 打印树 t 的左子树
复制代码

那么打印树 t 的右子树呢？同样 easy 啊

search_tree(t->right); // 打印树 t 的右子树
复制代码

是不是很简略，那么打印以后节点的值呢？你必定曾经懒得搭理我了 :)

printf("%d", t->value); // 打印根节点的值
复制代码

至此咱们能够打印出根节点的值，也能够打印出树 t 的左子树节点，也能够打印出树 t 的右子树节点，如果我问你既然这些问题都解决了，那么该如何实现 search_tree()这个函数？

如果你不晓得，那么就该我说这句话了：很简略啊有没有，不就是把下面几行代码写在一起嘛

void search_tree(struct tree* t) {printf("%d", t->value); // 打印根节点的值
  seartch_tree(t->left); // 打印树 t 的左子树
  search_tree(t->right); // 打印树 t 的右子树
}
复制代码

是不是很简略，是不是很 easy，惊喜不惊喜，意外不意外，咱们在仅仅只靠给出函数定义并凭借丰盛设想的状况下就把这个函数给实现了 :)

上述代码完满合乎之前定义的规定。

当然咱们须要对非凡状况进行解决，如果给定的一棵树为空，那么间接返回，最终代码就是：

void search_tree(struct tree* t) {
  if (t == NULL）// 如果是一颗空树则间接返回
    return;
     
  printf("%d", t->value); // 打印根节点的值
  seartch_tree(t->left); // 打印树 t 的左子树
  search_tree(t->right); // 打印树 t 的右子树
}
复制代码

有的同学可能会一脸懵逼，这个函数就这样实现了？正确吗，不必狐疑，这段代码无比正确，你能够本人结构一棵树并试着运行一下这段代码。

上述代码就是树的 递归遍历。

我晓得这些一脸懵逼的同学心里的怎么想的，这段代码看上去的确正确，运行起来也正确，那么这段代码的运行过程是什么样的呢？

递归调用过程

假如有这样一段代码：

void C() {}

void A() {B();
}

void main() {A();
}
复制代码

A()会调用 B()，B()会调用 C()，那么函数调用过程如图所示：

实际上每一个函数被调用时都有对应的一段内存，这段内存中保留了调用该函数时传入的 参数以及函数中定义的局部变量 ，这段内存被称为 函数帧 ，函数的调用过程具备数据结构中栈的性质，也就是 先进后出 ，比方当函数 C() 执行结束后该函数对应的函数帧开释并回到函数 B，函数 B 执行结束后对应的函数帧被开释并回到函数 A。

有了上述常识咱们就可以看一下树的递归调用函数是如何执行的了。为简略起见，咱们给定一颗比较简单的树：

当在该树上调用 search_tree 函数时整个递归调用过程是怎么的呢，如图所示：

首先在根节点 1 上调用 search_tree()，当打印完以后节点的值后在 1 的左子树节点上调用 search_tree，这时第二个函数帧入栈；打印完以后节点的值 (2) 后在 2 的左子树上调用 search_tree，这样第三个函数帧入栈；同样是打印完以后节点的值后 (3) 在 3 的左子树上调用 search_tree，第四个函数帧入栈；因为 3 的左子树为空，因而第四个函数帧执行第一句时就会退出，因而咱们又来到了第三个函数帧，此时节点 3 的左子树遍历结束，因而开始在 3 的右子树节点上调用 search_tree，接下来的过程如图所示：

这个过程会始终继续直到节点 1 的右子树也遍历结束后整个递归调用过程运行结束。留神，函数帧中实际上不会蕴含代码，这里为不便察看 search_tree 的递归调用过程才加上去的。上图中没有将整个调用过程全副展现进去，大家能够自行推导节点 5 和节点 6 是如何遍历的。

从这个过程中咱们能够看到，函数的递归调用其实没什么神秘的，和一般函数调用其实是一样的，只不过递归函数的非凡之处在于调用的不是其它函数而是自身。

从下面的函数调用过程能够得出一个重要的论断，那就是 递归函数不会始终调用上来，否则就是栈溢出了，即驰名的 Stack Overflow，那么递归函数调用栈在什么状况下就不再增长了呢，在这个例子中就是当给定的树曾经为空时递归函数调用栈将不再增长，因而对于递归函数咱们必须指明在什么状况下递归函数将间接返回，也就是常说的递归函数的进口。

递归实现树的三种遍历办法

到目前为止，咱们曾经晓得了该如何遍历树、如何用代码实现以及代码的调用过程，留神打印语句的地位：

printf("%d", t->value); // 打印根节点的值
seartch_tree(t->left); // 打印树 t 的左子树
search_tree(t->right); // 打印树 t 的右子树
复制代码

中序和后序遍历都能够很容易的用递归遍历办法来实现，如下为中序遍历：

void search_in_order(struct tree* t) {
    if (t == NULL）// 如果是一颗空树则间接返回
      return;
      
    search_in_order(t->left); // 打印树 t 的左子树
    printf("%d", t->value); // 打印根节点的值
    search_in_order(t->right); // 打印树 t 的右子树
}
复制代码

后序遍历则为：

void search_post_order(struct tree* t) {
    if (t == NULL）// 如果是一颗空树则间接返回
      return;
      
    search_in_order(t->left); // 打印树 t 的左子树
    search_in_order(t->right); // 打印树 t 的右子树
    printf("%d", t->value); // 打印根节点的值
}
复制代码

至此，有的同学可能会感觉树的遍历几乎是太简略了，那么如果让你用非递归的形式来实现树的遍历你该怎么实现呢？

_在浏览上面的内容之前请确保你曾经真正了解了前几节的内容_。

如果你还是不能彻底了解请再多仔细阅读几遍。

如何将递归转为非递归

尽管递归实现简略，然而递归函数有本人特定的问题，比方递归调用会消耗很多的栈空间，也就是内存，同时该过程较为耗时，因而其性能通常不迭非递归版本。

那么咱们该如何实现非递归的遍历树呢？

要解决这个问题，咱们必须分明的了解递归函数的调用过程。

从递归函数的调用过程能够看出，递归调用无非就是函数帧入栈出栈的过程 ，因而咱们能够间接应用栈来 模仿 这个过程，只不过栈中保留的不是函数而是树节点。

确定用栈来模仿递归调用这一点后，接下来咱们就必须明确两件事：

1. 什么状况下入栈
2. 什么状况下出栈

咱们还是以先序遍历为例来阐明。

仔细观察递归调用的过程，咱们会发现这样的法则：

1. 不管三七二十一先把从根节点开始的所有左子树节点放入栈中
2. 查看栈顶元素，如果栈顶元素有右子树那么右子树入栈并以右子树为新的根节点反复过程 1 直到栈空为止

当初咱们能够答复这两个问题了。

什么状况下入栈？

最开始时先把从根节点开始的所有左子树节点放入栈中，第二步中如果栈顶有右子树那么反复过程 1，这两种状况下会入栈。

那么什么状况下出栈呢？

当查看栈顶元素时实际上咱们就能够间接 pop 掉栈顶元素了，这是和递归调用不同的一点，为什么呢？因为查看栈顶节点时咱们能够确定一点事，那就是 以后节点的左子树肯定曾经处理完毕了，因而对于栈顶元素来说咱们须要的仅仅是其右子树的信息，拿到右子树信息后栈顶节点就能够 pop 掉了。

因而下面的形容用代码来示意就是：

void search(tree* root) {if(root == NULL)
        return ;
    stack<tree*>s;
    
    // 不管三七二十一先把从根节点开始的所有左子树节点放入栈中
    while(root){s.push(root);
        root=root->left;
    }
    
    while(!s.empty()){
        // 查看栈顶元素，如果栈顶元素有右子树那么右子树入栈并反复过程 1 直到栈空为止
        tree* top = s.top();
        tree* t = top->right;
        s.pop();
   
        while(t){s.push(t);
            t = t->left;
        }
    }
    return r;
}
复制代码

上述代码是实现树的三种非递归遍历的根底，请务必了解。

接下来就能够实现树的三种非递归遍历了。

实现二叉树的非递归遍历

有的同学可能曾经留神到了，上一节中的代码中没有 printf 语句，如果让你利用下面的代码以先序遍历形式打印节点该怎么实现呢？如果你真的曾经了解了上述代码那么就非常简单了，对于先序遍历来说，咱们只须要在 节点入栈 之前打印进去就能够了：

void search_pre_order(tree* root) {if(root == NULL)
        return ;
    stack<tree*>s;
    
    // 不管三七二十一先把从根节点开始的所有左子树节点放入栈中
    while(root){printf("%d", root->value); // 节点入栈前打印 
        s.push(root);
        root=root->left;
    }
    
    while(!s.empty()){
        // 查看栈顶元素，如果栈顶元素有右子树那么右子树入栈并反复过程 1 直到栈空为止
        tree* top = s.top();
        tree* t = top->right;
        s.pop();
   
        while(t){printf("%d", root->value); // 节点入栈前打印 
            s.push(t);
            t = t->left;
        }
    }
    return r;
}
复制代码

那么对于中序遍历呢？实际上也非常简单，咱们只须要在 节点 pop 时 打印就能够了：

void search_in_order(tree* root) {if(root == NULL)
        return ;
    stack<tree*>s;
    
    // 不管三七二十一先把从根节点开始的所有左子树节点放入栈中
    while(root){s.push(root);
        root=root->left;
    }
    
    while(!s.empty()){
        // 查看栈顶元素，如果栈顶元素有右子树那么右子树入栈并反复过程 1 直到栈空为止
        tree* top = s.top();
        printf("%d", top->value); // 节点 pop 时打印 
        tree* t = top->right;
        s.pop();
   
        while(t){s.push(t);
            t = t->left;
        }
    }
    return r;
}
复制代码

对于后续遍历呢？

后续遍历绝对简单，起因就在于 出栈的状况不一样了。

在先序和中序遍历过程中，只有左子树处理完毕实际上栈顶元素就能够出栈了，然而后续遍历状况不同，什么是后续遍历？只有左子树和右子树都遍历结束才能够解决以后节点，这是后续遍历，那么咱们该如何晓得以后节点的左子树和右子树都解决完了呢？

显然咱们须要某种办法记录下遍历的过程，实际上咱们只须要记录下遍历的前一个节点就足够了。

如果咱们晓得了遍历过程中的前一个节点，那么咱们就能够做如下判断了：

1. 如果前一个节点是以后节点的右子树，那么阐明右子树遍历结束能够 pop 了
2. 如果前一个节点是以后节点的左子树而且以后节点右子树为空，那么阐明能够 pop 了
3. 如果以后节点的左子树和右子树都为空，也就是叶子节点那么阐明能够 pop 了

这样什么状况下出栈的问题就解决了，如果不合乎这些状况就不能出栈。

只须要依据以上剖析对代码稍加批改就能够了：

void search_post_order(tree* root) {if(root == NULL)
        return ;
    stack<tree*>s;
    TreeNode* last=NULL; // 记录遍历的前一个节点
    
    // 不管三七二十一先把从根节点开始的所有左子树节点放入栈中
    while(root){s.push(root);
        root=root->left;
    }
    
    while(!s.empty()){tree* top = s.top();
        if (top->left ==NULL && top->right == NULL ||   // 以后节点为叶子节点
            last==top->right ||                         // 前一个节点为以后节点的右子树 
            top->right==NULL && last==top->left){ // 前一个节点为以后节点左子树且右子树为空
            printf("%d", top->value);            // 节点 pop 时打印 
            last = top;                           // 记录下前一个节点
            s.pop();} else {
            tree* t = top->right;
            while(t){s.push(t);
                t = t->left;
            }
        }
    }
    return r;
}
复制代码

《2020 最新 Java 根底精讲视频教程和学习路线！》

总结

树的递归遍历绝对简略且容易了解，然而递归调用实际上暗藏了绝对简单的遍历过程，要想以非递归的形式来遍历二叉树就须要认真了解递归调用过程。

链接：https://juejin.cn/post/691119…