二叉树的分类（按存储结构）
树的分类（按存储结构）
顺序存储（用数组表示（静态二叉树））
链式存储
一些特别的二叉根：
完全二叉树，平衡二叉树（AVL），线索二叉树，三叉的（带父亲的指针）
二叉搜索树或者叫二叉 查找树（BST）
所用二叉树如下图所示：
二叉树的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
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
|
class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false; private TreeNode leftChild = null; private TreeNode rightChild = null; public TreeNode(){ } public TreeNode(int key, String data){ this.key = key; this.data = data; this.leftChild = null; this.rightChild = null; } public int getKey() { return key; } public void setKey(int key) { this.key = key; } public String getData() { return data; } public void setData(String data) { this.data = data; } public TreeNode getLeftChild() { return leftChild; } public void setLeftChild(TreeNode leftChild) { this.leftChild = leftChild; } public TreeNode getRightChild() { return rightChild; } public void setRightChild(TreeNode rightChild) { this.rightChild = rightChild; } public boolean isVisted() { return isVisted; } public void setVisted(boolean isVisted) { this.isVisted = isVisted; }}public class BinaryTree { private TreeNode root = null; public BinaryTree() { root = new TreeNode(1, "rootNode(A)"); } public void createBinTree(TreeNode root){ //手动的创建（结构如图所示） TreeNode newNodeB = new TreeNode(2,"B"); TreeNode newNodeC = new TreeNode(3,"C"); TreeNode newNodeD = new TreeNode(4,"D"); TreeNode newNodeE = new TreeNode(5,"E"); TreeNode newNodeF = new TreeNode(6,"F"); root.setLeftChild(newNodeB); root.setRightChild(newNodeC); root.getLeftChild().setLeftChild(newNodeD); root.getLeftChild().setRightChild(newNodeE); root.getRightChild().setRightChild(newNodeF); } public boolean IsEmpty() { // 判二叉树空否 return root == null; } public int Height() { // 求树高度 return Height(root); } public int Height(TreeNode subTree) { if (subTree == null) return 0; //递归结束：空树高度为0 else { int i = Height(subTree.getLeftChild()); int j = Height(subTree.getRightChild()); return (i < j) ? j + 1 : i + 1; } } public int Size() { // 求结点数 return Size(root); } public int Size(TreeNode subTree) { if (subTree == null) return 0; else { return 1 + Size(subTree.getLeftChild()) + Size(subTree.getRightChild()); } } public TreeNode Parent(TreeNode element) { //返回双亲结点 return (root == null || root == element) ? null : Parent(root, element); } public TreeNode Parent(TreeNode subTree, TreeNode element) { if (subTree == null) return null; if (subTree.getLeftChild() == element || subTree.getRightChild() == element) //找到, 返回父结点地址 return subTree; TreeNode p; //先在左子树中找，如果左子树中没有找到，才到右子树去找 if ((p = Parent(subTree.getLeftChild(), element)) != null) //递归在左子树中搜索 return p; else //递归在左子树中搜索 return Parent(subTree.getRightChild(), element); } public TreeNode LeftChild(TreeNode element) { //返回左子树 return (element != null) ? element.getLeftChild() : null; } public TreeNode RightChild(TreeNode element) { //返回右子树 return (element != null) ? element.getRightChild() : null; } public TreeNode getRoot() { //取得根结点 return root; } public void destroy(TreeNode subTree) { //私有函数: 删除根为subTree的子树 if (subTree != null) { destroy(subTree.getLeftChild()); //删除左子树 destroy(subTree.getRightChild()); //删除右子树 //delete subTree; //删除根结点 subTree = null; } } public void Traverse(TreeNode subTree) { System.out.println("key:" + subTree.getKey() + "--name:" + subTree.getData()); Traverse(subTree.getLeftChild()); Traverse(subTree.getRightChild()); } public void PreOrder(TreeNode subTree) { //先根 if (subTree != null) { visted(subTree); PreOrder(subTree.getLeftChild()); PreOrder(subTree.getRightChild()); } } public void InOrder(TreeNode subTree) { //中根 if (subTree != null) { InOrder(subTree.getLeftChild()); visted(subTree); InOrder(subTree.getRightChild()); } } public void PostOrder(TreeNode subTree) { //后根 if (subTree != null) { PostOrder(subTree.getLeftChild()); PostOrder(subTree.getRightChild()); visted(subTree); } } public void LevelOrder(TreeNode subTree) { //水平遍边 } public boolean Insert(TreeNode element){ //插入 return true; } public boolean Find(TreeNode element){ //查找 return true; } public void visted(TreeNode subTree) { subTree.setVisted(true); System.out.println("key:" + subTree.getKey() + "--name:" + subTree.getData()); } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.createBinTree(bt.root); System.out.println("the size of the tree is " + bt.Size()); System.out.println("the height of the tree is " + bt.Height()); System.out.println("*******先根(前序)[ABDECF]遍历*****************"); bt.PreOrder(bt.root); System.out.println("*******中根(中序)[DBEACF]遍历*****************"); bt.InOrder(bt.root); System.out.println("*******后根(后序)[DEBFCA]遍历*****************"); bt.PostOrder(bt.root); }} |
结果输出：
the size of the tree is 6
the height of the tree is 3
*******先根(前序)[ABDECF]遍历*****************
key:1--name:rootNode(A)
key:2--name:B
key:4--name:D
key:5--name:E
key:3--name:C
key:6--name:F
*******中根(中序)[DBEACF]遍历*****************
key:4--name:D
key:2--name:B
key:5--name:E
key:1--name:rootNode(A)
key:3--name:C
key:6--name:F
*******后根(后序)[DEBFCA]遍历*****************
key:4--name:D
key:5--name:E
key:2--name:B
key:6--name:F
key:3--name:C
key:1--name:rootNode(A)
希望本文对学习JAVA程序设计的同学有所帮助。
