数据结构之树形结构

发表于 | 更新于 | 分类于 |
字数统计 2,228 字

《回顾数据结构的基础知识》

非线性结构-树

树形结构属于非线性结构，树中结点之间具有明确的层次关系，并且结点之间有分支。例如权限、行政组织、家谱等。树形结构最大的特点是：它是一个递归结构。度、深度、层数、左孩子、右孩子、森林之类的名词，这里不就再解释了。

二叉树

二叉树不仅仅只是在树形结构中非常重要，在实际问题解决过程中，往往也是转换为二叉树的形式解决的。例如像Java中的HashMap，抽象出来的数据结构是红黑树。TreeMap，抽象出来的数据结构是二叉排序树。关于定义，这里就不多说了。其最大的特点就是每个结点最多只有两棵子树。

二叉树的存储方式，分为顺序存储结构跟链式存储结构。顺序存储结构比较浪费空间，基本都是采用链式存储。
顺序存储结构是把二叉树补充成一个完全二叉树，添加一些实际上不存在的虚节点，从根节点开始，一层一层从左往右依次存放到顺序表中。


二叉树的遍历主要有三种。先序遍历、中序遍历、后序遍历。所谓的先、中、后，都是相对于对应树或子树的根节点而言的。
先序遍历：其规律是根、左、右。

中序遍历：其规律是左、根、右。

后序遍历：其规律是左、右、根。

C代码

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
#include <stdio.h>
#include <malloc.h>
typedef struct TreeNode{
	//数据域
	char data;
	//左孩子
	struct TreeNode * pLeftChild;
	//右孩子
	struct TreeNode * pRightChild;
}TREENODE, *PTREENODE;
//创建一个树
PTREENODE createTree();
//先序输出
void printXianXu(PTREENODE);
//中序输出
void printZhongXu(PTREENODE);
//后序输出
void printHouXu(PTREENODE);
//计算深度
int binTreeDepth(PTREENODE);
//得到所有的节点数
int sumNodes(PTREENODE rootNode);
//得到所有的叶子节点数
int sumLeafNodes(PTREENODE rootNode);
//copy一个树
PTREENODE copyTree(PTREENODE);
//使用#号创建法，创建一个树
PTREENODE createTree1();
void main(){
	int depth, sum, sumLeaf;
	PTREENODE tree;
	PTREENODE rootNode = createTree();
	printXianXu(rootNode);
	//printZhongXu(rootNode);
	//printHouXu(rootNode);
	depth = binTreeDepth(rootNode);
	printf("树的深度为：%d\n", depth);
	sum = sumNodes(rootNode);
	printf("树的节点总数为：%d\n", sum);
	sumLeaf = sumLeafNodes(rootNode);
	printf("树的叶子节点总数为：%d\n", sumLeaf);
	tree = copyTree(rootNode);
	printXianXu(tree);
	tree = createTree1();
	printXianXu(tree);
}
//创建树
PTREENODE createTree(){
	PTREENODE pNodeA = (PTREENODE)malloc(sizeof(TREENODE));
	PTREENODE pNodeB = (PTREENODE)malloc(sizeof(TREENODE));
	PTREENODE pNodeC = (PTREENODE)malloc(sizeof(TREENODE));
	PTREENODE pNodeD = (PTREENODE)malloc(sizeof(TREENODE));
	PTREENODE pNodeE = (PTREENODE)malloc(sizeof(TREENODE));
	pNodeA->data = 'A';
	pNodeB->data = 'B';
	pNodeC->data = 'C';
	pNodeD->data = 'D';
	pNodeE->data = 'E';
	pNodeA->pLeftChild = pNodeB;
	pNodeA->pRightChild = pNodeC;
	
	pNodeB->pLeftChild = pNodeB->pRightChild = NULL;
	pNodeC->pLeftChild = pNodeD;
	pNodeC->pRightChild = NULL;
	pNodeD->pLeftChild = NULL;
	pNodeD->pRightChild = pNodeE;
	pNodeE->pLeftChild = pNodeE->pRightChild = NULL;
	return pNodeA;
}
//先序输出
void printXianXu(PTREENODE rootNode){
	if(NULL != rootNode){
		//先序访问根节点
		printf("%c\n", rootNode->data);
		if(NULL != rootNode->pLeftChild){
			//再先序访问左子树
			printXianXu(rootNode->pLeftChild);
		}
		if(NULL != rootNode->pRightChild){
			//再先序访问右子树
			printXianXu(rootNode->pRightChild);
		}
	}
}
//中序输出
void printZhongXu(PTREENODE rootNode){
	if(NULL != rootNode){
		if(NULL != rootNode->pLeftChild){
			//中序访问左子树
			printZhongXu(rootNode->pLeftChild);
		}
		//再中序访问根节点
		printf("%c\n", rootNode->data);
		if(NULL != rootNode->pRightChild){
			//再中序访问右子树
			printZhongXu(rootNode->pRightChild);
		}
	}
}
//后序输出
void printHouXu(PTREENODE rootNode){
	if(NULL != rootNode){
		if(NULL != rootNode->pLeftChild){
			//后序访问左子树
			printHouXu(rootNode->pLeftChild);
		}
		if(NULL != rootNode->pRightChild){
			//再后序访问右子树
			printHouXu(rootNode->pRightChild);
		}
		//再后序访问根节点
		printf("%c\n", rootNode->data);
	}
}
//深度
int binTreeDepth(PTREENODE rootNode){
	int depL, depR;
	if(rootNode ==NULL){
		return 0;
	}else{
		//计算左子树的深度
		depL = binTreeDepth(rootNode->pLeftChild);
		//计算右子树的深度
		depR = binTreeDepth(rootNode->pRightChild);
		if(depL > depR){
			return depL + 1;
		}else{
			return depR + 1;
		}
	}
}
//所有的节点
int sumNodes(PTREENODE rootNode){
	int sumNodesL, sumNodesR;
	if(rootNode ==NULL){
		return 0;
	}else{
		sumNodesL = sumNodes(rootNode->pLeftChild);
		sumNodesR = sumNodes(rootNode->pRightChild);
		return sumNodesL + sumNodesR + 1;
	}
}
//得到所有的叶子节点数
int sumLeafNodes(PTREENODE rootNode){
	int sumNodesL, sumNodesR;
	if(rootNode ==NULL){
		return 0;
	}
	if(rootNode->pLeftChild == NULL && rootNode->pRightChild == NULL){
		return 1;
	}else{
		sumNodesL = sumLeafNodes(rootNode->pLeftChild);
		sumNodesR = sumLeafNodes(rootNode->pRightChild);
		return sumNodesL + sumNodesR;
	}
}
//copy一个树
PTREENODE copyTree(PTREENODE rootNode){
	PTREENODE newNode;
	PTREENODE leftNode;
	PTREENODE rightNode;
	if(rootNode == NULL){
		return NULL;
	}
	//copy左子树
	if(rootNode->pLeftChild != NULL){
		leftNode = copyTree(rootNode->pLeftChild);
	}else{
		leftNode = NULL;
	}
	//copy右子树
	if(rootNode->pRightChild != NULL){
		rightNode = copyTree(rootNode->pRightChild);
	}else{
		rightNode = NULL;
	}
	
	//创建一个新节点
	newNode = (PTREENODE)malloc(sizeof(TREENODE));
	newNode->pLeftChild = leftNode;
	newNode->pRightChild = rightNode;
	newNode->data = rootNode->data;
	return newNode;
}
/**
//二叉树的非递归遍历算法
void inorder(PTREENODE rootNode){
	//辅助指针变量
	PTREENODE node;
	//初始化一个栈
	STACK stack;
	init(&stack);
	//把根节点压栈
	push(&stack, rootNode);
	//栈不为空，就一直循环。知道栈为空
	while(!isEmpty(&stack)){
		//栈顶的元素不给空，则一直循环
		while(getTop(&stack){
			//把左子树一直压入栈中
			push(&stack, getTop(&stack)->pLeftChild);
		}
		//执行到这里，说明栈顶是一个NULL元素。左子树为空的节点
		//把栈顶的空元素，出栈
		node = pop(&stack);
		//栈不为空时，说明还没有结束
		if(!isEmpty(&stack)){
			//左子树没有，访问根节点。栈顶的那个元素则是根节点
			printf("%c\n", getTop(&stack)->data);
			//访问完根节点，根节点则出栈
			node = pop(&stack);
			//把右子树压入栈中。执行完这一句，则进行下一个循环了。
			push(&stack, node->pRightChild);
		}
	}
}*/
//使用#号创建法，创建一个树
PTREENODE createTree1(){
	PTREENODE node = NULL;
	PTREENODE leftNode = NULL;
	PTREENODE rightNode = NULL;
	char ch;
	scanf("%c", &ch);
	//#号，则不创建树节点
	if(ch == '#'){
		return NULL;
	}else{
		//创建一个节点
		node = (PTREENODE)malloc(sizeof(TREENODE));
		node->data = ch;
		node->pLeftChild = createTree1();
		node->pRightChild = createTree1();
		return node;
	}
}

Java代码

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
package datastructure.part.tree;
/**
 * @description 
 * @author Denghs
 * @version 1.0,2018年6月30日 上午10:16:49
 * @remark 树节点
 */
public class TreeNode<T> {
	
	private TreeNode<T> leftNode;//左子树
	private TreeNode<T> rightNode;//右子树
	private T data;//数据部分
	
	public TreeNode<T> getLeftNode() {
		return leftNode;
	}
	public void setLeftNode(TreeNode<T> leftNode) {
		this.leftNode = leftNode;
	}
	public TreeNode<T> getRightNode() {
		return rightNode;
	}
	public void setRightNode(TreeNode<T> rightNode) {
		this.rightNode = rightNode;
	}
	public T getData() {
		return data;
	}
	public void setData(T data) {
		this.data = 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
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
package datastructure.part.tree;
/**
 * @description 
 * @author Denghs
 * @version 1.0,2018年6月30日 上午10:22:57
 * @remark 
 */
public class TreeUtils {
	
	/**
	 * @param node
	 * @return
	 */
	public static TreeNode<String> createTree() {
		TreeNode<String> nodeA = new TreeNode<String>();
		TreeNode<String> nodeB = new TreeNode<String>();
		TreeNode<String> nodeC = new TreeNode<String>();
		TreeNode<String> nodeD = new TreeNode<String>();
		TreeNode<String> nodeE = new TreeNode<String>();
		
		nodeA.setData("A");
		nodeB.setData("B");
		nodeC.setData("C");
		nodeD.setData("D");
		nodeE.setData("E");
		
		nodeA.setLeftNode(nodeB);
		nodeB.setLeftNode(nodeC);
		
		nodeA.setRightNode(nodeD);
		nodeD.setLeftNode(nodeE);
		
		return nodeA;
	}
	
	/**
	 * 先序输出
	 * @param rootNode
	 */
	public static <T> void printXianXu(TreeNode<T> rootNode) {
		if(null != rootNode){
			//先输出根节点
			System.out.println(rootNode.getData().toString());
			//访问左子树
			if(null != rootNode.getLeftNode()){
				printXianXu(rootNode.getLeftNode());
			}
			//访问右子树
			if(null != rootNode.getRightNode()){
				printXianXu(rootNode.getRightNode());
			}
		}
	}
	/**
	 * 中序输出
	 * @param rootNode
	 */
	public static <T> void printZhongXu(TreeNode<T> rootNode) {
		if(null != rootNode){
			//访问左子树
			if(null != rootNode.getLeftNode()){
				printZhongXu(rootNode.getLeftNode());
			}
			//输出根节点
			System.out.println(rootNode.getData().toString());
			//访问右子树
			if(null != rootNode.getRightNode()){
				printZhongXu(rootNode.getRightNode());
			}
		}
	}
	/**
	 * 后序输出
	 * @param rootNode
	 */
	public static <T> void printHouXu(TreeNode<T> rootNode) {
		if(null != rootNode){
			//访问左子树
			if(null != rootNode.getLeftNode()){
				printHouXu(rootNode.getLeftNode());
			}
			//访问右子树
			if(null != rootNode.getRightNode()){
				printHouXu(rootNode.getRightNode());
			}
			//输出根节点
			System.out.println(rootNode.getData().toString());
		}
	}
	
	/**
	 * 树的高度
	 * @param rootNode
	 * @return
	 */
	public static <T> int treeDepth(TreeNode<T> rootNode) {
		if(null == rootNode){
			return 0;
		} else {
			//计算左子树的深度
			int depL = treeDepth(rootNode.getLeftNode());
			//计算右子树的深度
			int depR = treeDepth(rootNode.getRightNode());
			if(depL > depR){
				return depL + 1;
			}else{
				return depR + 1;
			}
		}
	}
	
	/**
	 * 计算所有节点数
	 * @param rootNode
	 * @return
	 */
	public static <T> int sumNodes(TreeNode<T> rootNode) {
		if(null == rootNode){
			return 0;
		}
		//计算左子树的节点
		int sumL = sumNodes(rootNode.getLeftNode());
		//计算右子树的节点
		int sumR = sumNodes(rootNode.getRightNode());
		return sumL + sumR + 1;
	}
	
	/**
	 * 计算所有的叶子节点
	 * @param rootNode
	 * @return
	 */
	public static <T> int sumLeafNodes(TreeNode<T> rootNode) {
		if(null == rootNode){
			return 0;
		}
		//没有左子树和右子树的节点，就是叶子节点
		if(null == rootNode.getLeftNode() && null == rootNode.getRightNode()){
			return 1;
		} else {
			int sumNodesL = sumLeafNodes(rootNode.getLeftNode());
			int sumNodesR = sumLeafNodes(rootNode.getRightNode());
			return sumNodesL + sumNodesR;
		}
		
	}
	
	/**
	 * 复制一棵树
	 * @param rootNode
	 * @return
	 */
	public static <T> TreeNode<T> copyTree(TreeNode<T> rootNode) {
		TreeNode<T> newNode = null;
		TreeNode<T> leftNode = null;
		TreeNode<T> rightNode = null;
		
		if(null == rootNode){
			return null;
		}
		
		//复制左子树
		if(null != rootNode.getLeftNode()){
			leftNode = copyTree(rootNode.getLeftNode());
		}
		//复制右子树
		if(null != rootNode.getRightNode()){
			rightNode = copyTree(rootNode.getRightNode());
		}
		newNode = new TreeNode<T>();
		newNode.setData(rootNode.getData());
		newNode.setLeftNode(leftNode);
		newNode.setRightNode(rightNode);
		
		return newNode;
	}
	
	public static void main(String[] args) {
		TreeNode<String> treeNode = TreeUtils.createTree();
		
		System.out.println("先序输出");
		printXianXu(treeNode);
		
		System.out.println("中序输出");
		printZhongXu(treeNode);
		
		System.out.println("后序输出");
		printHouXu(treeNode);
		
		System.out.println("高度：" + treeDepth(treeNode));
		System.out.println("节点数：" + sumNodes(treeNode));
		System.out.println("叶子节点数：" + sumLeafNodes(treeNode));
		
		TreeNode<String> copyTree = copyTree(treeNode);
		System.out.println("先序输出");
		printXianXu(copyTree);
	}
	
}

B树、B+树

平衡多路查找树，不是很懂，只知道常用于文件系统。可以参阅《MySQL索引背后的数据结构及算法原理》一文。

树、森林与二叉树的转换

把树或森林转换成成对应的二叉树。其转换成二叉树的核心思想是二叉树的结点，左边挂孩子，右边挂兄弟。把二叉树还原成对应的树或森林，也是用同样的原理去还原即可。

非线性结构-图

图的算法比较复杂，了解了一些概念以及图常用算法的原理。并没有写出代码。
有向图、无向图、强连通图、存储结构的邻接矩阵和邻接表、遍历算法的深度优先和广度优先、最小生成树的普利姆算法及克鲁斯卡尔算法、最短路径的迪杰斯特拉算法、拓扑排序等。了解一下这些概念，并能在纸上能够大致画出过程图。还真总结不出什么。

谢谢你请我吃糖果

--------- 本文结束，感谢您的审阅 ---------
0%