-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathTreeTest.java
More file actions
213 lines (153 loc) · 5.14 KB
/
TreeTest.java
File metadata and controls
213 lines (153 loc) · 5.14 KB
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
package tree;
/**
* Created by ozc on 2018/3/20.
*
* @author ozc
* @version 1.0
*/
public class TreeTest {
public static void main(String[] args) {
/*
//根节点-->10
TreeNode treeNode1 = new TreeNode(10);
//左孩子-->9
TreeNode treeNode2 = new TreeNode(9);
//右孩子-->20
TreeNode treeNode3 = new TreeNode(20);
//20的左孩子-->15
TreeNode treeNode4 = new TreeNode(15);
//20的右孩子-->35
TreeNode treeNode5 = new TreeNode(35);
//根节点的左右孩子
treeNode1.setLefTreeNode(treeNode2);
treeNode1.setRightNode(treeNode3);
//20节点的左右孩子
treeNode3.setLefTreeNode(treeNode4);
treeNode3.setRightNode(treeNode5);
preTraverseBTree(treeNode1);*/
int[] arrays = {3, 2, 7, 4, 5};
//int[] arrays2 = {6, 3, 8, 2, 5, 1, 7};
//动态创建树
TreeRoot root = new TreeRoot();
for (int value : arrays) {
createTree(root, value);
}
//先序遍历树
preTraverseBTree(root.getTreeRoot());
System.out.println("---------------公众号：Java3y");
//中序遍历树
inTraverseBTree(root.getTreeRoot());
System.out.println("---------------公众号：Java3y");
System.out.println("树的深度是：" + getHeight(root.getTreeRoot()));
System.out.println("树的最大值是：" + getMax(root.getTreeRoot()));
}
/**
* 动态创建二叉查找树
*
* @param treeRoot 根节点
* @param value 节点的值
*/
public static void createTree(TreeRoot treeRoot, int value) {
//如果树根为空(第一次访问)，将第一个值作为根节点
if (treeRoot.getTreeRoot() == null) {
TreeNode treeNode = new TreeNode(value);
treeRoot.setTreeRoot(treeNode);
} else {
//当前树根
TreeNode tempRoot = treeRoot.getTreeRoot();
while (tempRoot != null) {
//当前值大于根值，往右边走
if (value > tempRoot.getValue()) {
//右边没有树根，那就直接插入
if (tempRoot.getRightNode() == null) {
tempRoot.setRightNode(new TreeNode(value));
return;
} else {
//如果右边有树根，到右边的树根去
tempRoot = tempRoot.getRightNode();
}
} else {
//左没有树根，那就直接插入
if (tempRoot.getLefTreeNode() == null) {
tempRoot.setLefTreeNode(new TreeNode(value));
return;
} else {
//如果左有树根，到左边的树根去
tempRoot = tempRoot.getLefTreeNode();
}
}
}
}
}
public static int getHeight(TreeNode treeNode) {
if (treeNode == null) {
return 0;
} else {
//左边的子树深度
int left = getHeight(treeNode.getLefTreeNode());
//右边的子树深度
int right = getHeight(treeNode.getRightNode());
int max = left;
if (right > max) {
max = right;
}
return max + 1;
}
}
/**
* 找出树的最大值
*
* @param rootTreeNode
*/
public static int getMax(TreeNode rootTreeNode) {
if (rootTreeNode == null) {
return -1;
} else {
//找出左边的最大值
int left = getMax(rootTreeNode.getLefTreeNode());
//找出右边的最大值
int right = getMax(rootTreeNode.getRightNode());
//与当前根节点比较
int currentRootValue = rootTreeNode.getValue();
//假设左边的最大
int max = left;
if (right > max) {
max = right;
}
if (currentRootValue > max) {
max = currentRootValue;
}
return max ;
}
}
/**
* 中序遍历
*
* @param rootTreeNode 根节点
*/
public static void inTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//访问根节点
System.out.println(rootTreeNode.getValue());
//访问左节点
inTraverseBTree(rootTreeNode.getLefTreeNode());
//访问右节点
inTraverseBTree(rootTreeNode.getRightNode());
}
}
/**
* 先序遍历
*
* @param rootTreeNode 根节点
*/
public static void preTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//访问左节点
preTraverseBTree(rootTreeNode.getLefTreeNode());
//访问根节点
System.out.println(rootTreeNode.getValue());
//访问右节点
preTraverseBTree(rootTreeNode.getRightNode());
}
}
}