数据结构-二叉树的线索化（C++）

1、中序

（1）中序遍历线索化

版本1：

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	int ltag, rtag;
	ThreadNode* lchild, * rchild;
}ThreadNode,*ThreadTree;

//求中序线索二叉树中中序序列下的第一个结点
ThreadNode *Firstnode(ThreadNode *p)
{
	while (p->rtag == 0) p = p->lchild;	//因为是中序遍历，所以找到最左下结点
	return p;
}

//找结点p在中序遍历下的后继结点
ThreadNode* nextnode(ThreadNode* p)
{
	if (p->rtag == 0) return Firstnode(p);
	else return p->rchild;
}

//不含头结点中序线索二叉树的遍历
void Inorder(ThreadNode* T)
{
	for (ThreadNode* p = Firstnode(T); p != NULL;p = nextnode(p) ){
		cout<<p->data;
	}
}
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

版本2：

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	ThreadNode* lchild, * rchild;
	int ltag, rtag;
}ThreadNode,*ThreadTree;

ThreadNode* pre = NULL;

//中序遍历主体部分
void inThread(ThreadTree T)
{
	if (T != NULL) {
		inThread(T->lchild);
		visit(T);
		inThread(T->rchild);
	}
}
void visit(ThreadNode *q)
{
	if (q->lchild == NULL) {//左子树为空，建立前驱线索
		q->lchild = pre;
		q->ltag = 1;
	}
	if (pre != NULL && pre->rchild == NULL) {//建立前驱结点的后继线索
		pre->rchild = q;
		q->rtag = 1;
	}
	pre = q;	//注意是在这里pre跟上了q
}

//线索化
void CreateInThread(ThreadTree T)
{
	pre = NULL;
	if (T != NULL) {
		inThread(T);
		if (pre->rchild == 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

（2）中序线索二叉树的遍历、找后继

大致思路：先找到中序遍历中的第一个结点，接着通过指针循环查找后继直到为空。

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	int ltag, rtag;
	ThreadNode* lchild, * rchild;
}ThreadNode,*ThreadTree;

//求中序线索二叉树中中序序列下的第一个结点
ThreadNode *Firstnode(ThreadNode *p)
{
	while (p->rtag == 0) p = p->lchild;	//因为是中序遍历，所以找到最左下结点
	return p;
}

//找结点p在中序遍历下的后继结点
ThreadNode* nextnode(ThreadNode* p)
{
	if (p->rtag == 0) return Firstnode(p);
	else return p->rchild;
}

//不含头结点中序线索二叉树的遍历
void Inorder(ThreadNode* T)
{
	for (ThreadNode* p = Firstnode(T); p != NULL;p = nextnode(p) ){
		cout<<p->data;
	}
}
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

（3）中序线索二叉树的反向遍历、寻找前驱

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	int ltag, rtag;
	ThreadNode* lchild, * rchild;
}ThreadNode, * ThreadTree;

//这里找的是p的最右下端结点，也就是最后一个遍历的结点
ThreadNode* LastNode(ThreadNode* p)
{
	while (p->rtag == 0) p = p->rchild;
	return 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))
	{
		cout << p->data;
	}
}



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

2、先序

（1）二叉树的先序线索化

版本1

注意：中间存在一个转圈问题，比如左边最下面的叶结点是没有左孩子的，visit操作会将其左孩子指向其前驱结点，然后我们进行PreThread(T->lchild)操作，结果T->lchild恰好就是其前驱结点，q又指向前驱结点了；visit操作使pre和q相等，q再指向左孩子……循环往复，因此我们必须加上一个判断条件，ltag是否为0，为0才会继续遍历左子树。

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	ThreadNode* lchild, * rchild;
	int ltag, rtag;
}ThreadNode,*ThreadTree;

ThreadNode* pre = NULL; //全局变量，指向当前方位内结点的前驱
//先序遍历主体
void PreThread(ThreadTree T)
{
	if (T != NULL) {
		visit(T);
		if (T->ltag == 0) {//防止出现转圈问题
			PreThread(T->lchild);
		}
		PreThread(T->rchild);
	}
}
//线索化
void visit(ThreadNode *q)
{
	//指向后继结点
	if (q->lchild == NULL) {
		q->lchild = pre;
		q->ltag = 1;
	}
	if (pre != NULL && pre->rchild == NULL) {
		pre->rchild = q;
		pre->rtag = 1;
	}
	pre = q;
}

//先序线索化二叉树
void CreatePreThread(ThreadTree T)
{
	pre = NULL;			//pre初始为NULL
	if (T != NULL) {		//非空的二叉树才能线索化
		PreThread(T);
		if (pre->rchild == 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

版本2

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	ThreadNode* lchild, * rchild;
	int ltag, rtag;
}ThreadNode, * ThreadTree;

ThreadTree pre = NULL; //全局变量，指向当前方位内结点的前驱

//先序线索化
void PreThread(ThreadTree p,ThreadTree&pre)
{
	if (p != NULL) {
		//根
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild != NULL) {//pre!=NULL针对最开始的情况
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;	//标记当前已访问结点
		if (p->ltag == 0) {
			PreThread(p->lchild, pre);	//递归遍历左子树
		}
		PreThread(p->rchild, pre);	//递归遍历右子树
	}
}

//先序线索化二叉树T
void CreatePreThread(ThreadTree T)
{
	ThreadTree pre = NULL;
	if (T != NULL) {
		PreThread(T,pre);
		if (pre->rchild == 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

（2） 先序线索化寻找后继

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	ThreadNode* lchild, * rchild;
	int ltag, rtag;
}ThreadNode, * ThreadTree;

ThreadNode* nextnode(ThreadNode* p)
{
	if (p->rtag == 1) {
		return p->rchild;
	}
	else {
		//假设有左孩子，根据根左右顺序下一个就是左孩子；否则就是右孩子
		if (p->ltag==0) {
			return p->lchild;
		}
		else {
			return p->rchild;
		}
	}
}

void Inorder(ThreadNode* T)
{
	for (ThreadNode* p =T; p != NULL; p = nextnode(p)) {
		cout << p->data;
	}
}

	
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

（3）先序线索化寻找前驱

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	ThreadNode* lchild, * rchild,*parent;
	int ltag, rtag;
}ThreadNode, * ThreadTree;
最后一个遍历的结点
//ThreadNode* lastnode(ThreadNode * p)
//{
//	while (p->rtag == 0) {
//		p = p->rchild;
//	}
//	return p;
//}

//专门用于对付左子树最后一个遍历的结点的情况
ThreadNode* lastnode(ThreadNode* p)
{
	//当结点左子树或者是右子树至少一个还存在的时候
	while (p->ltag != 1 && p->rtag != 1) {
		//假如p没有右子树
		if (p->rtag == 1) {
			p = p->lchild;
		}
		while (p->rtag == 0) {
			p = p->rchild;
		}
	}
	
}

ThreadNode* prenode(ThreadNode* p)
{
	//第一层：判断ltag
	if (p->ltag == 1) {
		return p->lchild;
	}
	else {
		//第二层：是否可以找到p的父结点，或者说父结点是否为空
		if (p->parent == NULL) {
			return NULL;
		}
		else {
			ThreadNode* parent = p->parent;
			//如果是左孩子，p的父结点就是前驱
			if (p == parent->lchild) {
				return parent;
			}
			//如果p为右孩子且p的左孩子为空，那么父结点就是前驱
			else if (p->lchild == NULL) {
				return parent;
			}
			//如果p为右孩子，而parent的左孩子不为空，那么p的前驱就是parent左孩子的lastnode
			else {
				return lastnode(parent->lchild);
			}
		}
	}
}

void RevPreOrder(ThreadNode* T)
{
	for (ThreadNode* p = lastnode(T); p != NULL; p = prenode(p))
	{
		cout << p->data;
	}
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

3、后序

注意：后续操作是不会出现上面的转圈问题的，因为左右子树都已经遍历过了，再进行visit操作。

（1）后序遍历线索化

版本1

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	ThreadNode* lchild, * rchild;
	int ltag, rtag;
}ThreadNode,*ThreadTree;

ThreadNode* pre = NULL;

//后序线索化主体，一边遍历一边线索化
void PostThread(ThreadTree T)
{
	if (T != NULL) {
		PostThread(T->lchild);
		PostThread(T->rchild);
		visit(T);
	}
}
void visit(ThreadNode *q)
{
	if (q->lchild == NULL) {
		q->lchild = pre;
		q->ltag = 1;
	}
	if (pre != NULL && pre->rchild == NULL) {
		pre->rchild = q;
		pre->rtag = 1;
	}
	pre = q;//标记结点
}

//后序线索化
void CreatePostThread(ThreadTree T)
{
	pre = NULL;	//pre初始为NULL
	if (T != NULL) {
		PostThread(T);
		if (pre->rchild == 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

版本2

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	ThreadNode* lchild, * rchild;
	int ltag, rtag;
}ThreadNode, * ThreadTree;

void PostThread(ThreadTree p, ThreadTree& pre)
{
	if (p != NULL)
	{
		//递归，分别线索化左子树和右子树
		PostThread(p->lchild, pre);
		PostThread(p->rchild, pre);
		//visit操作
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL)
		{
			pre->rchild = p;
			p->rtag = 1;
		}
		pre = p;
	}
}

void CreatePostThread(ThreadTree T)
{
	ThreadTree pre = NULL;
	if (T != NULL) {
		PostThread(T, pre);	//线索化二叉树
		if (pre->rchild == 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
29
30
31
32
33
34
35
36
37
38
39
40

（2）后序线索化查找前驱

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	ThreadNode* lchild, * rchild;
	int ltag, rtag;
};

ThreadNode* Prenode(ThreadNode* p)
{
	//第一层，判断ltag
	if (p->ltag == 1)
	{
		return p->lchild;
	}
	else {
		//此时p必然有左孩子
		//假设有右孩子
		if (p->rtag == 0)
		{
			return p->rchild;
		}
		else {
			return p->lchild;//根在最后且无右孩子，所以p的前驱是其左孩子
		}
	}
}

void RevPostOrder(ThreadNode* T)
{
	for (ThreadNode* p = T; p != NULL; p = Prenode(p)) {
		cout << p->data;
	}
}
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

（3）后序线索化查找后继

#include 
using namespace std;
typedef struct ThreadNode
{
	int data;
	ThreadNode* lchild, * rchild, * parent;
	int ltag, rtag;
}ThreadNode, * ThreadTree;

ThreadNode* firstnode(ThreadNode *p)
{
	while (p->ltag != 1 || p->rtag != 1) {
		//p没有左孩子的时候，只能往右走，直到有左孩子为止
		if (p->ltag == 1) {
			p = p->rchild;
		}
		//在左孩子的路上越走越远
		while (p->ltag == 0) {
			p = p->lchild;
		}
	}
	//while (p->rtag != 1 || p->ltag != 1) {     
	//	while (p->ltag == 0)
	//		p = p->lchild;
	//	if (p->rtag == 0)
	//		p = p->rchild;
	//}

}

ThreadNode* nextnode(ThreadNode* p)
{
	//第一层，判断rtag
	if (p->rtag == 1) {
		return p->rchild;
	}
	else {
		//第二层，判断是否可以找到父结点
		if (p->parent == NULL) {
			return NULL;	//没有父结点，没有后继
		}
		else {
			ThreadNode* parent = p->parent;
			if (p == parent->rchild) {
				return parent;	//为父结点的右孩子，父结点就是后继
			}
			else {//为父结点的左孩子
				if (parent->rchild == NULL) {
					return parent;//父结点没有右孩子，那么父结点就是后继
				}
				else {//父结点有右孩子，那么后继就是父结点右孩子第一个遍历的元素
					firstnode(p->rchild);
				}
			}
		}
	}
}

void postorder(ThreadNode* T)
{
	for (ThreadNode* p = firstnode(T); p != NULL; p = nextnode(p)) {
		cout << p->data;
	}
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64