一、樹
樹與線性表、棧、隊列等線性結構不同，樹是一種非線性結構。
一棵樹只有一個根節點，如果一棵樹有了多個根節點，那它已經不再是一棵樹了，而是多棵樹的集合，也被稱為森林。
二、樹的父節點表示法
樹中除根節點之外每個節點都有一個父節點，為了記錄樹中節點與節點之間的父子關系，可以為每個節點增加一個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
|
package com.ietree.basic.datastructure.tree;import java.util.ArrayList;import java.util.List;/** * Created by ietree * 2017/4/30 */public class TreeParent<E> { public static class Node<T> { T data; // 保存其父節點的位置 int parent; public Node() { } public Node(T data) { this.data = data; } public Node(T data, int parent) { this.data = data; this.parent = parent; } public String toString() { return "TreeParent$Node[data=" + data + ", parent=" + parent + "]"; } } private final int DEFAULT_TREE_SIZE = 100; private int treeSize = 0; // 使用一個Node[]數組來記錄該樹里的所有節點 private Node<E>[] nodes; // 記錄樹的節點數 private int nodeNums; // 以指定節點創建樹 public TreeParent(E data) { treeSize = DEFAULT_TREE_SIZE; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data, -1); nodeNums++; } // 以指定根節點、指定treeSize創建樹 public TreeParent(E data, int treeSize) { this.treeSize = treeSize; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data, -1); nodeNums++; } // 為指定節點添加子節點 public void addNode(E data, Node parent) { for (int i = 0; i < treeSize; i++) { // 找到數組中第一個為null的元素，該元素保存新節點 if (nodes[i] == null) { // 創建新節點，并用指定的數組元素保存它 nodes[i] = new Node(data, pos(parent)); nodeNums++; return; } } throw new RuntimeException("該樹已滿，無法添加新節點"); } // 判斷樹是否為空 public boolean empty() { // 根結點是否為null return nodes[0] == null; } // 返回根節點 public Node<E> root() { // 返回根節點 return nodes[0]; } // 返回指定節點（非根結點）的父節點 public Node<E> parent(Node node) { // 每個節點的parent記錄了其父節點的位置 return nodes[node.parent]; } // 返回指定節點（非葉子節點）的所有子節點 public List<Node<E>> children(Node parent) { List<Node<E>> list = new ArrayList<Node<E>>(); for (int i = 0; i < treeSize; i++) { // 如果當前節點的父節點的位置等于parent節點的位置 if (nodes[i] != null && nodes[i].parent == pos(parent)) { list.add(nodes[i]); } } return list; } // 返回該樹的深度 public int deep() { // 用于記錄節點的最大深度 int max = 0; for (int i = 0; i < treeSize && nodes[i] != null; i++) { // 初始化本節點的深度 int def = 1; // m 記錄當前節點的父節點的位置 int m = nodes[i].parent; // 如果其父節點存在 while (m != -1 && nodes[m] != null) { // 向上繼續搜索父節點 m = nodes[m].parent; def++; } if (max < def) { max = def; } } return max; } // 返回包含指定值的節點 public int pos(Node node) { for (int i = 0; i < treeSize; i++) { // 找到指定節點 if (nodes[i] == node) { return i; } } return -1; }} |
測試類：
|
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
|
package com.ietree.basic.datastructure.tree;import java.util.List;/** * Created by ietree * 2017/4/30 */public class treeParentTest { public static void main(String[] args) { TreeParent<String> tp = new TreeParent<String>("root"); TreeParent.Node root = tp.root(); System.out.println(root); tp.addNode("節點1", root); System.out.println("此樹的深度：" + tp.deep()); tp.addNode("節點2", root); // 獲取根節點的所有子節點 List<TreeParent.Node<String>> nodes = tp.children(root); System.out.println("根節點的第一個子節點：" + nodes.get(0)); // 為根節點的第一個子節點新增一個子節點 tp.addNode("節點3", nodes.get(0)); System.out.println("此樹的深度：" + tp.deep()); }} |
程序輸出：
TreeParent$Node[data=root, parent=-1]
此樹的深度：2
根節點的第一個子節點：TreeParent$Node[data=節點1, parent=0]
此樹的深度：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
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
|
package com.ietree.basic.datastructure.tree;import java.util.ArrayList;import java.util.List;/** * Created by ietree * 2017/4/30 */public class TreeChild<E> { private static class SonNode { // 記錄當前節點的位置 private int pos; private SonNode next; public SonNode(int pos, SonNode next) { this.pos = pos; this.next = next; } } public static class Node<T> { T data; // 記錄第一個子節點 SonNode first; public Node(T data) { this.data = data; this.first = null; } public String toString() { if (first != null) { return "TreeChild$Node[data=" + data + ", first=" + first.pos + "]"; } else { return "TreeChild$Node[data=" + data + ", first=-1]"; } } } private final int DEFAULT_TREE_SIZE = 100; private int treeSize = 0; // 使用一個Node[]數組來記錄該樹里的所有節點 private Node<E>[] nodes; // 記錄節點數 private int nodeNums; // 以指定根節點創建樹 public TreeChild(E data) { treeSize = DEFAULT_TREE_SIZE; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data); nodeNums++; } // 以指定根節點、指定treeSize創建樹 public TreeChild(E data, int treeSize) { this.treeSize = treeSize; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data); nodeNums++; } // 為指定節點添加子節點 public void addNode(E data, Node parent) { for (int i = 0; i < treeSize; i++) { // 找到數組中第一個為null的元素，該元素保存新節點 if (nodes[i] == null) { // 創建新節點，并用指定數組元素保存它 nodes[i] = new Node(data); if (parent.first == null) { parent.first = new SonNode(i, null); } else { SonNode next = parent.first; while (next.next != null) { next = next.next; } next.next = new SonNode(i, null); } nodeNums++; return; } } throw new RuntimeException("該樹已滿，無法添加新節點"); } // 判斷樹是否為空 public boolean empty() { // 根結點是否為null return nodes[0] == null; } // 返回根節點 public Node<E> root() { // 返回根節點 return nodes[0]; } // 返回指定節點（非葉子節點）的所有子節點 public List<Node<E>> children(Node parent) { List<Node<E>> list = new ArrayList<Node<E>>(); // 獲取parent節點的第一個子節點 SonNode next = parent.first; // 沿著孩子鏈不斷搜索下一個孩子節點 while (next != null) { // 添加孩子鏈中的節點 list.add(nodes[next.pos]); next = next.next; } return list; } // 返回指定節點（非葉子節點）的第index個子節點 public Node<E> child(Node parent, int index) { // 獲取parent節點的第一個子節點 SonNode next = parent.first; // 沿著孩子鏈不斷搜索下一個孩子節點 for (int i = 0; next != null; i++) { if (index == i) { return nodes[next.pos]; } next = next.next; } return null; } // 返回該樹的深度 public int deep() { // 獲取該樹的深度 return deep(root()); } // 這是一個遞歸方法：每棵子樹的深度為其所有子樹的最大深度 + 1 private int deep(Node node) { if (node.first == null) { return 1; } else { // 記錄其所有子樹的最大深度 int max = 0; SonNode next = node.first; // 沿著孩子鏈不斷搜索下一個孩子節點 while (next != null) { // 獲取以其子節點為根的子樹的深度 int tmp = deep(nodes[next.pos]); if (tmp > max) { max = tmp; } next = next.next; } // 最后，返回其所有子樹的最大深度 + 1 return max + 1; } } // 返回包含指定值得節點 public int pos(Node node) { for (int i = 0; i < treeSize; i++) { // 找到指定節點 if (nodes[i] == node) { return i; } } return -1; }} |
測試類：
|
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
|
package com.ietree.basic.datastructure.tree;import java.util.List;/** * Created by ietree * 2017/4/30 */public class TreeChildTest { public static void main(String[] args) { TreeChild<String> tp = new TreeChild<String>("root"); TreeChild.Node root = tp.root(); System.out.println(root); tp.addNode("節點1", root); tp.addNode("節點2", root); tp.addNode("節點3", root); System.out.println("添加子節點后的根結點：" + root); System.out.println("此樹的深度：" + tp.deep()); // 獲取根節點的所有子節點 List<TreeChild.Node<String>> nodes = tp.children(root); System.out.println("根節點的第一個子節點：" + nodes.get(0)); // 為根節點的第一個子節點新增一個子節點 tp.addNode("節點4", nodes.get(0)); System.out.println("此樹第一個子節點：" + nodes.get(0)); System.out.println("此樹的深度：" + tp.deep()); }} |
程序輸出：
TreeChild$Node[data=root, first=-1]
添加子節點后的根結點：TreeChild$Node[data=root, first=1]
此樹的深度：2
根節點的第一個子節點：TreeChild$Node[data=節點1, first=-1]
此樹第一個子節點：TreeChild$Node[data=節點1, first=4]
此樹的深度：3
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://www.cnblogs.com/Dylansuns/p/6791270.html
