树型结构
概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
- 有一个特殊的结点，称为根结点，根结点没有前驱结点
- 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
- 树是递归定义的。
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
结点的度：一个结点含有子树的个数称为该结点的度
树的度：一棵树中，所有结点度的最大值称为树的度
叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I…等节点为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
根结点：一棵树中，没有双亲结点的结点，称为根结点
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度或深度：树中结点的最大层次； 如上图：树的高度为4
非终端结点或分支结点：度不为0的结点
兄弟结点：具有相同父结点的结点互称为兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟
结点的祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中任一结点都称为该结点的子孙
森林：由m（m>=0）棵互不相交的树组成的集合称为森林
树的表示形式
双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。这里就简单的了解其中最常用的孩子兄弟表示法。
1
2
3
4
5
6
|
class Node {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}
|
树的应用
文件系统管理（目录和文件）
二叉树
概念
一棵二叉树是结点的一个有限集合，该集合：
- 或者为空
- 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树不存在度大于2的结点
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
两种特殊的二叉树
- 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是(2的k次方)-1，则它就是满二叉树。
- 完全二叉树: 完全二叉树是一种特殊的二叉树，它有以下特点：
二叉树的性质
二叉树的存储
二叉树的存储结构分为：顺序存储和类似于链表的链式存储。
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
Node parent; // 当前节点的根节点
}
|
二叉树的基本操作
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
268
269
270
271
272
273
274
275
276
277
278
279
280
|
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BinaryTree {
static class TreeNode {
/**
* param val 节点的元素
* param left 左子树
* param right 右子树
*/
public char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
/**
* 创建一个树
* @return 树的根节点
*/
public TreeNode createTree(){
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
E.right = H;
return A;
}
/**
* 前序遍历
* @param root 树的根节点
*/
public void preOrder(TreeNode root){
if(root == null){
return;
}
System.out.print(root.val);
preOrder(root.left);
preOrder(root.right);
}
/**
* 前序遍历非递归
* @param root 树的根节点
*/
public void preOrderNor(TreeNode root){
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
System.out.println(cur.val);
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
}
/**
* 中序遍历
* @param root 树的根节点
*/
public void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.val);
inOrder(root.right);
}
/**
* 中序遍历非递归
* @param root 树的根节点
*/
public void inOrderNor(TreeNode root){
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
System.out.println(top.val);
cur = top.right;
}
}
/**
* 后序遍历
* @param root 树的根节点
*/
public void postOrder(TreeNode root){
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val);
}
/**
* 后续遍历非递归
* @param root 树的根节点
*/
public void postOrderNor(TreeNode root){
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode prev = null;
while(cur != null || !stack.isEmpty()) {
while ((cur != null)) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.peek();
if (top.right == null || top.right == prev) {
System.out.println(top.val);
stack.pop();
prev = top;
} else {
cur = top.right;
}
}
}
/**
* 求树的节点个数
* @param root 树的根节点
* @return 节点的个数
*/
public int size (TreeNode root){
if(root == null){
return 0;
}
return size(root.left) + size(root.right) + 1;
}
/**
* 求树的叶子节点个数
* @param root 树的根节点
* @return 叶子节点的个数
*/
public int getLeafNodeCount(TreeNode root){
if(root == null)
return 0;
if(root.left == null && root.right == null)
return 1;
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
/**
* @param root 树的根节点
* @param k 树的层数
* @return 第k层节点的个数
*/
public int getKLevelNodeCount (TreeNode root,int k){
if(root == null)
return 0;
if(k == 1)
return 1;
return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
}
/**
* 求树的高度
* @param root 树的根节点
* @return 树的高度
*/
public int getHeight(TreeNode root){
if(root == null){
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
/**
* 查找树中是否包含val元素
* @param root 树的根节点
* @param val 要查找的元素
* @return 找到的节点
*/
public TreeNode find(TreeNode root,char val){
if(root == null)
return null;
if(root.val == val)
return root;
TreeNode left = find(root.left,val);
if(left != null)
return left;
TreeNode right = find(root.right,val);
if(right != null)
return right;
return null;
}
/**
* 层序遍历
* @param root 树的根节点
*/
public void levelOrder(TreeNode root){
if(root == null){
return;
}
Queue<TreeNode>queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode cur = queue.poll();
System.out.print(cur.val);
if(cur.left != null)
queue.offer(cur.left);
if(cur.right != null)
queue.offer(cur.right);
}
}
/**
* 判断是否是完全二叉树
* @param root 树的根节点
* @return true 是 false 不是
*/
public boolean isCompleteTree(TreeNode root){
if(root == null){
return true;
}
Queue<TreeNode>queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode cur = queue.poll();
if (cur != null) {
queue.offer(cur.left);
queue.offer(cur.right);
}else{
break;
}
}
while (!queue.isEmpty()){
TreeNode node = queue.poll();
if (node != null){
return false;
}
}
return true;
}
}
|