Skip to content

Commit 15ca6a1

Browse files
author
cfdcoder
committed
update the node deletion operation for binary search tree
1 parent ea9d146 commit 15ca6a1

File tree

101 files changed

+20603
-1655
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

101 files changed

+20603
-1655
lines changed

‎.metadata/.plugins/org.eclipse.core.resources/.history/10/7033608a3db100151d15c07ec223227e

Lines changed: 187 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,187 @@
1+
package study;
2+
/**
3+
* this is the simple implementation of binary search tree:
4+
* in-order traverse, post-order traverse, pre-order traverse
5+
* add node
6+
* delete node
7+
* */
8+
public class BinarySearchTree {
9+
Node root;
10+
11+
//add a node to the binary search tree
12+
public void addNewNode(int key, String data){
13+
Node newNode=new Node(key, data);
14+
if(root==null){
15+
root=newNode;
16+
}else{
17+
Node focusNode=root;
18+
Node parent;
19+
while(true){
20+
parent=focusNode;//set the parent node to the root as start point
21+
if(key<focusNode.key){
22+
focusNode=focusNode.leftChild;
23+
if(focusNode==null){//no left child there
24+
parent.leftChild=newNode;// add newnode tobe the leftchild of the parent
25+
return;
26+
}
27+
}else{
28+
focusNode=focusNode.rightChild;
29+
if(focusNode==null){//no right child there
30+
parent.rightChild=newNode;// add newnode tobe the rightchild of the parent
31+
return;
32+
}
33+
}
34+
}
35+
}
36+
}
37+
38+
//inorder traverse order: left, parent, right
39+
public void inOrderTraverse(Node focusNode){
40+
if(focusNode!=null){
41+
inOrderTraverse(focusNode.leftChild);
42+
System.out.println(focusNode);
43+
inOrderTraverse(focusNode.rightChild);
44+
}
45+
}
46+
47+
//preorder traverse order: parent, left, right
48+
public void preOrderTraverse(Node focusNode){
49+
if(focusNode!=null){
50+
System.out.println(focusNode);
51+
preOrderTraverse(focusNode.leftChild);
52+
preOrderTraverse(focusNode.rightChild);
53+
}
54+
}
55+
56+
//postorder traverse order: left, right, parent,
57+
public void postOrderTraverse(Node focusNode){
58+
if(focusNode!=null){
59+
60+
postOrderTraverse(focusNode.leftChild);
61+
postOrderTraverse(focusNode.rightChild);
62+
System.out.println(focusNode);
63+
}
64+
}
65+
66+
//find a node
67+
public Node findNode(int key){
68+
Node focusNode=root;
69+
while(focusNode.key!=key){
70+
if(key<focusNode.key){
71+
focusNode=focusNode.leftChild;
72+
}else{
73+
focusNode=focusNode.rightChild;
74+
}
75+
if(focusNode==null) return null;
76+
}
77+
return focusNode;
78+
}
79+
80+
//delete a node
81+
public boolean removeNode(int key){
82+
Node focusNode=root;
83+
Node parent =root;
84+
boolean isItLeftChild=true;
85+
while(focusNode.key!=key){
86+
parent=focusNode;
87+
if(key<focusNode.key){
88+
isItLeftChild=true;
89+
focusNode=focusNode.leftChild;
90+
}else{
91+
isItLeftChild=false;
92+
focusNode=focusNode.rightChild;
93+
}
94+
95+
if(focusNode==null) return false;
96+
}
97+
98+
if(focusNode.leftChild==null && focusNode.rightChild==null){
99+
if(focusNode==root) root=null;
100+
else if(isItLeftChild) parent.leftChild=null;
101+
else parent.rightChild=null;
102+
}
103+
else if(focusNode.rightChild==null){
104+
if(focusNode==root) root=focusNode.leftChild;
105+
else if(isItLeftChild) parent.leftChild=focusNode.leftChild;
106+
else parent.rightChild=focusNode.leftChild;
107+
}
108+
else if(focusNode.leftChild==null){
109+
if(focusNode==root) root=focusNode.rightChild;
110+
else if(isItLeftChild) parent.leftChild=focusNode.rightChild;
111+
else parent.rightChild=focusNode.leftChild;
112+
}
113+
else{
114+
Node replacement =getReplacementNode(focusNode);
115+
if(focusNode==root) root=replacement;
116+
else if(isItLeftChild)
117+
parent.leftChild=replacement;
118+
else
119+
parent.rightChild=replacement;
120+
121+
replacement.leftChild=focusNode.leftChild;
122+
}
123+
124+
return true;
125+
126+
}
127+
128+
public Node getReplacementNode(Node replacedNode){
129+
Node replacementParent=replacedNode;
130+
Node replacement =replacedNode;
131+
Node focusNode=replacedNode.rightChild;
132+
while(focusNode!=null){
133+
replacementParent=replacement;
134+
replacement=focusNode;
135+
focusNode=focusNode.leftChild;
136+
}
137+
if(replacement!=replacedNode.rightChild){
138+
replacementParent.leftChild=replacement.rightChild;
139+
replacement.rightChild=replacedNode.rightChild;
140+
}
141+
return replacement;
142+
}
143+
144+
public static void main(String[] args) {
145+
// TODO Auto-generated method stub
146+
BinarySearchTree tree=new BinarySearchTree();
147+
148+
//add new node
149+
tree.addNewNode(1, "Boss");
150+
tree.addNewNode(2, "President");
151+
tree.addNewNode(3, "Head");
152+
tree.addNewNode(4, "Manager");
153+
tree.addNewNode(5, "Secretary");
154+
tree.addNewNode(6, "Salesman");
155+
156+
//check traverse implementation
157+
//tree.inOrderTraverse(tree.root);
158+
//tree.preOrderTraverse(tree.root);
159+
tree.postOrderTraverse(tree.root);
160+
161+
//System.out.println("search data with key 3");
162+
//System.out.println(tree.findNode(3));
163+
164+
System.out.println("remove data with key 3");
165+
System.out.println(tree.removeNode(3));
166+
tree.postOrderTraverse(tree.root);
167+
}
168+
169+
}
170+
171+
//define the nodes in the binary search tree
172+
class Node{
173+
int key;
174+
String data;
175+
176+
Node leftChild;
177+
Node rightChild;
178+
179+
Node(int key, String data){
180+
this.key=key;
181+
this.data=data;
182+
}
183+
184+
public String toString(){
185+
return this.data+" has a key "+ this.key;
186+
}
187+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/12/10ff5fca5ab100151d15c07ec223227e

Lines changed: 199 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,199 @@
1+
package study;
2+
/**
3+
* this is the simple implementation of binary search tree:
4+
* in-order traverse, post-order traverse, pre-order traverse
5+
* add node
6+
* delete node
7+
* */
8+
public class BinarySearchTree {
9+
Node root;
10+
11+
//create a new node and initialize it
12+
public void addNewNode(int key, String data){
13+
Node newNode=new Node(key, data);
14+
if(root==null){//if empty tree, set the new node as the root node
15+
root=newNode;
16+
}else{
17+
//set root node as the start point
18+
Node focusNode=root;
19+
//set the parent node for the new node
20+
Node parent;
21+
while(true){
22+
parent=focusNode;//set the parent node to the root node as start point
23+
//check if the new node should go to the left
24+
if(key<focusNode.key){
25+
//switch focus to the left child
26+
focusNode=focusNode.leftChild;
27+
if(focusNode==null){//no left child there
28+
parent.leftChild=newNode;// add newnode tobe the leftchild of the parent
29+
return;//all done
30+
}
31+
}else{//check if the new node should go to the right
32+
focusNode=focusNode.rightChild;
33+
if(focusNode==null){//no right child there
34+
parent.rightChild=newNode;// add newnode tobe the rightchild of the parent
35+
return;
36+
}
37+
}
38+
}
39+
}
40+
}
41+
42+
//inorder traverse order: leftchild, parent, rightchild
43+
public void inOrderTraverse(Node focusNode){
44+
if(focusNode!=null){
45+
inOrderTraverse(focusNode.leftChild);
46+
System.out.println(focusNode);
47+
inOrderTraverse(focusNode.rightChild);
48+
}
49+
}
50+
51+
//preorder traverse order: parent, leftchild, rightchild
52+
public void preOrderTraverse(Node focusNode){
53+
if(focusNode!=null){
54+
System.out.println(focusNode);
55+
preOrderTraverse(focusNode.leftChild);
56+
preOrderTraverse(focusNode.rightChild);
57+
}
58+
}
59+
60+
//postorder traverse order: leftchild, rightchild, parent,
61+
public void postOrderTraverse(Node focusNode){
62+
if(focusNode!=null){
63+
64+
postOrderTraverse(focusNode.leftChild);
65+
postOrderTraverse(focusNode.rightChild);
66+
System.out.println(focusNode);
67+
}
68+
}
69+
70+
//find a node
71+
public Node findNode(int key){
72+
//start with the root of the tree
73+
Node focusNode=root;
74+
while(focusNode.key!=key){
75+
if(key<focusNode.key){
76+
//we needto search on the left child
77+
focusNode=focusNode.leftChild;
78+
}else{
79+
//we needto search on the right child
80+
focusNode=focusNode.rightChild;
81+
}
82+
//if the node was not found
83+
if(focusNode==null) return null;
84+
}
85+
return focusNode;
86+
}
87+
88+
89+
//find the min in the tree
90+
public Node getTreeMin(){
91+
Node focusNode=root;
92+
while(focusNode.leftChild!=null){
93+
focusNode=focusNode.leftChild;
94+
}
95+
return focusNode;
96+
}
97+
98+
//find the max in the tree
99+
public Node getTreeMax(){
100+
Node focusNode=root;
101+
while(focusNode.rightChild!=null){
102+
focusNode=focusNode.rightChild;
103+
}
104+
return focusNode;
105+
}
106+
107+
//delete a node
108+
public Node delete(Node focusNode, int key){
109+
if(focusNode==null) return null;
110+
else if(key<focusNode.key) focusNode.leftChild=delete(focusNode.leftChild,key);
111+
else if(key>focusNode.key) focusNode.rightChild=delete(focusNode.rightChild, key);
112+
else{
113+
if(focusNode.rightChild==null) return focusNode.leftChild;
114+
if(focusNode.leftChild==null) return focusNode.rightChild;
115+
Node t=focusNode;
116+
focusNode=min(t.rightChild);
117+
focusNode.rightChild=deleteMin(t.rightChild);
118+
focusNode.leftChild=t.leftChild;
119+
}
120+
return focusNode;
121+
}
122+
123+
private Node deleteMin(Node x){
124+
if(x.leftChild==null) return x.rightChild;
125+
x.leftChild=deleteMin(x.leftChild);
126+
return x;
127+
}
128+
129+
private Node min(Node x){
130+
if(x.leftChild==null) return x;
131+
return min(x.leftChild);
132+
}
133+
134+
public int getNodeNum(Node x){
135+
int countLeft=0, countRight=0;
136+
int count=0;
137+
if(x==null) count=0;
138+
else{
139+
while(x.leftChild!=null) countLeft++;
140+
while(x.rightChild!=null) countRight++;
141+
142+
}
143+
count=countLeft+countRight;
144+
return count;
145+
}
146+
147+
148+
public static void main(String[] args) {
149+
// TODO Auto-generated method stub
150+
BinarySearchTree tree=new BinarySearchTree();
151+
152+
//add new node
153+
tree.addNewNode(1, "Boss");
154+
tree.addNewNode(2, "President");
155+
tree.addNewNode(3, "Head");
156+
tree.addNewNode(4, "Manager");
157+
tree.addNewNode(5, "Secretary");
158+
tree.addNewNode(6, "Salesman");
159+
160+
//check traverse implementation
161+
//tree.inOrderTraverse(tree.root);
162+
//tree.preOrderTraverse(tree.root);
163+
//System.out.println("tree data before deleted key:");
164+
tree.postOrderTraverse(tree.root);
165+
System.out.println("node num: "+tree.getNodeNum(tree.root));
166+
167+
//System.out.println("search data with key 3");
168+
System.out.println(tree.findNode(2));
169+
170+
System.out.println(" ");
171+
System.out.println("remove data with key 4");
172+
173+
Node y=tree.findNode(4);
174+
tree.delete(y,4);
175+
176+
System.out.println(" ");
177+
System.out.println("tree data after deleted key:");
178+
179+
}
180+
181+
}
182+
183+
//define the nodes in the binary search tree
184+
class Node{
185+
int key;
186+
String data;
187+
188+
Node leftChild;
189+
Node rightChild;
190+
191+
Node(int key, String data){
192+
this.key=key;
193+
this.data=data;
194+
}
195+
196+
public String toString(){
197+
return this.data+" has a key "+ this.key;
198+
}
199+
}

0 commit comments

Comments
 (0)