-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathMyBinarySearchTree.java
More file actions
117 lines (102 loc) · 3.1 KB
/
Copy pathMyBinarySearchTree.java
File metadata and controls
117 lines (102 loc) · 3.1 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
public class MyBinarySearchTree {
public TreeNode bRoot;
public TreeNode insert(TreeNode root, int value){
TreeNode newNode = new TreeNode(value);
if(root == null){
root = newNode;
return root;
}else{
TreeNode temp = root;
while(true){
if(value > temp.value){
if(temp.right == null){
temp.right = newNode;
break;
}else{
temp = temp.right;
}
}else{ //value < temp.value
if(temp.left == null){
temp.left = newNode;
break;
}else{
temp = temp.left;
}
}
}
}
return root;
}
public TreeNode removeNode(TreeNode root, int key){
if(root == null){
return null;
}
//B1: Tìm node cần xoá
if(key < root.value){//Đi về phía bên trái
root.left = removeNode(root.left, key);
}else if(key > root.value){//Đi về phía bên phải
root.right = removeNode(root.right, key);
}else{ //key = root.value, xác định được node muốn xoá
//TH 1: deleteNode là node lá
if(root.left == null && root.right == null){
return null;
}
//TH2: deleteNode có 1 node con
if(root.left != null && root.right == null){
return root.left;
}
if(root.left == null && root.right != null){
return root.right;
}
//TH3: Tồn tại 2 node con
TreeNode leftNode = findLeftNode(root.right);
root.value = leftNode.value;
root.right = removeNode(root.right, leftNode.value);
}
return root;
}
public TreeNode findLeftNode(TreeNode root){
if(root == null){
return null;
}
TreeNode leftNode = root;
while (leftNode.left != null) {
leftNode = leftNode.left;
}
return leftNode;
}
//Duyệt tiền thứ tự
public void preOrder(TreeNode root){
if(root == null){
return;
}
//Duyệt gốc
System.out.print(root.value + " \t");
//Duyet bên trái
preOrder(root.left);
//Duyệt bên phải
preOrder(root.right);
}
public void inOrder(TreeNode root){
if(root == null){
return;
}
//Duyệt bên trái
inOrder(root.left);
//Duyệt gốc
System.out.print(root.value + "\t");
//Duyệt bên phải
inOrder(root.right);
}
public void postOrder(TreeNode root){
if(root == null){
return;
}
//Duyệt bên trái
postOrder(root.left);
//Duyệt bên phải
postOrder(root.right);
//Duyệt gốc
System.out.print(root.value + "\t");
}
}