Skip to content

Commit 2f4dc6b

Browse files
byhiegbyhieg
committed
添加根据前序遍历和中序遍历的情况，还原二叉树
1 parent 769ffdd commit 2f4dc6b

File tree

3 files changed

+75
-24
lines changed

3 files changed

+75
-24
lines changed

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

Lines changed: 60 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -17,25 +17,26 @@ public class BinarySearchTree {
1717
private Node root;
1818

1919

20-
public BinarySearchTree(){
20+
public BinarySearchTree() {
2121

2222
}
2323

2424

2525
public BinarySearchTree(int[] nums) {
2626
Node[] nodes = new Node[nums.length];
27-
for (int i = 0 ; i < nums.length;i++) {
27+
for (int i = 0; i < nums.length; i++) {
2828
nodes[i] = new Node(nums[i]);
2929
insert(nodes[i]);
3030
}
3131
}
3232

3333
/**
3434
* 查找指定的元素
35+
*
3536
* @param des
3637
* @return
3738
*/
38-
public Node find(int des){
39+
public Node find(int des) {
3940
if (root == null) {
4041
System.out.println("树是空的");
4142
throw new RuntimeException();
@@ -44,7 +45,7 @@ public Node find(int des){
4445
while (current.data != des) {
4546
if (current.data < des) {
4647
current = current.right;
47-
}else{
48+
} else {
4849
current = current.left;
4950
}
5051
if (current == null) return null;
@@ -55,10 +56,11 @@ public Node find(int des){
5556
/**
5657
* 对BST执行插入操作，采用非递归的形式
5758
* 保证插入后，左节点的值小于根节点的值，根节点的值小于右节点的值
59+
*
5860
* @param node
5961
* @return
6062
*/
61-
public boolean insert(Node node){
63+
public boolean insert(Node node) {
6264
if (root == null) {
6365
root = node;
6466
return true;
@@ -77,7 +79,7 @@ public boolean insert(Node node){
7779
return true;
7880
}
7981
current = current.right;
80-
}else{
82+
} else {
8183
if (current.left == null) {
8284
current.left = node;
8385
return true;
@@ -105,9 +107,10 @@ public void preOrder(Node node) {
105107
/**
106108
* 树的中序遍历，递归实现
107109
* 针对BST，该结果会从小到大输出树
110+
*
108111
* @param node
109112
*/
110-
public void inOrder(Node node){
113+
public void inOrder(Node node) {
111114
if (node.left != null) {
112115
inOrder(node.left);
113116
}
@@ -120,7 +123,7 @@ public void inOrder(Node node){
120123
/**
121124
* 树的后续遍历，递归实现
122125
*/
123-
public void postOrder(Node node){
126+
public void postOrder(Node node) {
124127
if (node.left != null) {
125128
postOrder(node.left);
126129
}
@@ -136,7 +139,6 @@ public void postOrder(Node node){
136139
* 1. 建立一个栈，现将头结点压入栈中。
137140
* 2. 现将每出栈一个节点，打印他的值，然后都要先加入他的右节点，在加入他的左节点。因为栈的后进先出的特性，才能让左边先出。
138141
* 3. 不断重复2，直到栈空
139-
*
140142
*/
141143
public void preOrder2(Node node) {
142144
if (node != null) {
@@ -161,7 +163,7 @@ public void preOrder2(Node node) {
161163
* 2. 出栈一个节点，打印他的值，然后cur = node.right,并不断重复第二步
162164
* 3. 当栈为空，并且cur为空时，停止
163165
*/
164-
public void inorder2(Node node){
166+
public void inorder2(Node node) {
165167
if (node != null) {
166168
Stack<Node> stack = new Stack<>();
167169
Node cur = node;
@@ -170,7 +172,7 @@ public void inorder2(Node node){
170172
cur = stack.pop();
171173
System.out.print(cur.data + "-->");
172174
cur = cur.right;
173-
}else{
175+
} else {
174176
stack.push(cur);
175177
cur = cur.left;
176178
}
@@ -183,6 +185,7 @@ public void inorder2(Node node){
183185
* 1. 树的先续遍历中，是栈存放顺序是根，右节点，左节点。
184186
* 2. 我们可以将其反过来，用栈存放是根，左节点，右节点。然后出栈的时候，将出栈的结果存放到另一个栈里。
185187
* 3. 第二栈里的顺序从上到下就是左节点，右节点，根的顺序。
188+
*
186189
* @param node
187190
*/
188191

@@ -192,7 +195,7 @@ public void postOrder2(Node node) {
192195
Stack<Node> result = new Stack<>();
193196
Node cur = node;
194197
stack.push(cur);
195-
while (!stack.isEmpty()){
198+
while (!stack.isEmpty()) {
196199
Node tmp = stack.pop();
197200
result.push(tmp);
198201
if (tmp.left != null) {
@@ -212,9 +215,10 @@ public void postOrder2(Node node) {
212215

213216
/**
214217
* 得到树中最小的节点
218+
*
215219
* @return
216220
*/
217-
public Node getMinNode(){
221+
public Node getMinNode() {
218222
if (root == null) {
219223
throw new RuntimeException("树为空");
220224
}
@@ -228,9 +232,10 @@ public Node getMinNode(){
228232

229233
/**
230234
* 得到树中最大的节点
235+
*
231236
* @return
232237
*/
233-
public Node getMaxNode(){
238+
public Node getMaxNode() {
234239
if (root == null) {
235240
throw new RuntimeException("树为空");
236241
}
@@ -242,12 +247,51 @@ public Node getMaxNode(){
242247
return current;
243248
}
244249

245-
public static class Node{
250+
251+
public void getTree(int[] preOrders, int[] inOrders,boolean isLeft) {
252+
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);
260+
int[] left = new int[index];
261+
int[] preLeft = new int[index];
262+
if (left.length != 0) {
263+
for (int i = 0; i < index; i++) {
264+
left[i] = inOrders[i];
265+
preLeft[i] = preOrders[i + 1];
266+
}
267+
}
268+
int size = inOrders.length - index - 1;
269+
int[] right = new int[inOrders.length - index - 1];
270+
int[] preRight = new int[size];
271+
if (right.length != 0) {
272+
for (int i = 0; i < size; i++) {
273+
right[i] = inOrders[i + index + 1];
274+
preRight[i] = preOrders[preLeft.length + i + 1];
275+
}
276+
}
277+
278+
if (preLeft.length != 0) {
279+
getTree(preLeft, left,true);
280+
}
281+
282+
if (preRight.length != 0) {
283+
getTree(preRight, right,false);
284+
}
285+
System.out.println();
286+
287+
}
288+
289+
public static class Node {
246290
public int data;
247291
public Node left;
248292
public Node right;
249293

250-
public Node(int data){
294+
public Node(int data) {
251295
this.data = data;
252296
}
253297
}

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -14,12 +14,12 @@ public class Find {
1414
* @param nums int型数组，要求有序
1515
* @return 找到，返回下标，没找到，返回-1
1616
*/
17-
public int binarySerachFind(int[] nums,int des) {
17+
public int binarySearchFind(int[] nums,int des) {
1818
int length = nums.length;
1919
int low = 0;
2020
int high = length - 1;
21-
while (low < high) {
22-
int mid = low + (high - low) / 2;
21+
while (low <= high) {
22+
int mid = (low + high) / 2;
2323
if (nums[mid] == des) {
2424
return mid;
2525
} else if (nums[mid] < des) {

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

Lines changed: 12 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
11
package cn.byhieg.collectiontutorialtest;
22

33
import cn.byhieg.algorithmtutorial.BinarySearchTree;
4-
import com.sun.tools.internal.ws.wsdl.document.soap.SOAPUse;
54
import junit.framework.TestCase;
65
import org.junit.Assert;
76

@@ -10,11 +9,12 @@
109
* Mail to byhieg@gmail.com
1110
*/
1211
public class BinarySearchTreeTest extends TestCase {
13-
int [] nums;
12+
int[] nums;
1413
BinarySearchTree tree;
14+
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[]{10, 6, 2, 8, 7, 3, 4, 1};
1818
tree = new BinarySearchTree(nums);
1919
}
2020

@@ -43,11 +43,18 @@ public void testPostOrder() throws Exception {
4343
System.out.println();
4444
}
4545

46+
public void testGetTree() throws Exception {
47+
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);
51+
}
52+
4653
public void testGetMaxData() throws Exception {
47-
// Assert.assertEquals(12,tree.getMaxNode().data);
54+
Assert.assertEquals(10,tree.getMaxNode().data);
4855
}
4956

5057
public void testGetMinData() throws Exception {
51-
// Assert.assertEquals(1,tree.getMinNode().data);
58+
Assert.assertEquals(1,tree.getMinNode().data);
5259
}
5360
}

0 commit comments

Comments
 (0)