数据结构——树（树的基本概念）_树的定义

定义

线性表是一对一，但是树就不一样了，一对多的性质扑面而来，先看一下百度的说法吧，
树：它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树中的专有名词

就用这张图来描述树的特征：

• 当n=0，就称为空树
• 有且只有一个称为根的结点，这里为A
• 当n>1时，其余结点可以分为m(m>0)个互不相交的有限集，其中每个集合又是一棵树，称为子树
• 举个例子：
  是以B为结点的子树

下面我们来将结点分一下类：

1. 树的结点包含一个数据结构及若干指向其子树的分支
2. 结点拥有的子树称为结点的度
3. 度为0的结点称为叶结点或终端结点
4. 度不为0的结点称为非终端结点或分支结点
   看图
   
   结点的关系：
   这块有点像我们的家庭关系，比较好理解
   像上图A为B，C的双亲，B，C互为兄弟，对于#来说，D，B，A，都是它的祖先，反之A的子孙有B，D，#

其他相关概念，特定情况才会用到

引入了深度，可以说是有几层就有多少深度.
无序树：如果将树中结点的各子树看成从左到右都是没有次序，都可以随意互换，则称为无序树，反之为有序树

树中的基本操作

双亲表示法

树真的太像人了，人可能暂时没有孩子但是一定有且只有一个父母，树也一样除了根结点外，其余每个结点，它不一定有孩子，但是一定有且只有一个双亲

/*
Project: Tree_parent(树-双亲表示法)

基本操作函数：
InitTree(Tree &T) 参数T，树根节点 作用：初始化树，先序递归创建
InsertNode(Tree &T, TElemType node) 插入树的结点 参数：树T,结点node 作用：在双亲数组中插入结点，增加树的结点值
InsertParent(Tree &T, TElemType node1, TElemType node2)//插入双亲数组的双亲域 参数：树T ，结点node1,结点node2
                                                       //作用：使双亲数组中,node2对应的双亲域为node1的下标
GetIndegree(Tree &T, TElemType node)                   //得到某结点入度 参数：树T，结点node 结点不存在返回-1
GetOutdegree(Tree &T, TElemType node)                  //得到某结点出度 参数：树T，结点node 结点不存在返回-1
PreOrder(Tree T)  参数：树T,根节点下标 作用：先序遍历树
PostOrder(Tree T) 参数：树T,根节点下标 作用：后序遍历树
LevelOrder(Tree T)参数：树T            作用：层序遍历树
功能实现函数：
CreateTree(Tree &T) 参数T，树根节点 作用：创建树，调用InsertNode,InsertParent
Traverse(Tree T)    参数T，树根节点 作用：PreOrder InOrder PostOrder LevelOrder遍历树
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<iostream>
#define TElemType char
#define Max 100
using namespace std;
//树的结点数据结构
typedef struct TNode
{
	TElemType data;//数据域
	int parent;    //双亲
}TNode;
//树的数据结构
typedef struct Tree
{
 
	TNode parent[Max];
	int NodeNum;
 
}Tree;
//********************************基本操作函数********************************//
//初始化树函数 参数：树T 作用：规定数据域为#，则为空，双亲为-1,则为空
void InitTree(Tree &T)
{
	for (int i=0;i<Max;i++)
	{
		T.parent[i].data = '#';
		T.parent[i].parent = -1;
	}
	T.NodeNum = 0;
}
//插入树的结点 参数：树T,结点node 作用：在双亲数组中插入结点，增加树的结点值
bool InsertNode(Tree &T, TElemType node)
{
	
	if (node != '#')
	{
		T.parent[T.NodeNum++].data = node;//插入到双亲数组中
		return true;
	}
	return false;
}
//插入双亲数组的双亲域 参数：树T ，结点node1,结点node2
//作用：使双亲数组中,node2对应的双亲域为node1的下标
bool InsertParent(Tree &T, TElemType node1, TElemType node2)
{
	int place1, place2;
	place1 = -1;place2 = -1;
	for (int i=0;i<T.NodeNum;i++)//查找两点是否存在
	{
		if (node1 == T.parent[i].data)place1 = i;
		if (node2 == T.parent[i].data)place2 = i;
	}
	if (place1 != -1 && place2 != -1)//两点均存在
	{
		T.parent[place2].parent = place1;
		return true;
	}
	return false;
}
//得到某结点入度 参数：树T，结点node 结点不存在返回-1
int GetIndegree(Tree &T, TElemType node)
{
	int place = -1;
	for (int i = 0;i<T.NodeNum;i++)
	{
		if (T.parent[i].data == node)place = i;
	}
	if (place!=-1)//结点存在
	{
		if(T.parent[place].parent!=-1)return 1;//双亲只能有一个
		else return 0; //根节点没有双亲，即没有入度
	}
	return -1;
}
//得到某结点出度 参数：树T，结点node 结点不存在返回-1
int GetOutdegree(Tree &T, TElemType node)
{
	int place = -1;
	int outdegree = 0;
	for (int i = 0;i<T.NodeNum;i++)
	{
		if (T.parent[i].data == node)place = i;
	}
	if (place != -1)
	{
		for (int i = 0;i < T.NodeNum;i++)
		{
			if (T.parent[i].parent == place)outdegree++;
		}
		return outdegree;
	}
	return -1;
}
//先序遍历 参数：树T,根节点下标
void PreOrder(Tree T,int i)
{
	if (T.NodeNum != 0)
	{
		cout << T.parent[i].data << " ";
		for(int j=0;j<T.NodeNum;j++)
		{
		  if(T.parent[j].parent==i)
		  PreOrder(T,j);//按左右先序遍历子树
		}
	}
}
//后序遍历 参数：树T,根节点下标
void PostOrder(Tree T,int i)
{
	if (T.NodeNum != 0)
	{
		
		for (int j = 0;j<T.NodeNum;j++)
		{
			if (T.parent[j].parent == i)
				PostOrder(T, j);//按左右先序遍历子树
		}
		cout << T.parent[i].data << " ";
	}
}
//层序遍历 参数：树T
void LevelOrder(Tree T)
{
	queue<TNode> q;//借助队列
	if (T.NodeNum!=0)
	{
		TNode temp;//暂存要出队的结点
		q.push(T.parent[0]);//根结点入队
		while (!q.empty())//队列非空
		{
			temp = q.front();
			q.pop();
			cout<<temp.data<<" ";
			for (int j = 0;j<T.NodeNum;j++)
			{
				if (T.parent[T.parent[j].parent].data == temp.data)//当前结点的父节点的数据域与弹出的相同 
					//因为temp没有保存下标，只能按这种方式比较，默认结点名称不同
					q.push(T.parent[j]);//队列先进先出，先入左孩子
			}
		}
	}
}
//**********************************功能实现函数*****************************//
//创建树，调用InsertNode,InsertParent
void CreateTree(Tree &T)
{
	int nodenum = 0;
	int parent;
	TElemType node,node1,node2;
	printf("请输入树的结点个数:");
	cin >> nodenum;
	parent = nodenum - 1;
	printf("请输入树的结点名称（空格隔开）:");
	while (nodenum--)
	{
		cin >> node;
		InsertNode(T,node);
	}
	printf("请输入树的结点间的双亲关系（一对为一双亲关系，A B表示A为B的双亲）:\n");
	while (parent--)
	{
		cin >> node1>>node2;
		InsertParent(T,node1,node2);
	}
	printf("\n");
}
//入度
void Indegree(Tree &T)
{
	TElemType node;
	int indegree;
	printf("请输入结点名称:\n");
	cin >> node;
	indegree = GetIndegree(T, node);
	if (-1 != indegree)
		cout << "该结点入度为：" << indegree << endl;
	else
		cout << "结点不存在。" << endl;
}
//出度
void Outdegree(Tree &T)
{
	TElemType node;
	int outdegree;
	printf("请输入结点名称:\n");
	cin >> node;
	outdegree = GetOutdegree(T, node);
	if (-1 != outdegree)
		cout << "该结点出度为：" << outdegree << endl;
	else
		cout << "结点不存在。" << endl;
}
//遍历功能函数 调用PreOrder InOrder PostOrder LevelOrder
void Traverse(Tree T)
{
	int choice;
	while (1)
	{
		printf("********1.先序遍历    2.后序遍历*********\n");
		printf("********3.层次遍历    4.返回上一单元*********\n");
		printf("请输入菜单序号：\n");
		scanf("%d", &choice);
		if (4 == choice) break;
		switch (choice)
		{
		case 1: {printf("树先序遍历序列:");PreOrder(T,0);printf("\n");}break;
		case 2: {printf("树后序遍历序列:");PostOrder(T,0);printf("\n");}break;
		case 3: {printf("树层序遍历序列:");LevelOrder(T);printf("\n");}break;
		default:printf("输入错误！！！\n");break;
		}
	}
}
//菜单
void menu()
{
	printf("********1.创建     2.某点入度*********\n");
	printf("********3.某点出度 4.遍历*************\n");
	printf("********5.退出\n");
}
//主函数
int main()
{
	Tree T;
	int choice = 0;
	InitTree(T);
	while (1)
	{
		menu();
		printf("请输入菜单序号：\n");
 
		scanf("%d", &choice);
		if (5 == choice) break;
		switch (choice)
		{
		case 1:CreateTree(T);break;
		case 2:Indegree(T);break;
		case 3:Outdegree(T);break;
		case 4:Traverse(T);break;
		default:printf("输入错误！！！\n");break;
		}
	}
	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
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267

所用图

孩子表示法

顾名思义，就是每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们也把这种方法叫做多重链表表式法，有点像线性表中的链式表示法
那么这样的话，我这里就写伪代码了

//指针域的个数就等于树的度，其中树的度又等于树各个结点度的最大值
struct ChildNode
{
	int data；
	ChildNode*;
}
ChildNode *D;//d为最大结点
d.ChildNode;

1
2
3
4
5
6
7
8
9

不难看出这样的话，如果各个树度之间的差距不大，还可以，但是如果各个树度之间的差距很大，那么很浪费空间，原因是许多的结点域都是空的

孩子兄弟表示法

这个可以说是学二叉树的基础，有的兄弟可能要说了，为什么不是兄弟表示法？还要带上我的孩子一起？
因为可能存在下面这种情况，只有了兄弟，孩子没有办法往下延申了，那么如何孩子和兄弟一起开呢？
是这样的，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，记得不是堂兄弟昂，是亲兄弟，下面我们看图

观察后，我们可以发现每个结点最多有俩个孩子，也就是一个简单的二叉树，这也可以说是，孩子兄弟表示法最大的好处

struct Node
{
	int data;
	*firstchild,*ringtsib;
}
Node *Tree;
1
2
3
4
5
6

刷题巩固

相同的树