java中樹的存儲結構實現 一、樹 樹與線性表、棧、隊列等線性結構不同,樹是一...節點與節點之間的父子關系,可以為每個節點增加一個parent域,用以記錄該節點的父點
樹是一種抽象數據類型（adt）或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>0）個有限節點組成一個具有層次關系的集合。把 它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
樹定義和基本術語
定義
樹(tree)是n(n≥0)個結點的有限集t，并且當n＞0時滿足下列條件：
（1）有且僅有一個特定的稱為根(root)的結點；
（2）當n＞1時，其余結點可以劃分為m(m＞0)個互不相交的有限集t1、t2、…、tm，每個集ti(1≤i≤m)均為樹，且稱為樹t的子樹(subtree)。
特別地，不含任何結點(即n＝0)的樹，稱為空樹。
如下就是一棵樹的結構：
基本術語
結點：存儲數據元素和指向子樹的鏈接，由數據元素和構造數據元素之間關系的引用組成。
孩子結點：樹中一個結點的子樹的根結點稱為這個結點的孩子結點，如圖1中的a的孩子結點有b、c、d
雙親結點：樹中某個結點有孩子結點(即該結點的度不為0)，該結點稱為它孩子結點的雙親結點，也叫前驅結點。雙親結點和孩子結點是相互的，如圖1中，a的孩子結點是b、c、d，b、c、d的雙親結點是a。
兄弟結點：具有相同雙親結點(即同一個前驅)的結點稱為兄弟結點，如圖1中b、b、d為兄弟結點。
結點的度：結點所有子樹的個數稱為該結點的度，如圖1，a的度為3，b的度為2.
樹的度：樹中所有結點的度的最大值稱為樹的度，如圖1的度為3.
葉子結點：度為0的結點稱為葉子結點，也叫終端結點。如圖1的k、l、f、g、m、i、j
分支結點：度不為0的結點稱為分支結點，也叫非終端結點。如圖1的a、b、c、d、e、h
結點的層次：從根結點到樹中某結點所經路徑的分支數稱為該結點的層次。根結點的層次一般為1(也可以自己定義為0)，這樣，其它結點的層次是其雙親結點的層次加1.
樹的深度：樹中所有結點的層次的最大值稱為該樹的深度(也就是最下面那個結點的層次)。
有序樹和無序樹：樹中任意一個結點的各子樹按從左到右是有序的，稱為有序樹，否則稱為無序樹。
樹的抽象數據類型描述
數據元素：具有相同特性的數據元素的集合。
結構關系：樹中數據元素間的結構關系由樹的定義確定。
基本操作：樹的主要操作有
（1）創建樹inttree(&t)
創建1個空樹t。
（2）銷毀樹destroytree(&t)
（3）構造樹creattree(&t，deinition)
（4）置空樹cleartree(&t)
將樹t置為空樹。
（5）判空樹treeempty(t)
（6）求樹的深度treedepth(t)
（7）獲得樹根root(t)
（8）獲取結點value(t，cur_e，&e)
將樹中結點cur_e存入e單元中。
（9）數據賦值assign(t，cur_e，value)
將結點value，賦值于樹t的結點cur_e中。
（10）獲得雙親parent(t，cur_e)
返回樹t中結點cur_e的雙親結點。
（11）獲得最左孩子leftchild(t，cur_e)
返回樹t中結點cur_e的最左孩子。
（12）獲得右兄弟rightsibling(t，cur_e)
返回樹t中結點cur_e的右兄弟。
（13）插入子樹insertchild(&t，&p，i，c)
將樹c插入到樹t中p指向結點的第i個子樹之前。
（14）刪除子樹deletechild(&t，&p，i)
刪除樹t中p指向結點的第i個子樹。
（15）遍歷樹traversetree(t，visit())
樹的實現
樹是一種遞歸結構，表示方式一般有孩子表示法和孩子兄弟表示法兩種。樹實現方式有很多種、有可以由廣義表的遞歸實現，也可以有二叉樹實現，其中最常見的是將樹用孩子兄弟表示法轉化成二叉樹來實現。
下面以孩子表示法為例講一下樹的實現：
樹的定義和實現
|
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
|
package datastructure.tree;import java.util.arraylist;import java.util.arrays;import java.util.linkedlist;import java.util.list;/** * 樹的定義和實現 * @author administrator * */public class tree { private object data; private list<tree> childs; public tree(){ data = null; childs = new arraylist(); childs.clear(); } public tree(object data) { this.data = data; childs = new arraylist(); childs.clear(); } /** * 添加子樹 * @param tree 子樹 */ public void addnode(tree tree) { childs.add(tree); } /** * 置空樹 */ public void cleartree() { data = null; childs.clear(); } /** * 求樹的深度 * 這方法還有點問題，有待完善 * @return 樹的深度 */ public int dept() { return dept(this); } /** * 求樹的深度 * 這方法還有點問題，有待完善 * @param tree * @return */ private int dept(tree tree) { if(tree.isempty()) { return 0; } else if(tree.isleaf()) { return 1; } else { int n = childs.size(); int[] a = new int[n]; for (int i=0; i<n; i++) { if(childs.get(i).isempty()) { a[i] = 0+1; } else { a[i] = dept(childs.get(i)) + 1; } } arrays.sort(a); return a[n-1]; } } /** * 返回遞i個子樹 * @param i * @return */ public tree getchild(int i) { return childs.get(i); } /** * 求第一個孩子 結點 * @return */ public tree getfirstchild() { return childs.get(0); } /** * 求最后 一個孩子結點 * @return */ public tree getlastchild() { return childs.get(childs.size()-1); } public list<tree> getchilds() { return childs; } /** * 獲得根結點的數據 * @return */ public object getrootdata() { return data; } /** * 判斷是否為空樹 * @return 如果為空，返回true,否則返回false */ public boolean isempty() { if(childs.isempty() && data == null) return true; return false; } /** * 判斷是否為葉子結點 * @return */ public boolean isleaf() { if(childs.isempty()) return true; return false; } /** * 獲得樹根 * @return 樹的根 */ public tree root() { return this; } /** * 設置根結點的數據 */ public void setrootdata(object data) { this.data = data; } /** * 求結點數 * 這方法還有點問題，有待完善 * @return 結點的個數 */ public int size() { return size(this); } /** * 求結點數 * 這方法還有點問題，有待完善 * @param tree * @return */ private int size(tree tree) { if(tree.isempty()) { return 0; } else if(tree.isleaf()) { return 1; } else { int count = 1; int n = childs.size(); for (int i=0; i<n; i++) { if(!childs.get(i).isempty()) { count += size(childs.get(i)); } } return count; } }} |
樹的遍歷
樹的遍歷有兩種
前根遍歷
（1）.訪問根結點；
（2）.按照從左到右的次序行根遍歷根結點的第一棵子樹；
后根遍歷
（1）.按照從左到右的次序行根遍歷根結點的第一棵子樹；
（2）.訪問根結點；
visit.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
package datastructure.tree;import datastructure.tree.btree.btree;/** * 對結點進行操作的接口,規定樹的遍歷的類必須實現這個接口 * @author administrator * */public interface visit { /** * 對結點進行某種操作 * @param btree 樹的結點 */ public void visit(btree btree);} |
order.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
34
35
36
37
38
39
40
|
package datastructure.tree;import java.util.list;/** * 樹的遍歷 * @author administrator * */public class order { /** * 先根遍歷 * @param root 要的根結點 */ public void preorder(tree root) { if(!root.isempty()) { visit(root); for (tree child : root.getchilds()) { if(child != null) { preorder(child); } } } } /** * 后根遍歷 * @param root 樹的根結點 */ public void postorder(tree root) { if(!root.isempty()) { for (tree child : root.getchilds()) { if(child != null) { preorder(child); } } visit(root); } } public void visit(tree tree) { system.out.print("\t" + tree.getrootdata()); }} |
測試：
要遍歷的樹如下：
|
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
|
package datastructure.tree;import java.util.iterator;import java.util.scanner;public class treetest { /** * @param args */ public static void main(string[] args) { tree root = new tree("a"); root.addnode(new tree("b")); root.addnode(new tree("c")); root.addnode(new tree("d")); tree t = null; t = root.getchild(0); t.addnode(new tree("l")); t.addnode(new tree("e")); t = root.getchild(1); t.addnode(new tree("f")); t = root.getchild(2); t.addnode(new tree("i")); t.addnode(new tree("h")); t = t.getfirstchild(); t.addnode(new tree("l")); system.out.println("first node:" + root.getrootdata()); //system.out.println("size:" + root.size()); //system.out.println("dept:" + root.dept()); system.out.println("is left:" + root.isleaf()); system.out.println("data:" + root.getrootdata()); order order = new order(); system.out.println("前根遍歷："); order.preorder(root); system.out.println("\n后根遍歷："); order.postorder(root); }} |
結果：
first node:a
is left:false
data:a
前根遍歷：
a bl e c f di l h
后根遍歷：
b le c f d il h a
結束語：
以上就是本文關于java數據結構之樹基本概念解析及代碼示例的全部內容，希望對大家有所幫助。如有不足之處，歡迎留言指出。
原文鏈接：https://www.cnblogs.com/web424/p/6911892.html
