什么是树？
数据结构中的树和现实生活中的树虽然不是同一种事物，但是却有着相同的特点。
数据结构中的树，其实就是一种和现实生活中的树有着相似结构的数据逻辑结构，从同一个“根”衍生出许多“枝干”，最后衍生出更多的“叶子”。
树的定义：
树是n（你>=0）个节点的有限集。当n=0时，称为空树。在任意一个非空树中，有如下特点。
1、有且仅有一个特定的称为根的节点。
2、当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。
1
2
3
4
5
| 7
/ \
10 8
/ \ / \
4 1 3 6
|
根节点：树的最上面的那个节点，被称为根节点，所有非空树有且只有一个根节点。在上图中，元素7为根节点。
叶子节点：树的末端，没有“孩子”节点的节点被称作叶子节点。在上图中，元素4、1、3、6为叶子节点。
子树：树的非根节点，以及它的孩子节点，组成的树结构被称为子树。在上图中，由元素10、4、1组成的树结构为整棵树的子树。
树的高度：树的最大层级数，被称为树的高度或深度。在上图中，树的高度为3。
父节点：一个节点的上一层级的节点被称为当前节点的父节点。根节点没有父节点。在上图中，节点10是节点4、1的父节点。
孩子节点：一个节点的下一层级的节点被称为当前节点的孩子节点。叶子节点没有孩子节点。在上图中，节点10是节点7的孩子节点。
兄弟节点：一个节点同一层级的节点被称为当前节点的兄弟节点。所有节点都有n（n>=0）个兄弟节点。在上图中，节点8是节点10的兄弟节点。
什么是二叉树？
二叉树（binary tree）是数的一种特殊形式。二叉，顾名思义，这种数的每个节点最多有2个孩子节点。
注意：这里是最多有2两个，可能只有1个节点，或者没有孩子节点。
二叉树节点的两个孩子节点，一个被称为左孩子（lift child），一个被称为右孩子（right child）。这两个孩子节点的顺序是固定的，不能够颠倒或者混淆。
二叉树有两种特殊形式，分别叫做满二叉树和完全二叉树。
什么是满二叉树？
一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就叫做满二叉树。
1
2
3
4
5
6
| 满二叉树
7
/ \
10 8
/ \ / \
4 1 3 6
|
什么是完全二叉树？
对于一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树的所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。
1
2
3
4
5
6
| 完全二叉树
7
/ \
10 8
/ \ /
4 1 3
|
二叉树的实现
二叉树的实现方法一般有两种，分别为：
链式存储结构
链式存储结构实现二叉树，每个二叉树的节点拥有存储数据的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
| public class BinaryTree {
private TreeNode root;
public TreeNode root() {
return this.root;
}
private int createBinaryTreeByArrIndex = 0;
public BinaryTree(Integer[] arr) {
this.root = createBinaryTree(arr);
}
public TreeNode createBinaryTree(Integer[] arr) {
TreeNode node = null;
if (arr == null || arr.length == 0 || createBinaryTreeByArrIndex < 0
|| createBinaryTreeByArrIndex > arr.length - 1) {
return null;
}
Integer data = arr[createBinaryTreeByArrIndex++];
if (data != null) {
node = new TreeNode(data);
node.leftChild = createBinaryTree(arr);
node.rightChile = createBinaryTree(arr);
}
return node;
}
class TreeNode {
private Integer data;
private TreeNode leftChild;
private TreeNode rightChile;
public Integer data() {
return this.data;
}
public TreeNode leftChild() {
return this.leftChild;
}
public TreeNode rightChile() {
return this.rightChile;
}
TreeNode(Integer data) {
this.data = data;
}
}
}
|
数组
使用数组存储时，会按照层级顺序把二叉树的节点放入数组中对应的位置上去。如果某一个节点的左孩子或者右孩子缺失，则数组对应的位置也会空出来。
其中二叉树的根节点存储在数组的第一位，即下标为0的位置。
如果一个二叉树的父节点下标为parent，则该节点的左孩子节点的下标即为2*parent+1，该节点的右孩子节点的下标为2*parent+2。
同理而言，一个左孩子节点的下标为leftChild，则该左孩子节点的父节点为(leftChile-1)/2。
如果一个右孩子节点的下标为rightChild，则该右孩子节点的父节点为(rightChild-1)/2。
二叉查找树
什么是二叉查找树？
二叉查找树是一种特殊的二叉树，这种树的主要作用是进行查找操作的。
二叉树的遍历
二叉树的遍历，从节点之间的位置关系角度来看，二叉树的遍历分为4种：
如果从宏观的角度来看，二叉树的遍历归结为两大类：
深度优先遍历（前序遍历，中序遍历，后续遍历）
广度优先遍历（层序遍历）
前序遍历
二叉树的前序遍历，输出顺序为根节点、左子树、右子树。
1
2
3
4
5
| 3
/ \
2 8
/ \ \
9 10 4
|
上述的二叉树中，前序遍历的输出循序为：3、2、9、10、8、4。
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
| public static void main(String[] args) {
Integer[] arr = new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4};
BinaryTree binaryTree = new BinaryTree(arr);
BinaryTree.TreeNode root = binaryTree.root();
System.out.println("前序遍历：");
preOrderTraveral(root);
System.out.println();
preOrderTraveralWithStack(root);
}
public void preOrderTraveral(BinaryTree.TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.data() + "\t");
preOrderTraveral(node.leftChild());
preOrderTraveral(node.rightChile());
}
public void preOrderTraveralWithStack(BinaryTree.TreeNode root) {
Stack<BinaryTree.TreeNode> stack = new Stack<>();
BinaryTree.TreeNode treeNode = root;
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
System.out.print(treeNode.data() + "\t");
stack.push(treeNode);
treeNode = treeNode.leftChild();
}
if (!stack.isEmpty()) {
treeNode = stack.pop();
treeNode = treeNode.rightChile();
}
}
}
|
中序遍历
二叉树的中序遍历，输出顺序为左子树、根节点、右子树。
1
2
3
4
5
| 3
/ \
2 8
/ \ \
9 10 4
|
上述的二叉树中，中序遍历的输出循序为：9、2、10、3、8、4。
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
| public static void main(String[] args) {
Integer[] arr = new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4};
BinaryTree binaryTree = new BinaryTree(arr);
BinaryTree.TreeNode root = binaryTree.root();
System.out.println("中序遍历：");
inOrderTraveral(root);
System.out.println();
inOrderTraveralWithStack(root);
}
public void inOrderTraveral(BinaryTree.TreeNode node) {
if (node == null) {
return;
}
inOrderTraveral(node.leftChild());
System.out.print(node.data() + "\t");
inOrderTraveral(node.rightChile());
}
public void inOrderTraveralWithStack(BinaryTree.TreeNode root) {
Stack<BinaryTree.TreeNode> stack = new Stack<>();
BinaryTree.TreeNode treeNode = root;
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
stack.push(treeNode);
treeNode = treeNode.leftChild();
}
if (!stack.isEmpty()) {
treeNode = stack.pop();
System.out.print(treeNode.data() + "\t");
treeNode = treeNode.rightChile();
}
}
}
|
后序遍历
二叉树的后序遍历，输出顺序为左子树、右子树、根节点。
1
2
3
4
5
| 3
/ \
2 8
/ \ \
9 10 4
|
上述的二叉树中，后序遍历的输出循序为：9、10、2、4、8、3。
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
| public static void main(String[] args) {
Integer[] arr = new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4};
BinaryTree binaryTree = new BinaryTree(arr);
BinaryTree.TreeNode root = binaryTree.root();
System.out.println("后序遍历：");
postOrderTraveral(root);
System.out.println();
postOrderTraveralWithStack(root);
}
public void postOrderTraveral(BinaryTree.TreeNode node) {
if (node == null) {
return;
}
postOrderTraveral(node.leftChild());
postOrderTraveral(node.rightChile());
System.out.print(node.data() + "\t");
}
public void postOrderTraveralWithStack(BinaryTree.TreeNode root) {
Stack<BinaryTree.TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
BinaryTree.TreeNode treeNode = root;
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
list.add(treeNode.data());
stack.push(treeNode);
treeNode = treeNode.rightChile();
}
if (!stack.isEmpty()) {
treeNode = stack.pop();
treeNode = treeNode.leftChild();
}
}
for (int i = list.size() - 1; i >= 0; i--) {
System.out.print(list.get(i) + "\t");
}
}
|
层序遍历
二叉树的层序遍历，输出顺序按照一层一层往下输出，所以也叫作广度优先遍历。
1
2
3
4
5
| 3
/ \
2 8
/ \ \
9 10 4
|
上述的二叉树中，层序遍历的输出循序为：3、2、8、9、10、4。
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
| public static void main(String[] args) {
Integer[] arr = new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4};
BinaryTree binaryTree = new BinaryTree(arr);
BinaryTree.TreeNode root = binaryTree.root();
System.out.println("层序遍历：");
levelOrderTraveralWithQueue(root);
}
public void levelOrderTraveralWithQueue(BinaryTree.TreeNode root) {
Queue<BinaryTree.TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
BinaryTree.TreeNode node = queue.poll();
System.out.print(node.data() + "\t");
BinaryTree.TreeNode leftChild = node.leftChild();
if (leftChild != null) {
queue.offer(leftChild);
}
BinaryTree.TreeNode rightChile = node.rightChile();
if (rightChile != null) {
queue.offer(rightChile);
}
}
}
|
最后
本文Github https://github.com/herenpeng/code-learn 已收录，欢迎Star。
