二叉树的遍历总结(递归+迭代)

1. 中序遍历

中序遍历过程的顺序是 左 -> 根 -> 右

递归算法

递归算法比较简单,就根据中序遍历的过程,先遍历左子树,再遍历当前根,然后遍历右子树。递归函数的中止条件是当前结点为空,同时当遍历当前结点时,将该点加入遍历数组即可。

调用递归函数时可以看作它已经帮你完成了你所想要完成的所有事,它已经将答案封装好交到了你的手上。

迭代算法

递归函数实现的过程其实就是系统帮我们调用栈的过程,所以如果换为迭代算法来写,我们只需要自己模拟实现一个栈。

递归的实现也可以反映成一棵树,就是所谓的递归树,当我们调用递归函数的时候,其实有两个过程,一个是向下的的过程,然后再是向上的的过程。递归函数很好地封装了这一点,然而当我们用迭代算法时,需要自己去模拟的过程。

遍历是,我们需要将所有左子树链上的所有点放入栈中,该过程即为,然后取出栈顶,加入遍历数组,之后再放入右子树,同时注意这里的右子树指的是整个右子树的左子树链。直到遍历完所有结点。

2. 前序遍历

前序遍历顺序为根 -> 左 -> 右,所以运用递归算法时,先将该点放入遍历数组,再递归遍历左子树和右子树

递归算法

迭代算法

当前遍历结点即为,所以在迭代算法中,先将该点放入遍历数组,然后将左子树链到最低层,然后出栈,放入右子树。

3. 后序遍历

后序遍历的顺序为左 -> 右 -> 根

根据观察,后序遍历倒过来的顺序为根 -> 右 -> 左

而我们已经知道如何进行先序遍历根 -> 左 -> 右

在递归算法中比较好些,只需要调整遍历顺序。但是在迭代算法中,我们首先需要先模拟先序遍历的过程,同时将先序遍历中左右子树遍历过程对换,最后还需将遍历数组翻转才可以得到后序遍历。

递归算法

迭代算法

4. 层次遍历

算法思路

层序遍历,顾名思义需要对二叉树进行一层一层的遍历。因此可以采用BFS的思路,根据BFS的性质,每进行一次扩展,会将下一层的点全部放入队列中,所以每次在对队列进行取出操作时,当前队列中的所有元素均当前层元素。因为我们需要一边取出元素,一边放入元素。所以在每一次更迭前,先记录当前的队列的大小,即为当前层的元素,然后取出队头的该几个元素,放入当前层遍历数组level中,同时对左右儿子进行扩展。每遍历完一层,最后将level数组插入最终遍历数组中。

C ++代码

全部评论

相关推荐

评论
6
8
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务