【数据结构-树】线索二叉树

注：仅为本人做笔记用！如需更详细的介绍请参考其它博文。

1 线索二叉树的存储结构

/* 1 线索二叉树的存储结构 */
typedef struct ThreadNode{
	ElemType data;						// 数据域 
	struct ThreadNode *lchild, *rchild;	// 左右指针域 
	int ltag, rtag;						// 左右线索标志：1 表示为线索 
}ThreadNode, *ThreadTree;
1
2
3
4
5
6

2 中序线索二叉树（LNR）

2.1 中序线索二叉树的构造

/* 2 中序线索二叉树 */
/* 2.1 中序线索二叉树的构造 */
// 用于构造线索二叉树的初始函数，T：待构造的树
void CreateInThread (ThreadNode T){		 
	ThreadTree pre = NULL;	// 用于记录
	if (T != NULL){
		InThread(T, pre);	// 中序线索化二叉树
		if (pre->rchild == NULL)	// 运行到此处时，一定只剩中序遍历的最后一个节点未线索化，因此需单独处理 
			pre->rtag = 1;
	} 
} 

// 思路：一边中序访问一边线索化，递归算法 
void InThread (ThreadTree &p, ThreadNode &pre){
	if (p != NULL){
		// step 1: 访问左子树/左结点，同时将其线索化 
		if (p->ltag == 0)
			InThread(p->lchild, pre);	
		// step 2: 访问根结点，同时将其线索化；此时 pre 为当前访问结点 p 的前驱结点 
		InVisit(p, pre)	
		// step 3: 访问右子树/右结点，同时将其线索化 
		if (p->rtag == 0)
			InThread(p->lchild, pre);	
	}
}

void InVisit (ThreadNode &p, ThreadNode &pre){
	// step 2.1: 如果发现当前访问结点 p 的左指针域为空，则使其指向前驱线索 pre 
	if (p->lchild == NULL){		 
		p->lchild = pre;		  
		p->ltag = 1;
	}	// 当前访问结点 p 的前驱线索建立完成 
	// step 2.2: 同时检查前驱结点 pre，如果前驱结点的右指针域为空，则使其指向当前访问结点 p
	if ((pre->rchild == NULL) && pre != NULL){  
		pre->child = p;
		pre->rtag = 1;
	}	// 前驱结点 pre 的后继线索建立完成 
	// step 2.3: 前驱结点 pre 往前遍历，指向当前访问结点 p 
	pre = p; 
}
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

2.2 中序线索二叉树的遍历

中序线索二叉树的遍历实质是找指定结点 p 的后继结点，其思路如下：

• 若p->rtag == 1（即 p 无右孩子），则 p 的后继结点为p->rchild（即 p 的后继线索）；
• 若p->rtag == 0（即 p 有右孩子），则 p 的后继结点为 p 的右子树的最左下的结点。

/* 2.2 中序线索二叉树的遍历 */
// 非递归算法 
// 该函数用于求 p 的右子树的最左下结点
ThreadNode *FirstNode (ThreadNode *p){
	// 如果是寻找中序遍历的第一个结点，则为整棵树的最左下结点，它不一定是叶结点 
	// 而对于指定结点 p，其后继结点为 p 的右子树的最左下的结点，它也不一定是叶结点 
	while (p->ltag == 0)
		p = p->lchild;
	return p;
} 

ThreadNode *NextNode (ThreadNode *p){
	if (p->rtag == 0) 
		return Firstnode(p->rchild);    // 找下一个后继结点 
	else 
		return p->rchild; // 指针域是后继线索，直接返回后继线索
}

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
21
22
23

2.3 中序线索二叉树的逆遍历

中序线索二叉树的逆遍历实质是找指定结点 p 的前驱结点，其思路如下：

• 若p->ltag == 1（即 p 无左孩子），则 p 的前驱结点为p->lchild（即 p 的前驱线索）；
• 若p->ltag == 0（即 p 有左孩子），则 p 的前驱结点为 p 的左子树的最右下的结点。

/* 2.3 中序线索二叉树的逆遍历 */
// 非递归算法 
// 该函数用于求 p 的左子树的最右下结点
ThreadNode *LastNode (ThreadNode *p){
	// 如果是寻找中序逆遍历的第一个结点（即中序遍历的最后一个结点），则为整棵树的最右下结点，它不一定是叶结点 
	// 而对于指定结点 p，其前驱结点为 p 的左子树的最右下的结点，它也不一定是叶结点 
	while (p->rtag == 0)
		p = p->rchild;
	return p;
} 

ThreadNode *NextNode (ThreadNode *p){
	if (p->ltag == 0) 
		return Lastnode(p->lchild);	// 找上一个前驱结点 
	else 
		return p->lchild; // 指针域是前驱线索，直接返回前驱线索
}

void InReverse (ThreadNode &T){
	// 从中序遍历的最后一个结点开始
	for (ThreadNode *p = LastNode(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
21
22
23

3 先序线索二叉树（NLR）

3.1 先序线索二叉树的构造

/* 3 先序线索二叉树 */
/* 3.1 先序线索二叉树的构造 */
// 用于构造线索二叉树的初始函数，T：待构造的树
void CreatePreThread (ThreadNode T){		 
	ThreadTree pre = NULL;	// 用于记录
	if (T != NULL){
		preThread(T, pre);	// 先序线索化二叉树
		if (pre->rchild == NULL)	// 运行到此处时，一定只剩先序遍历的最后一个节点未线索化，因此需单独处理 
			pre->rtag = 1;
	} 
} 

// 思路：一边先序访问一边线索化，递归算法 
void PreThread (ThreadTree &p, ThreadNode &pre){
	if (p != NULL){
		// step 1: 访问根结点，同时将其线索化；此时 pre 为当前访问结点 p 的前驱结点 
		PreVisit(p, pre)
		// step 2: 访问左子树/左结点，同时将其线索化，注意此处判断线索标志是必要的！ 
		if (p->ltag == 0)
			PreThread(p->lchild, pre);	
		// step 3: 访问右子树/右结点，同时将其线索化 
		if (p->rtag == 0)
			PreThread(p->rchild, pre);	
	}
}

void PreVisit (ThreadNode &p, ThreadNode &pre){
	// step 1.1: 如果发现当前访问结点 p 的左指针域为空，则使其指向前驱线索 pre 
	if (p->lchild == NULL){		 
		p->lchild = pre;		  
		p->ltag = 1;
	}	// 当前访问结点 p 的前驱线索建立完成 
	// step 1.2: 同时检查前驱结点 pre，如果前驱结点的右指针域为空，则使其指向当前访问结点 p
	if ((pre->rchild == NULL) && pre != NULL){  
		pre->child = p;
		pre->rtag = 1;
	}	// 前驱结点 pre 的后继线索建立完成 
	// step 1.3: 前驱结点 pre 往前遍历，指向当前访问结点 p 
	pre = p; 
}
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

3.2 先序线索二叉树的遍历

先序线索二叉树的遍历实质是找指定结点 p 的后继结点，其思路如下：

• 若p->rtag == 1（即 p 无右孩子），则 p 的后继结点为p->lchild（即 p 的后继线索）；
• 若p->rtag == 0（即 p 有右孩子）且p->ltag == 1（即 p 无左孩子），则 p 的后继结点为p->rchild（即 p 的右孩子）；
• 若p->rtag == 0（即 p 有右孩子）且p->ltag == 0（即 p 有左孩子），则 p 的后继结点为p->lchild（即 p 的左孩子）。

/* 3.2 先序线索二叉树的遍历 */
ThreadNode *NextNode (ThreadNode *p){
	if (p->rtag == 1) 
		return p->lchild;	
	if ((p->rtag == 0) && (p->ltag == 1))
		return p->rchild; 
	if ((p->rtag == 0) && (p->ltag == 0))
		return p->lchild; 
}

void PreOrder (ThreadNode &T){
	// 从先序遍历的第一个结点开始
	for (ThreadNode *p = T; p != NULL; p = NextNode(p))
		visit(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.3 先序线索二叉树的逆遍历（难实现）

先序线索二叉树的遍历实质是找指定结点 p 的前驱结点。

但是，因为先序遍历顺序是 NLR，而 p 的左右孩子都是后继结点，所以找不到 p 的前驱结点。因此，需要得知 p 的父节点，才能找到其前驱结点。

4 后序线索二叉树（LRN）

4.1 后序线索二叉树的构造

/* 4 后序线索二叉树 */
/* 4.1 后序线索二叉树的构造 */
// 用于构造线索二叉树的初始函数，T：待构造的树
void CreatePostThread (ThreadNode T){		 
	ThreadTree pre = NULL;	// 用于记录
	if (T != NULL){
		preThread(T, pre);	// 后序线索化二叉树
		if (pre->rchild == NULL)	// 运行到此处时，可能只剩后序遍历的最后一个节点（根结点）未线索化，因此需单独处理 
			pre->rtag = 1;
	} 
} 

// 思路：一边后序访问一边线索化，递归算法 
void PostThread (ThreadTree &p, ThreadNode &pre){
	if (p != NULL){
		// step 1: 访问左子树/左结点，同时将其线索化
		if (p->ltag == 0)
			PostThread(p->lchild, pre);	
		// step 2: 访问右子树/右结点，同时将其线索化 
		if (p->rtag == 0)
			PostThread(p->rchild, pre);	
		// step 3: 访问根结点，同时将其线索化；此时 pre 为当前访问结点 p 的前驱结点 
		PostVisit(p, pre)
	}
}

void PostVisit (ThreadNode &p, ThreadNode &pre){
	// step 3.1: 如果发现当前访问结点 p 的左指针域为空，则使其指向前驱线索 pre 
	if (p->lchild == NULL){		 
		p->lchild = pre;		  
		p->ltag = 1;
	}	// 当前访问结点 p 的前驱线索建立完成 
	// step 3.2: 同时检查前驱结点 pre，如果前驱结点的右指针域为空，则使其指向当前访问结点 p
	if ((pre->rchild == NULL) && pre != NULL){  
		pre->child = p;
		pre->rtag = 1;
	}	// 前驱结点 pre 的后继线索建立完成 
	// step 3.3: 前驱结点 pre 往前遍历，指向当前访问结点 p 
	pre = p; 
}
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

4.2 后序线索二叉树的遍历（难实现）

后序线索二叉树的遍历实质是找指定结点 p 的后继结点。

但是，因为后序遍历顺序是 LRN，而 p 的左右孩子都是前驱结点，所以找不到 p 的后继结点。因此，需要得知 p 的父节点，才能找到其后继结点。

4.3 后序线索二叉树的逆遍历

后序线索二叉树的逆遍历实质是找指定结点 p 的前驱结点，其思路如下：

• 若p->ltag == 1（即 p 无左孩子），则 p 的后继结点为p->lchild（即 p 的前驱线索）；
• 若p->ltag == 0（即 p 有左孩子）且p->rtag == 1（即 p 无右孩子），则 p 的后继结点为p->lchild（即 p 的左孩子）；
• 若p->ltag == 0（即 p 有左孩子）且p->rtag == 0（即 p 有右孩子），则 p 的后继结点为p->rchild（即 p 的右孩子）。

/* 4.3 后序线索二叉树的逆遍历 */
ThreadNode *NextNode (ThreadNode *p){
	if (p->ltag == 1) 
		return p->rchild;	
	if ((p->ltag == 0) && (p->rtag == 1))
		return p->lchild; 
	if ((p->ltag == 0) && (p->rtag == 0))
		return p->rchild; 
}

void PostReverse (ThreadNode &T){
	// 从后序遍历的最后一个结点开始
	for (ThreadNode *p = T; p != NULL; p = NextNode(p))
		visit(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15