Skip to content

Commit 2d5db31

Browse files
byhiegbyhieg
committed
修改从前序遍历和中序遍历得到树的代码
1 parent 2f4dc6b commit 2d5db31

File tree

4 files changed

+85
-45
lines changed

4 files changed

+85
-45
lines changed

‎src/main/java/cn/byhieg/algorithmtutorial/BinarySearchTree.java‎

Lines changed: 47 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,8 @@
55
* Mail to byhieg@gmail.com
66
*/
77

8+
import java.util.LinkedList;
9+
import java.util.Queue;
810
import java.util.Stack;
911

1012
/**
@@ -212,6 +214,26 @@ public void postOrder2(Node node) {
212214
}
213215
}
214216

217+
/**
218+
* 树的层次遍历，类似于图的BFS
219+
* @param root
220+
*/
221+
public void levelRead(Node root) {
222+
if (root == null) return;
223+
Queue<Node> queue = new LinkedList<>();
224+
queue.offer(root);
225+
while (!queue.isEmpty()) {
226+
Node current = queue.poll();
227+
System.out.print(current.data + "-->");
228+
if (current.left != null) {
229+
queue.offer(current.left);
230+
}
231+
if (current.right != null) {
232+
queue.offer(current.right);
233+
}
234+
}
235+
}
236+
215237

216238
/**
217239
* 得到树中最小的节点
@@ -248,23 +270,27 @@ public Node getMaxNode() {
248270
}
249271

250272

251-
public void getTree(int[] preOrders, int[] inOrders,boolean isLeft) {
273+
public void getTree(int[] preOrders, int[] inOrders,Node r) {
252274
int root = preOrders[0];
253-
if (isLeft) {
254-
System.out.println("左" + root);
255-
}else{
256-
System.out.println("右" + root);
257-
}
258-
259-
int index = new Find().binarySearchFind(inOrders, root);
275+
// if (isLeft) {
276+
// System.out.println("左" + root);
277+
// }else{
278+
// System.out.println("右" + root);
279+
// }
280+
r.data = root;
281+
int index = findIndex(inOrders, root);
260282
int[] left = new int[index];
261283
int[] preLeft = new int[index];
262284
if (left.length != 0) {
263285
for (int i = 0; i < index; i++) {
264286
left[i] = inOrders[i];
265287
preLeft[i] = preOrders[i + 1];
266288
}
289+
Node node = new Node(preLeft[0]);
290+
r.left = node;
267291
}
292+
293+
268294
int size = inOrders.length - index - 1;
269295
int[] right = new int[inOrders.length - index - 1];
270296
int[] preRight = new int[size];
@@ -273,17 +299,17 @@ public void getTree(int[] preOrders, int[] inOrders,boolean isLeft) {
273299
right[i] = inOrders[i + index + 1];
274300
preRight[i] = preOrders[preLeft.length + i + 1];
275301
}
302+
Node node = new Node(preRight[0]);
303+
r.right = node;
276304
}
277305

278306
if (preLeft.length != 0) {
279-
getTree(preLeft, left,true);
307+
getTree(preLeft, left,r.left);
280308
}
281309

282310
if (preRight.length != 0) {
283-
getTree(preRight, right,false);
311+
getTree(preRight, right,r.right);
284312
}
285-
System.out.println();
286-
287313
}
288314

289315
public static class Node {
@@ -299,4 +325,13 @@ public Node(int data) {
299325
public Node getRoot() {
300326
return root;
301327
}
328+
329+
private int findIndex(int[] nums, int target) {
330+
for (int i = 0 ; i < nums.length;i++) {
331+
if (nums[i] == target) {
332+
return i;
333+
}
334+
}
335+
return -1;
336+
}
302337
}

‎src/main/java/cn/byhieg/algorithmtutorial/Sort.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -250,7 +250,8 @@ public void sink(int nums[], int i,int n) {
250250
nums[i] = nums[son];
251251
nums[son] = temp;
252252
i = son;
253-
} else {
253+
son = 2 * i + 1;
254+
}else{
254255
break;
255256
}
256257
}

‎src/test/java/cn/byhieg/algorithmtutorialtest/SortTest.java‎

Lines changed: 21 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -19,27 +19,27 @@ public void tearDown() throws Exception {
1919
System.out.print(nums[i] + " ");
2020
}
2121
}
22-
23-
public void testChooseSort() throws Exception {
24-
new Sort().chooseSort(nums);
25-
}
26-
27-
28-
public void testInsertDirectlySort() throws Exception {
29-
new Sort().insertDirectlySort(nums);
30-
}
31-
32-
public void testInsertBinarySort() throws Exception {
33-
new Sort().insertBinarySort(nums);
34-
}
35-
36-
public void testBubbleSort() throws Exception {
37-
new Sort().bubbleSort2(nums);
38-
}
39-
40-
public void testQuickSort() throws Exception {
41-
new Sort().quickSort(nums);
42-
}
22+
//
23+
// public void testChooseSort() throws Exception {
24+
// new Sort().chooseSort(nums);
25+
// }
26+
//
27+
//
28+
// public void testInsertDirectlySort() throws Exception {
29+
// new Sort().insertDirectlySort(nums);
30+
// }
31+
//
32+
// public void testInsertBinarySort() throws Exception {
33+
// new Sort().insertBinarySort(nums);
34+
// }
35+
//
36+
// public void testBubbleSort() throws Exception {
37+
// new Sort().bubbleSort2(nums);
38+
// }
39+
//
40+
// public void testQuickSort() throws Exception {
41+
// new Sort().quickSort(nums);
42+
// }
4343

4444
public void testHeapSort() throws Exception {
4545
new Sort().heapSort(nums);

‎src/test/java/cn/byhieg/collectiontutorialtest/BinarySearchTreeTest.java‎

Lines changed: 15 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -14,11 +14,13 @@ public class BinarySearchTreeTest extends TestCase {
1414

1515
public void setUp() throws Exception {
1616
super.setUp();
17-
nums = new int[]{10, 6, 2, 8, 7, 3, 4, 1};
17+
nums = new int[]{1,2,3,4,5};
1818
tree = new BinarySearchTree(nums);
1919
}
2020

2121
public void tearDown() throws Exception {
22+
BinarySearchTree.Node node = new BinarySearchTree.Node(10);
23+
tree.levelRead(node);
2224
}
2325

2426

@@ -45,16 +47,18 @@ public void testPostOrder() throws Exception {
4547

4648
public void testGetTree() throws Exception {
4749
System.out.println("树");
48-
int[] pre = new int[]{10, 6, 2, 1, 3, 4, 8, 7};
49-
int[] in = new int[]{1, 2, 3, 4, 6, 7, 8, 10};
50-
tree.getTree(pre, in,true);
50+
int[] pre = new int[]{1,2,4,5,3};
51+
int[] in = new int[]{4,2,5,1,3};
52+
BinarySearchTree.Node node = new BinarySearchTree.Node(1);
53+
tree.getTree(pre, in,node);
54+
tree.levelRead(node);
5155
}
5256

53-
public void testGetMaxData() throws Exception {
54-
Assert.assertEquals(10,tree.getMaxNode().data);
55-
}
56-
57-
public void testGetMinData() throws Exception {
58-
Assert.assertEquals(1,tree.getMinNode().data);
59-
}
57+
// public void testGetMaxData() throws Exception {
58+
// Assert.assertEquals(10,tree.getMaxNode().data);
59+
// }
60+
//
61+
// public void testGetMinData() throws Exception {
62+
// Assert.assertEquals(1,tree.getMinNode().data);
63+
// }
6064
}

0 commit comments

Comments
 (0)