二叉树的遍历回顾

写在前面

本文重点在于复习并总结 二叉树每种遍历方式的递归与迭代实现,图片和示例代码均来自《邓俊辉-数据结构》

向量vector链表list线性结构,其中的元素具有天然的直接前驱直接后继

二叉树binary tree半线性结构,其元素不存在天然的直接前驱和后继,但可以通过附加某种约束,将其线性化。

线性化的方法称之为遍历traversal,具体地,遍历指的是

按照事先约定的某种规则和次序,对所有节点各访问一次且仅一次。

根据约束(规则、次序)的不同,可以分为 先序中序后序遍历以及层次遍历,根据实现方式的不同,又可分为 递归式遍历迭代式遍历

简化二叉树的数据结构为

1
2
3
4
5
6
7
#define BinNodePosi(T) BinNode<T>*
template <typename T> struct BinNode {
T data;
BinNodePosi(T) parent;
BinNodePosi(T) lChild;
BinNodePosi(T) rChild;
};

得益于递归的简洁性,先对先序、中序和后序遍历的递归实现一探究竟。

递归式遍历

二叉树可以递归地定义,根节点、左子树和右子树,左右子树也可以分别是一棵二叉树。

令当前根节点为V,左孩子和右孩子分别为L和R,对于当前这个局部,访问的次序有VLR、LVR、LRV 共3种,根据V所在的访问次序,分别称之为先序、中序和后续。

因为L和R也是树,VLR、LVR和LRV可以对L和R进一步展开,展开时也是按相应的先序、中序和后续方式访问。L和R被当成新的V,形成递归。

二叉树的遍历.png
二叉树的遍历.png

对应到代码上,三种遍历方式的递归实现可套用同一个代码模板,区别只在于访问V的位置不同

1
2
3
4
5
6
7
8
9
template <typename T, typename VST> //元素类型、操作器
void traversal(BinNodePosi(T) x, VST& visit) { //二叉树后序遍历算法(递归)
if (!x) return;
// visit(x->data); // 先序遍历
traversal(x->lChild, visit);
// visit(x->data); // 中序遍历
traversal(x->rChild, visit);
// visit(x->data); // 后序遍历
}

3种方式对应的遍历路径如下,

二叉树的先序遍历.png
二叉树的先序遍历.png

二叉树的中序遍历.png
二叉树的中序遍历.png

二叉树的后序遍历.png
二叉树的后序遍历.png

通过先序、中序和后序遍历,线性化得到的序列分别为VLR、LVR和LRV的彻底展开,序列中每个局部也都符合先序、中序和后序的次序。

下面看一下,不同遍历的迭代实现,在于洞察不同规则下访问路径的特点。

先序遍历的迭代版本

先序遍历为VLR的完全展开,先访问当前节点,如果有左子树,先访问左子树,访问完左子树再右子树。

相当于如下过程,

  • 如果有左侧通路,就沿着左侧通路自顶向下访问沿途节点,先遇到的节点先访问,直到最左侧走到头
  • 再自底向上,以同样的方式遍历右子树

如下图所示

先序遍历迭代版.png
先序遍历迭代版.png

需要逆序记录最左侧通路上节点的右孩子,恰好适合用栈实现,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//从当前节点出发,沿左分支不断深入,直至没有左分支的节点;沿途节点遇到后立即访问
template <typename T, typename VST> //元素类型、操作器
static void visitAlongLeftBranch(BinNodePosi(T) x, VST& visit, Stack<BinNodePosi(T)>& S) {
while (x) {
visit(x->data); //讵问弼前节点
S.push(x->rChild); //右孩子入栈暂存(可优化:通过判断,避免空的右孩子入栈)
x = x->lChild; //沿左分支深入一层
}
}

template <typename T, typename VST> //元素类型、操作器
void travPre(BinNodePosi(T) x, VST& visit) { //二叉树先序遍历算法(迭代版)
Stack<BinNodePosi(T)> S; //辅助栈
while (true) {
visitAlongLeftBranch(x, visit, S); //从当前节点出发,逐批访问
if (S.empty()) break; //直到栈空
x = S.pop(); //弹出下一批的起点
}
}

中序遍历的迭代版本

中序遍历为LVR的完全展开,访问完左子树,再访问当前节点,然后右子树。

流程如下:

  • 如果有左侧通路,沿着左侧通路自顶向下,沿途节点仅路过不访问,至最左侧走到头(没有左孩子的节点)
  • 再自底向上,访问沿途各节点及其右子树

如下图所示,

中序遍历迭代版.png
中序遍历迭代版.png

逆序记录路过的节点,也用栈,代码如下,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename T> //从当前节点出发,沿左分支不断深入,直至没有左分支的节点
static void goAlongLeftBranch(BinNodePosi(T) x, Stack<BinNodePosi(T)>& S) {
true//当前节点入栈后随即向左侧分支深入,迭代直到无左孩子
truewhile (x) { S.push(x); x = x->lChild; } // 该行可合并到调用函数中,以简化代码
}

template <typename T, typename VST> //元素类型、操作器
void travIn(BinNodePosi(T) x, VST& visit) { //二叉树中序遍历算法
Stack<BinNodePosi(T)> S; //辅助栈
while (true) {
goAlongLeftBranch(x, S); //从当前节点出发,逐批入栈
if (S.empty()) break; //直至所有节点处理完毕
x = S.pop(); visit(x->data); //弹出栈顶节点并讵问
x = x->rChild; //转向右子树
}
}

后序遍历的迭代版本

后序遍历为LRV的完全展开,如果有左子树先遍历左子树,遍历完左子树,再遍历右子树,最后访问当前节点。

流程如下,

  • 与先序和中序遍历不同,不再只沿着左侧通路,而是优先左侧通路,左侧到头后走右侧,直至叶子节点中最左侧的那个
  • 再自底向上,访问沿途各节点

如下图所示,

后序遍历迭代版.png
后序遍历迭代版.png

因为输出是以LRV的次序输出,所以入栈时需按VRL入栈,逆序记录沿途各节点及其右孩子和左孩子,同时,需要判断,代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T> //在以S栈顶节点为根的子树中,找到最高左侧可见叶节点
static void gotoHLVFL(Stack<BinNodePosi(T)>& S) { //沿递所遇节点依次入栈
while (BinNodePosi(T) x = S.top()) //自顶而下,反复检查当前节点(即栈顶)
if (HasLChild(*x)) { //尽可能向左
if (HasRChild(*x)) S.push(x->rChild); //若有右孩子,优先入栈
S.push(x->lChild); //然后才转至左孩子
} else //实不得已
S.push(x->rChild); //才向右
S.pop(); //返回之前,弹出栈顶的空节点
}

template <typename T, typename VST>
void travPost(BinNodePosi(T) x, VST& visit) { //二叉树的后序遍历(迭代版)
Stack<BinNodePosi(T)> S; //辅助栈
if (x) S.push(x); //根节点入栈
while (!S.empty()) {
if (S.top() != x->parent) //若栈顶非当前节点的父亲(则必为其右兄),此时需
gotoHLVFL(S); //在以其右兄为根的子树中,找到HLVFL(相当于递归深入其中)
x = S.pop(); visit(x->data); //弹出栈顶(即前一节点的后继),并访问
}
}

层次遍历

层次遍历,也就是所谓的广度优先遍历,顾名思义,按“先上后下、先左后右”的顺序逐层访问。

如下图所示,

层次遍历.png
层次遍历.png

根节点,左孩子,右孩子,左孩子的左孩子,左孩子的右孩子,右孩子的左孩子,右孩子的右孩子……先访问的节点,其孩子在下一层也是先访问,适合使用队列,在节点出列时将其左右孩子入列。代码如下,

1
2
3
4
5
6
7
8
9
10
template <typename T> template <typename VST> //元素类型、操作器
void BinNode<T>::travLevel(VST& visit) { //二叉树局次遍历算法
Queue<BinNodePosi(T)> Q; //辅助队列
Q.enqueue(this); //根节点入队
while (!Q.empty()) { //在队列再次变空之前,反复迭代
BinNodePosi(T) x = Q.dequeue(); visit(x->data); //取出队首节点并讵问
if (HasLChild(*x)) Q.enqueue(x->lChild); //左孩子入队
if (HasRChild(*x)) Q.enqueue(x->rChild); //右孩子入队
}
}

小结

二叉树的遍历,

  • 先序、中序和后序遍历,是对VLR、LVR和LRV的完全展开
  • 递归版本,使用同一模板实现,只是访问当前数据的代码放置位置不同
  • 迭代版本,三者均可以通过辅助栈实现,根据VLR、LVR和LRV推导出遍历路径,将该路径上待访问的节点逆序压栈,出栈时需考虑对右子树进行同样的遍历
  • 层次遍历,比较简单,使用辅助队列,父辈先访问的,其孩子在子辈也先访问,出列的同时将孩子入列

参考

0%