【数据结构与算法】二叉树的遍历和线索二叉树

🔥 本文由 程序喵正在路上 原创，CSDN首发！
💖 系列专栏：数据结构与算法
🌠 首发时间：2022年10月30日
🦋 欢迎关注🖱点赞👍收藏🌟留言🐾
🌟 一以贯之的努力 不得懈怠的人生

二叉树的先 / 中 / 后序遍历

二叉树的递归特性：

• 要么是个空二叉树
• 要么就是由 “根节点 + 左子树 + 右子树” 组成的二叉树

先序遍历：根左右（NLR）
中序遍历：左根右（LNR）
后序遍历：左右根（LRN）

我们来看一个简单的例子：

对上面这棵树进行前面说到的三种遍历：

• 先序遍历：$ABDECFG$
• 中序遍历：$DBEAFCG$
• 后序遍历：$DEBFGCA$

先序遍历

先序遍历的操作过程如下：

1. 若二叉树为空，则什么也不做
2. 若二叉树非空：
   ① 访问根结点
   ② 先序遍历左子树
   ③ 先序遍历右子树

//先序遍历
void PreOrder(BiTree T) {
	if (T) {
		visit(T);  				//访问根结点
		PreOrder(T->lchild);	//递归遍历左子树
		PreOrder(T->rchild);	//递归遍历右子树
	}
}
1
2
3
4
5
6
7
8

中序遍历

先序遍历的操作过程如下：

1. 若二叉树为空，则什么也不做
2. 若二叉树非空：
   ① 先序遍历左子树
   ② 访问根结点
   ③ 先序遍历右子树

//中序遍历
void InOrder(BiTree T) {
	if (T) {
		InOrder(T->lchild);		//递归遍历左子树
		visit(T);  				//访问根结点
		InOrder(T->rchild);		//递归遍历右子树
	}
}
1
2
3
4
5
6
7
8

后序遍历

//后序遍历
void PostOrder(BiTree T) {
	if (T) {
		PostOrder(T->lchild);		//递归遍历左子树
		PostOrder(T->rchild);		//递归遍历右子树
		visit(T);  					//访问根结点
	}
}
1
2
3
4
5
6
7
8

快速求遍历序列

上图是以下列规则画出来的线路：

我们脑部空结点，首先从根结点出发，画一条路，如果左边还有没走的路，优先往左边走，走到路的尽头（空结点）就往回走；如果左边没路了，就往右边走；如果两边都没路，就往上面走

我们惊奇地发现，第一次路过的路线就是先序遍历的序列，第二次路过的路线就是中序遍历的序列，第三路过的路线就是后序遍历的序列

求树的深度

int treeDepth(BiTree T) {
	if (!T) return 0;
	else {
		int l = treeDepth(T->lchild);
		int r = treeDepth(T->rchild);
		//树的深度=Max(左子树深度, 右子树深度)+1
		return l > r ? l + 1 : r + 1;
	}
}
1
2
3
4
5
6
7
8
9

二叉树的层序遍历

算法思想

层序遍历就是一层一层地对二叉树进行遍历

1. 初始化一个辅助队列
2. 根结点入队
3. 若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
4. 重复第 $3$ 步直到队列为空

代码实现

//二叉树的结点
typedef struct BiTNode {
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//链式队列结点
typedef struct LinkNode {
	BiTNode *data;
	struct LinkNode *next;
}LinkNode;

typedef struct {
	LinkNode *front, *rear;		//队头队尾
}LinkQueue;

//层序遍历
void LevelOrder(BiTree T) {
	LinkQueue Q;					//初始化辅助队列
	InitQueue(Q);					
	BiTree p;
	EnQueue(Q, T);					//让根结点入队
	while (!IsEmpty(Q)) {			//队列不空则循环
		DeQueue(Q, p);				//队头结点出队
		visit(p);					//访问出队结点
		if (p->lchild) {
			EnQueue(Q, p->lchild);	//左孩子入队
		} 
		if (p->rchild) {
			EnQueue(Q, p->rchild);	//右孩子入队
		} 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

由遍历序列构造二叉树

如果只给出一棵二叉树的前 / 中 / 后 / 层 序遍历中的一种，我们是不能唯一确定一棵二叉树的

只有给出下列遍历序列，我们才能确定唯一的二叉树

• 前序 + 中序遍历序列
• 后序 + 中序遍历序列
• 层序 + 中序遍历序列

注意：其中都有中序遍历序列，这是因为我们可以通过前序、后序和层序遍历序列来找到根结点，并根据中序序列划分左右子树，再找到左右子树根结点，这样才能确定唯一的一棵二叉树

线索二叉树

在一棵普通的二叉树中，如何找到指定结点 $p$ 在中序遍历序列中的前驱和后继呢？

思路：

从根结点出发，重新进行一次中序遍历，指针 $p$ 记录当前访问的结点，指针 $pre$ 记录上一个被访问的结点

• 当 $q==p$ 时，$pre$ 为前驱
• 当 $pre==p$ 时，$q$ 为后继

这样查找的缺点就是很不方便，遍历操作必须从根开始

所以线索二叉树出现了

在 $n$ 个结点的二叉树中，有 $n+1$ 个空链域，我们可以利用这些空链域来记录前驱和后继的信息

线索二叉树的存储结构

下面是一棵中序线索二叉树，我们也可以将其称为线索链表

//线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild, *rchild;
	int ltag, rtag;		//左、右线索标志
}ThreadNode, *ThreadTree;
1
2
3
4
5
6

说明：

• $tag=0$ 时，表示指针指向孩子
• $tag=1$ 时，表示指针是“线索”

添加了 $tag$ 后，中序线索二叉树就变成下面这样

依次类推，我们也可以很容易地得到先序线索二叉树和后序线索二叉树

注意：

• 先序线索二叉树 —— 线索指向先序前驱、先序后继
• 中序线索二叉树 —— 线索指向中序前驱、中序后继
• 后序线索二叉树 —— 线索指向后序前驱、后序后继

二叉树的线索化

中序线索化

首先，我们来看一下怎么暴力找到中序前驱？

//辅助全局变量，用于查找结点 p 的前驱
BiTNode *p;				//p 指向目标结点
BiTNode *pre = NULL;	//pre 指向当前访问结点的前驱
BiTNode *final = NULL;	//final 用于记录最终结果

//访问结点 q
void visit(BiTNode *q) {
	if (q == p) {		//当前访问结点刚好是结点 p
		final = pre;	//找到 p 的前驱
	} else {
		pre = q;		//pre 指向当前访问的结点
	}
}

//查找中序前驱
void findPre(BiTree T) {
	if (T) {
		findPre(T->lchild);		//递归遍历左子树
		visit(T);  				//访问根结点
		findPre(T->rchild);		//递归遍历右子树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

学习上面的思想，我们可以得到中序线索化的代码

//线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild, *rchild;
	int ltag, rtag;		//左右线索标志
}ThreadNode, *ThreadTree;

//全局变量 pre, 指向当前访问结点的前驱
ThreadNode *pre = NULL;

void visit(ThreadNode *q) {
	if (!q->lchild) {	//左子树为空, 建立前驱线索
		q->lchild = pre;
		q->ltag = 1;
	}

	if (pre != NULL && pre->rchild == NULL) {	//建立前驱结点的后继线索
		pre->rchild = q;	
		pre->rtag = 1;
	}
	pre = q;
}

//中序遍历二叉树, 一边遍历一边线索化
void InThread(ThreadTree T) {
	if (T) {
		InThread(T->lchild);	//中序遍历左子树
		visit(T);				//访问根结点
		InThread(T->rchild);	//中序遍历右子树
	}
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T) {
	pre = NULL;				//pre 初始化为 NULL
	if (T) {				//非空二叉树才能线索化
		InThread(T);		//中序线索化二叉树
		if (!pre->rchild) {
			pre->rtag = 1;	//处理遍历的最后一个结点
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

另一种写法

//中序线索化
void InThread(ThreadTree p, ThreadTree &pre) {
	if (p) {
		InThread(p->lchild, pre);		//递归，线索化左子树

		if (!p->lchild) {				//左子树为空，建立前驱线索
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre && !pre->rchild) {		//建立前驱结点的后继线索
			pre->rchild = p;
			pre->rtag = 1;
		}
		
		pre = p;						//标记当前结点称为刚刚访问过的结点
		InThread(p->rchild, pre);		//递归，线索化右子树
	}
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T) {
	ThreadTree pre = NULL;
	if (T) {					//非空二叉树才进行线索化
		InThread(T, pre);		//线索化二叉树
		pre->rchlid = NULL;		//处理遍历的最后一个结点
		pre->rtag = 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

先序线索化

//线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild, *rchild;
	int ltag, rtag;		//左右线索标志
}ThreadNode, *ThreadTree;

//全局变量 pre, 指向当前访问结点的前驱
ThreadNode *pre = NULL;

void visit(ThreadNode *q) {
	if (!q->lchild) {	//左子树为空, 建立前驱线索
		q->lchild = pre;
		q->ltag = 1;
	}

	if (pre != NULL && pre->rchild == NULL) {	//建立前驱结点的后继线索
		pre->rchild = q;	
		pre->rtag = 1;
	}
	pre = q;
}

//先序遍历二叉树, 一边遍历一边线索化
void PreThread(ThreadTree T) {
	if (T) {
		visit(T);				//访问根结点
		if (T->ltag == 0) {		//lchild 不是前驱线索
			PreThread(T->lchild);	//中序遍历左子树
		}
		PreThread(T->rchild);	//中序遍历右子树
	}
}

//先序线索化二叉树T
void CreatePreThread(ThreadTree T) {
	pre = NULL;				//pre 初始化为 NULL
	if (T) {				//非空二叉树才能线索化
		PreThread(T);		//先序线索化二叉树
		if (!pre->rchild) {
			pre->rtag = 1;	//处理遍历的最后一个结点
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

后序线索化

//线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild, *rchild;
	int ltag, rtag;		//左右线索标志
}ThreadNode, *ThreadTree;

//全局变量 pre, 指向当前访问结点的前驱
ThreadNode *pre = NULL;

void visit(ThreadNode *q) {
	if (!q->lchild) {	//左子树为空, 建立前驱线索
		q->lchild = pre;
		q->ltag = 1;
	}

	if (pre != NULL && pre->rchild == NULL) {	//建立前驱结点的后继线索
		pre->rchild = q;	
		pre->rtag = 1;
	}
	pre = q;
}

//后序遍历二叉树, 一边遍历一边线索化
void PostThread(ThreadTree T) {
	if (T) {
		PostThread(T->lchild);	//中序遍历左子树
		PostThread(T->rchild);	//中序遍历右子树
		visit(T);				//访问根结点
	}
}

//后序线索化二叉树T
void CreatePostThread(ThreadTree T) {
	pre = NULL;				//pre 初始化为 NULL
	if (T) {				//非空二叉树才能线索化
		PostThread(T);		//后序线索化二叉树
		if (!pre->rchild) {
			pre->rtag = 1;	//处理遍历的最后一个结点
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

线索二叉树找前驱后继

中序线索二叉树找中序后继

在中序线索二叉树种找到指定结点 $p$ 的中序后继 $next$

思路：

• 若 $p$->$rtag==1$，说明 $p$ 的右孩子指针是 “线索”，则 $next=p$->$rchild$
• 若 $p$->$rtag==0$，则 $next$ 为 $p$ 的右子树中最左下的结点

//找到以 p 为根的子树中，第一个被中序遍历的结点
ThreadNode *FirstNode(ThreadNode *p) {
	//循环找到最左下结点（不一定是叶子结点）
	while (p->ltag == 0) p = p->lchild;
	return p;
}

//在中序线索二叉树中找到结点 p 的后继结点
ThreadNode *NextNode(ThreadNode *p) {
	//右子树最左下结点
	if (p->rtag == 0) return FirstNode(p->rchild);
	else return p->rchild;		//rtag==1直接返回后继线索
}

//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
void Inorder(ThreadNode *T) {
	for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)) {
		visit(p);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

中序线索二叉树找中序前驱

在中序线索二叉树种找到指定结点 $p$ 的中序前驱 $pre$

思路：

• 若 $p$->$ltag==1$，说明 $p$ 的左孩子指针是 “线索”，则 $pre=p$->$lchild$
• 若 $p$->$ltag==0$，则 $pre$ 为 $p$ 的左子树中最右下的结点

//找到以 p 为根的子树中，第一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p) {
	//循环找到最右下结点（不一定是叶子结点）
	while (p->rtag == 0) p = p->rchild;
	return p;
}

//在中序线索二叉树中找到结点 p 的前驱结点
ThreadNode *PreNode(ThreadNode *p) {
	//左子树最右下结点
	if (p->ltag == 0) return LastNode(p->lchild);
	else return p->lchild;		//ltag==1直接返回前驱线索
}

//对中序线索二叉树进行逆向中序遍历（利用线索实现的非递归算法）
void RevInorder(ThreadNode *T) {
	for (ThreadNode *p = LastNode(T); p != NULL; p = PreNode(p)) {
		visit(p);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

先序线索二叉树找先序后继

在先序线索二叉树种找到指定结点 $p$ 的先序后继 $next$

思路：

• 若 $p$->$rtag==1$，则 $next=p$->$rchild$
• 若 $p$->$rtag==0$，则当 $p$ 有左孩子时，先序后继为左孩子；当 $p$ 没有左孩子时，先序后继为右孩子

先序线索二叉树找先序前驱

由于在先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱，所以除非从头开始先序遍历，不然是找不到先序前驱的

如果改用三叉链表，我们就可以找到父节点，进而找到先序前驱，需要考虑的情况有：

1. 如果能找到 $p$ 的父节点，且 $p$ 是左孩子，那么 $p$ 的父节点即为其前驱
2. 如果能找到 $p$ 的父节点，且 $p$ 是右孩子，其左兄弟为空，那么 $p$ 的父节点即为其前驱
3. 如果能找到 $p$ 的父节点，且 $p$ 是右孩子，其左兄弟非空，那么 $p$ 的前驱为左兄弟子树中最后一个被先序遍历的结点
4. 如果 $p$ 是根结点，则 $p$ 没有先序前驱

后序线索二叉树找后序前驱

在后序线索二叉树种找到指定结点 $p$ 的后序前驱 $pre$

思路：

• 若 $p$->$ltag==1$，说明 $p$ 的左孩子指针是 “线索”，则 $pre=p$->$lchild$
• 若 $p$->$ltag==0$，如果有右孩子，则后序前驱为右孩子；如果没有右孩子，则后序前驱为左孩子

后序线索二叉树找后序后继

由于在后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继，所以除非从头开始先序遍历，不然是找不到后继的

如果改用三叉链表，我们就可以找到父节点，进而找到后序后继，需要考虑的情况有：

1. 如果能找到 $p$ 的父节点，且 $p$ 是右孩子，那么 $p$ 的父节点即为其后继
2. 如果能找到 $p$ 的父节点，且 $p$ 是左孩子，其右兄弟为空，那么 $p$ 的父节点即为其后继
3. 如果能找到 $p$ 的父节点，且 $p$ 是左孩子，其右兄弟非空，那么 $p$ 的后继即为右兄弟子树中第一个被后序遍历的结点
4. 如果 $p$ 是根结点，则 $p$ 没有后序后继