数据结构(5)-二叉树

引言

之前介绍了数据之间的线性结构，也就是线性表，每个数据结点都有着前后关系，接下来介绍一种新的数据之间的关系，叫树型关系，可以想象类似族谱，父母下面有很多儿子，一对父母可以有很多子女，而每个子女只能有一对父母，这也就是一对多关系。直接放个直观的图吧
树

基础概念

1.树可以是空树，也就是没有任何数据结点。
2.非空树有个唯一的根结点。也就是最上面那个没有父节点的。
3.每个结点下方对应的多个结点称为子结点，上方唯一对应的称为父结点。
4.一颗树，可以去掉根结点，那么根结点下面的每个子结点和所带的子子孙孙又可以看成一个新的树，称为子树。（从这里可以看出来，树的创建可以是迭代创建的，因为每个结点在没有父结点时都可以看出树的根结点）
5.结点拥有的子树(子结点)个数称为这个结点的度，一颗树的度是这棵树中结点最大的度。度为0的结点称为叶子或终端结点，不为0的则称为非终端结点或分支结点。
6.。。。懒得总结了自己看书吧

二叉树定义

1.顺序存储二叉树，因为要根据完全二叉树的编号来存放，所以空间利用率不高

1
2
3
#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点
SqBiTree bt; // 二叉树

2.链式二叉树。
1
2
3
4
5
6
7
#include<stdio.h>
#include <stdlib.h>
typedef char TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

链式二叉树的创建，先序遍历、中序遍历、后序遍历

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
//先顺创建二叉树(注意，叶子结点或者只存在一个儿子的结点，要敲空格表示下面没有的儿子)
void PreOrder_CreateBiTree(BiTree &T){
	TElemType e;
	scanf("%c",&e);//输入一个元素
	getchar();
	if(e==' ') T=NULL;
	else{
		//创建根结点存入e
		T = (BiTNode *)malloc(sizeof(BiTNode));
		T->data = e;
		//先序遍历创建坐子树
		PreOrder_CreateBiTree(T->lchild);
		//先序遍历创建右子树
		PreOrder_CreateBiTree(T->rchild);
	}
}

//先序遍历打印二叉树
void PreOrder_Traverse(BiTree T){
	if(T!=NULL){
		printf("%c",T->data);
		PreOrder_Traverse(T->lchild);
		PreOrder_Traverse(T->rchild);
	}
}
//中序遍历打印二叉树
void InOrder_Traverse(BiTree T){
	if(T!=NULL){
		InOrder_Traverse(T->lchild);
		printf("%c",T->data);
		InOrder_Traverse(T->rchild);
	}
}
//后序遍历打印二叉树
void LevelOrder_Traverse(BiTree T){
	if(T!=NULL){
		LevelOrder_Traverse(T->lchild);
		LevelOrder_Traverse(T->rchild);
		printf("%c",T->data);
	}
}
int main() {
	BiTree T;
	PreOrder_CreateBiTree(T);
	PreOrder_Traverse(T);
	printf("\n");
	InOrder_Traverse(T);
	printf("\n");
	LevelOrder_Traverse(T);
	return 0;
}

线索二叉树

线索二叉树就是把二叉树通过一定的规则 排列成一种线性结构，比如上面提到的各种遍历方法。如下图

通过先序遍历就成了：-+ab-cd/cd
通过中顺遍历就成了: a+bc-d-e/f
通过后序遍历就成了: abcd-*+ef/-
不同的遍历方法可以形成不同的线性串。所以如何将这种线性结构保存下来了。因为之前二叉树的存储方式，当有n个结点时注定会有n+1个指针被浪费

n个结点，每个结点有左右两个指针，所以一共有2n个指针，除了根结点，每个结点都要被一个指针指着，也就是有n-1个指针被用掉，所以还有n+1个指针没被用掉

那么可以将这n+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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<stdio.h>
#include <stdlib.h>
typedef char TElemType;
typedef struct BiThrNode{
	TElemType data;
	int LTag,RTag; //0表示指向子树，1表示指向前驱后继
	struct BiTNode *lchild, *rchild;
}BiThrNode, *BiThrTree;

//先顺创建二叉树(注意，叶子结点或者只存在一个儿子的结点，要敲空格表示下面没有的儿子)创建过程中记录LTag和RTag
void PreOrder_CreateBiTree(BiTree &T){
	TElemType e;
	scanf("%c",&e);//输入一个元素
	getchar();
	if(e==' ') T=NULL;
	else{
		//创建根结点存入e
		T = (BiTNode *)malloc(sizeof(BiTNode));
		T->data = e;
		//先序遍历创建坐子树
		PreOrder_CreateBiTree(T->lchild);
		if(T->lchild ==NULL) 
			LTag = 1;
		else 
			LTag=0;
		//先序遍历创建右子树
		PreOrder_CreateBiTree(T->rchild);
		if(T->rchild ==NULL) 
			RTag = 1;
		else 
			RTag=0;
	}
}
//先序遍历创建线索
void PreOrder_Traverse(BiThrTree T,BiThrNode &pre){
	if(T!=NULL){
		if(T->LTag==1){ //当前结点左子树是否存在
			T->lchild = pre; //不存在 左指针指向前驱
		}
		if(pre->RTag==1){ //前驱的右子树是否存在
			pre->rchild = T; // 不存在，前驱右指针指向当前结点
		}
		pre = T;
		PreOrder_Traverse(T->lchild);
		PreOrder_Traverse(T->rchild);
	}
}

//中序遍历创建线索
void InOrder_Traverse(BiThrTree T,BiThrNode &pre){
	if(T!=NULL){
		InOrder_Traverse(T->lchild,pre);
		if(T->LTag==1){ //当前结点左子树是否存在
			T->lchild = pre; //不存在 左指针指向前驱
		}
		if(pre->RTag==1){ //前驱的右子树是否存在
			pre->rchild = T; // 不存在，前驱右指针指向当前结点
		}
		pre = T;
		InOrder_Traverse(T->rchild,pre);
	}
}
//后序遍历创建线索
void LevelOrder_Traverse(BiThrTree T,BiThrNode &pre){
	if(T!=NULL){
		LevelOrder_Traverse(T->lchild,pre);
		LevelOrder_Traverse(T->rchild,pre);
		if(T->LTag==1){ //当前结点左子树是否存在
			T->lchild = pre; //不存在 左指针指向前驱
		}
		if(pre->RTag==1){ //前驱的右子树是否存在
			pre->rchild = T; // 不存在，前驱右指针指向当前结点
		}
		pre = T;
	}
}

// 线索化即 将二叉树在某种规则下遍历的线性结构存储下来，因此我们类似线性表，创建一个头结点来指向线性结构的第一个结点。
//头结点左指针指向二叉树根，右指针指向遍历时最后一个结点
void Treading(BiThrTree T,BiThrTree &Thr){ //前面为要线索化的树，后面为线索化后的头结点
	Thr = (BiThrTree)malloc(sizeof(BiThrNode)); //头结点分配空间
	Thr->LTag = 0;
	Thr->RTag = 1;
	if(T==NULL) Thr->lchild = Thr;
	else{
		Thr->lchild = T; //左指针指根
		pre = Thr; 
		// 线索化
		PreOrder_Traverse(T,pre);
		// InOrder_Traverse(T,pre)
		// LevelOrder_Traverse(T,pre)
		Thr->rchild = pre;
	}
}

//中序线索遍历
void Inorder_Traverse_Thr(BiThrTree T){
	BiThrTree p = T->lchild; //指向根
	while(p!=NULL){
		while(p->LTag==0){
			p=p->lchild;
		}
		printf("%c",p->data);
		while(p->RTag==1&&p->rchild!=T){ //访问后继结点
			p=p->rchild;
			printf("%c",p->data);
		}
		p=p->rchild;
	}
}

教程 数据结构
C/C++ 数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！