树型结构

数组和链表属于一对一的数据结构，每个元素都有唯一的前驱和后继；
树属于一对多的数据结构，每个元素/节点有唯一的前驱，但有N个后继；
图属于多对多的数据结构，每个元素有多个前驱和多个后继。

术语及属性

节点：包含元素和子树指针；
节点的度：节点的子树个数；
树的度：树中的最大节点度数；
根节点：没有父节点，只有子节点的节点；
叶子节点：没有子节点，只有父节点的节点；
层次：从根节点到目标节点的层数，根节点为第 1 层；
深度/高度：最大层数，即从根节点到叶子节点的层数；
路径：树中两个节点之间所经过的节点序列；
路径长度：两个节点之间路径上经过的边数；
有序树：节点的子树从左到右有序，不能位置互换；
无序树：节点的子树可互换；
森林：由n个独立的树组成的集合；

二叉树的性质

性质1：在二叉树的第i层上至多有$2^{i-1}$个节点;
性质2：深度为k的二叉树至多有$2^k-1$个节点。
性质3：对于任何一棵二叉树，若叶子数为$n_0$，度为2的节点数为$n_2$，则$n_0=n_2+1$;
性质4：具有n个节点的完全二叉树的深度必为$lo{g}_{2}n＋1$;
性质5：对于完全二叉树，若从上至下、从左至右编号，则编号为i的节点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲编号必为i/2。

树的存储结构

顺序存储：

1.父树表示法：存储一个数值，父树的下标；
2.子树表示法：存储一个数值，以及N个子树下标，N为最大子树数，-1表示不存在；
3.父树子树表示法：存储一个数值，一个父树下标，N个子树下标；

链式存储：

1.子树链表表示法：保存一个数值，N个子树指针，N为最大子树数；
2.子树兄弟表示法：保存一个数值，一个左子树指针，一个兄弟树指针；

普通二叉树进行存储时，需要被补充为完全二叉树，在缺失的子树位置补0，显然普通二叉树不适合使用顺序存储，因为会有很多0；

子树兄弟表示法的好处是：可以将任意树转换成二叉树，从而完美解决了子树数量不确定的问题，因此普通树都使用孩子兄弟表示法。

树的初始化

询问法

#include
#include

typedef struct myBtree{
	int value;
	struct myBtree *lchild,*rchild,*parent;
}tree,*pTree;

bool CreateTree(pTree a)
{
	a=(pTree)malloc(sizeof(tree));
	if(!a) return false;
	printf("请输入节点信息：\n");
	scanf("%d",&a->value);

	printf("是否添加%d的左子节点,Y/N?\n",a->value);
	char check=' ';
	while(check!='Y' && check!='N')
	{
		scanf(" %c",&check);
		if(check=='Y')
				CreateTree(a->lchild);
		else if(check=='N')
				a->lchild=NULL;
		else
				printf("参数输入错误，请重新输入。\n");
				printf("是否添加%d的左子节点,Y/N?\n",a->value);
	}

	check=' ';
	printf("是否添加%d的右子节点,Y/N?\n",a->value);
	while(check!='Y' && check!='N')
	{
		scanf(" %c",&check);
		if(check=='Y')
				CreateTree(a->lchild);
		else if(check=='N')
				a->lchild=NULL;
		else
				printf("参数输入错误，请重新输入，Y/N?\n");
				printf("是否添加%d的左子节点,Y/N?\n",a->value);
	}


	return true;
}


int main()
{
	pTree p=(pTree)malloc(sizeof(tree));
	CreateTree(p);

	return 0;
}
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

请输入节点信息：
1
是否添加1的左子节点,Y/N?
Y
请输入节点信息：
2
是否添加2的左子节点,Y/N?
N
是否添加2的左子节点,Y/N?
是否添加2的右子节点,Y/N?
Y
请输入节点信息：
4
是否添加4的左子节点,Y/N?
Y
请输入节点信息：
6
是否添加6的左子节点,Y/N?
N
是否添加6的左子节点,Y/N?
是否添加6的右子节点,Y/N?
N
是否添加6的左子节点,Y/N?
是否添加4的左子节点,Y/N?
是否添加4的右子节点,Y/N?
N
是否添加4的左子节点,Y/N?
是否添加2的左子节点,Y/N?
是否添加1的左子节点,Y/N?
是否添加1的右子节点,Y/N?
Y
请输入节点信息：
3
是否添加3的左子节点,Y/N?
Y
请输入节点信息：
5
是否添加5的左子节点,Y/N?
N
是否添加5的左子节点,Y/N?
是否添加5的右子节点,Y/N?
N
是否添加5的左子节点,Y/N?
是否添加3的左子节点,Y/N?
是否添加3的右子节点,Y/N?
N
是否添加3的左子节点,Y/N?
是否添加1的左子节点,Y/N?
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

补空法

#include
#include

typedef struct myTree{
	char value;
	struct myTree *lchild,*rchild,*prent;
}tree,*pTree;


void CreateTree(pTree a)
{
	char t;
	printf("请输入节点信息：\n");
	scanf(" %c",&t);
	if(t=='#') {
		a=NULL;
		return;
	}
	else {
		a=(pTree)malloc(sizeof(tree));
		a->value=t;
	}
	printf("添加 %c 的左节点信息。",a->value);
	CreateTree(a->lchild);
	printf("添加 %c 的右节点信息。",a->value);
	CreateTree(a->rchild);
}


int main()
{
	pTree p=(pTree)malloc(sizeof(tree));
   	CreateTree(p);
	return 0;
}
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

二叉树遍历

二叉树遍历限制了先左后右顺序，因此一共三种遍历顺序：
1.前序遍历，一般用于遍历或创建二叉树；
2.中序遍历，一般用于搜索；
3.后序遍历，？；
4.层次遍历，一般用于广度搜索。

如何理解二叉树遍历

要理解二叉树的遍历，就要函数调用和栈存放的方式。
但通常跳入栈中意义不大，因为我们使用的时候，只要知道两次递归分别是左树递归和右树递归就可以了。

前序遍历

前序遍历的顺序见图中绿线的路线，访问顺序是根左右；

void func(pTree a)
{
	if(!a) return ;

	printf("这里是前序遍历");
	func(a->left);
	func(a->rlight);
}
1
2
3
4
5
6
7
8

中序遍历

中序遍历的顺序见图中蓝线的路线，访问顺序是左根右；

void func(pTree a)
{
	if(!a) return ;

	func(a->left);
	printf("这里是中序遍历");
	func(a->rlight);
}
1
2
3
4
5
6
7
8

后序遍历

后序遍历的顺序见图中红线的路线，访问顺序是左右根；

void func(pTree a)
{
	if(!a) return ;

	func(a->left);
	func(a->rlight);
	printf("这里是中序遍历");
}
1
2
3
4
5
6
7
8

层次遍历

层次遍历的效果是：
先第一层从左到右；
再第二层从左到右

层次遍历使用队列来实现，思路是：

1.先将头节点入队；
2.开始循环，循环结束条件是队首指针等于队尾指针；
3.出队一个元素，并输出；
4.将出队元素的左右子树入队。

这样就完成了先左后右的二叉树层次遍历，要点就是元素出队后，将左右子树入队。

这里为了简化说明，没有使用循环队列，而是普通的顺序队列。

#include
#include

typedef struct myTree{
	char value;
	struct myTree *lchild,*rchild;
}tree,*pTree;

int front=0,rear=0;

void CreateTree(pTree a)
{
	a->value='a';
	pTree t=(pTree)malloc(sizeof(tree));
	a->lchild=t;
	t=(pTree)malloc(sizeof(pTree));
	a->rchild=t;

	a->lchild->value='b';
	a->lchild->lchild=NULL;
	a->lchild->rchild=NULL;

	a->rchild->value='c';
	a->rchild->lchild=NULL;
	a->rchild->rchild=NULL;
}

void EnQueue(pTree a,pTree node)
{
	if(node==NULL)return ;
	if(rear>=20) return ;
	a[rear++]=*node;
}

pTree DeQueue(pTree a)
{
	return &a[front++];
}

int main()
{
	pTree p=(pTree)malloc(sizeof(tree));
	CreateTree(p);
	tree que[20];

	//队头入队
	EnQueue(que,p);

	//当队首和队尾相等时，表示空
	while(front<rear){
		//出队一个元素
		pTree t=DeQueue(que);
		printf("%c\n",t->value);
		
		//将出队元素的子树都入队
		if(que->lchild) EnQueue(que,t->lchild);
		if(que->rchild) EnQueue(que,t->rchild);
	}
	return 0;
}
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

因此可以看出，递归解决的是一颗子树，非递归解决的是一个节点，所以递归是按照深度优先访问元素，while是按照广度优先访问元素。

还原二叉树

由二叉树的前序遍历和中序遍历可以唯一的还原一颗二叉树。
注意：由二叉树的前序和后序遍历不能还原一颗二叉树。

已知一棵二叉树的先序序列ABDECFG和中序序列DBEAFGC，还原这棵二叉树。

pTree func(char *pre,char *mid,int len)
{
	if(len==0) return NULL;
	//取前序遍历的第一个元素，即根节点
	char ch=pre[0];
	//中序遍历中，根节点的索引。
	int index=0;

	while(mid[index]!=ch)
	{
		index++;
	}
	pTree t=(pTree)malloc(sizeof(tree));
	t->value=ch;
	t->lchild=func(pre+1,mid,index);
	t->rchild=func(pre+index+1,mid+index+1,len-index-1);
	return t;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18