简述
二叉树的遍历分 DFS【深度优先遍历】 和 BFS【广度优先遍历】 两类,其中 DFS 又分为前序遍历,中序遍历和后续遍历。算法实现上 DFS 用递归容易实现,BFS 用队列容易实现,但用递归的方式也可以用栈来实现,用队列的地方也可以用递归来实现,所以总的来看可以有 8 个实现结果。
思路
前序遍历
xx 遍历中的 xx 都是相对根节点来说的,如果根节点先遍历输出,那就是前序,如果根节点介于左节点和右节点那就是中序。
假设给定一个以链表形式的二叉树的根节点,
- 首先会先输出当前这个节点 A,
- 接着看 A 节点的左节点,存在的话就可以重复步骤 1 了。
- 再接着看 A 节点的右节点,存在的话也去重复步骤 1 的操作。
这样一来步骤 2 和 3 就是递归操作了。
中序遍历
思路同前序遍历,不同点在于输出的顺序要调整,
- 首先如果 A 节点的左节点存在,就继续重复步骤 1 。
- A 节点的左节点不存在或者遍历过了,输出当前 A 节点。
- 如果 A 节点的右节点存在,重复步骤 1 。
相比前序遍历,就是对应的父节点输出顺序的不同。
后序遍历
依照前面两个的思路,后续遍历就好推导了,
- 首先如果 A 节点的左节点存在,就继续重复步骤 1 。
- 如果 A 节点的右节点存在,重复步骤 1 。
- 如果 A 节点的左右节点都不存在或者遍历过了,输出当前 A 节点。
以上就是 DFS 的递归实现思路,下面来梳理下 DFS 的栈实现思路。
前序遍历
用栈实现的思路我是通过试探的,目前仅做了些实例验证,可能会有问题,找时间通过平台验证下正确性。
考虑到前序遍历的输出要求,又结合栈的先进后出的特点,我的思路是,
- 先将根节点入栈。
- 再循环栈,判断栈不为空时,就出栈顶元素输出。
- 接着将该元素的右节点和左节点分别入栈。
- 重复步骤 2 。
我这个其实没按方法栈的思路,如果按方法栈的思路,其实就是对递归实现的翻译。就是说方法调用方法其实就是入栈操作,那么翻译上面的前序遍历递归实现应该是,
- 先入栈根节点,接着不停的入栈左节点,直到没有。这就对应着递归里的第 2 步。
- 接着做出栈操作,之后需要把出栈元素的右节点作为根节点入栈。然后就是重复步骤 1。这就对应着递归里的第 3 步。
- 就前两步不断执行,直到栈空就结束了。
中序遍历
我的思路是,
- 还是先入栈根节点,然后不停入栈左节点,这步其实和前序类似。
- 然后循环判断栈是否为空,不为空,则出栈打印。
- 然后如果出栈元素的右节点不为空就入栈,同时以该节点为根,不停入栈其左节点,直到左节点为空。
- 循环重复步骤 2,3 。直到栈空。
这整理发现和前序遍历按着递归实现的翻译思路很像。
后序遍历
我的思路是,
- 还是先入栈根节点,然后不停入栈左节点,这步和上面也是一样的。
- 然后循环判断栈是否为空,不为空的话,先获取栈顶元素,注意此时不出栈。
- 然后判断如果右节点为空则输出栈顶元素值,并移除栈顶元素。
- 如果右节点不为空则将右节点入栈,注意这里会把栈顶节点的右节点引用关联断开,然后将右节点的左节点一直入栈,知道左节点为空。
- 循环步骤 2,3,4,直到栈空。
这种实现最终会破坏树的结构,所以后来我又考虑,判断右节点是否已经输出,如输出了,即使右节点不为空也不会入栈了,而是继续下个节点操作。
层序遍历
层序遍历需要用到队列的思想,因为是一层一层的输出,所以,
- 将根节点入队。
- 循环判断队列是否为空,不为空则出队列打印,然后分别将左节点和右节点入栈。
- 重复步骤 2,直到队列为空结束。
层序遍历的递归实现方式,我理解的就是把循环体进行函数封装然后递归,
- 还是利用队列,先将根节点入队。
- 然后判断队列是否为空,遍历队列出队打印,并将左节点和右节点入队。
- 重复步骤 2 实现递归,直到遍历完整棵树。
代码
考虑到代码需要调试运行,我将写好的代码放在了 github 上,方便整理记录。
github地址:二叉树遍历实现
网友评论