-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBST.java
More file actions
79 lines (75 loc) · 1.96 KB
/
BST.java
File metadata and controls
79 lines (75 loc) · 1.96 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
package com.al;
class BST
{
class Node
{
private Node left,right;
private int val;
Node(int n)
{
this.val = n;
}
}
void inOrder(Node node){
if (node == null)
return;
inOrder(node.left);
System.out.println("val:" + node.val);
inOrder(node.right);
}
void preOrder(Node node){
if (node == null)
return;
System.out.println("val:" + node.val);
preOrder(node.left);
preOrder(node.right);
}
void insert(Node node, int n){
if (node ==null)
return;
if (n < node.val){
if(node.left == null){
node.left = new Node(n);
} else {
insert(node.left,n);
}
} else {
if(node.right == null){
node.right = new Node(n);
} else {
insert(node.right,n);
}
}
}
void delete(Node node,int data) throws Exception {
// find node p
Node p = node, pp = null;
while (p != null && p.val != data){
pp = p;
if (data > p.val) p = p.right;
else p = p.left;
}
// not found
if (p == null) return;
System.out.println("=====find: "+ data);
// found two child
if (p.left != null && p.right != null) {
Node minP = p.right, minPP = p;
while(minP.left != null){
minPP = minP;
minP = minP.left;
}
p.val = minP.val;
p = minP;
pp = minPP;
}
// single child or null child
Node child;
if (p.left != null) child = p.left;
else if (p.right != null) child = p.right;
else child = null;
if (pp == null) throw new Exception("del root node");
else if (pp.left == p) pp.left = child;
else pp.right = child;
}
}