Skip to content

Commit ea9d146

Browse files
author
cfdcoder
committed
add binary search tree
1 parent 444f4d8 commit ea9d146

File tree

50 files changed

+5192
-1593
lines changed

Some content is hidden

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

50 files changed

+5192
-1593
lines changed

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

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
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+
public static void main(String[] args) {
12+
// TODO Auto-generated method stub
13+
14+
}
15+
16+
}
17+
18+
//define the nodes in the binary search tree
19+
class Node{
20+
int key;
21+
String data;
22+
23+
Node leftChild;
24+
Node rightChild;
25+
26+
Node(int key, String name){
27+
this.key=key;
28+
this.data=data;
29+
}
30+
31+
public String toString(){
32+
return this.data+" has a key"+ this.key;
33+
}
34+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/20/809131f719b000151d15c07ec223227e

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
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+
10+
public static void main(String[] args) {
11+
// TODO Auto-generated method stub
12+
13+
}
14+
15+
}
16+
17+
//define the nodes in the binary search tree
18+
class Node{
19+
int key;
20+
String data;
21+
22+
Node leftChild;
23+
Node rightChild;
24+
25+
Node(int key, String name){
26+
this.key=key;
27+
this.data=data;
28+
}
29+
30+
public String toString(){
31+
return this.data+" has a key"+ this.key;
32+
}
33+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/28/9000ff9420b000151d15c07ec223227e

Lines changed: 162 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,162 @@
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 Node deleteNode(int key){
82+
83+
}
84+
85+
public boolean removeNode(int key){
86+
Node focusNode=root;
87+
Node parent =root;
88+
boolean isItLeftChild=true;
89+
while(focusNode.key!=key){
90+
parent=focusNode;
91+
if(key<focusNode.key){
92+
isItLeftChild=true;
93+
focusNode=focusNode.leftChild;
94+
}else{
95+
isItLeftChild=false;
96+
focusNode=focusNode.rightChild;
97+
}
98+
99+
if(focusNode==null) return false;
100+
}
101+
102+
if(focusNode.leftChild==null && focusNode.rightChild==null){
103+
if(focusNode==root) root=null;
104+
else if(isItLeftChild) parent.leftChild=null;
105+
else parent.rightChild=null;
106+
}
107+
else if(focusNode.rightChild==null){
108+
if(focusNode==root) root=focusNode.leftChild;
109+
else if(isItLeftChild) parent.leftChild=focusNode.leftChild;
110+
else parent.rightChild=focusNode.leftChild;
111+
}
112+
else if(focusNode.leftChild==null){
113+
if(focusNode==root) root=focusNode.rightChild;
114+
else if(isItLeftChild) parent.leftChild=focusNode.rightChild;
115+
else parent.rightChild=focusNode.leftChild;
116+
}
117+
118+
119+
}
120+
121+
public static void main(String[] args) {
122+
// TODO Auto-generated method stub
123+
BinarySearchTree tree=new BinarySearchTree();
124+
125+
//add new node
126+
tree.addNewNode(1, "Boss");
127+
tree.addNewNode(2, "President");
128+
tree.addNewNode(3, "Head");
129+
tree.addNewNode(4, "Manager");
130+
tree.addNewNode(5, "Secretary");
131+
tree.addNewNode(6, "Salesman");
132+
133+
//check traverse implementation
134+
tree.inOrderTraverse(tree.root);
135+
tree.preOrderTraverse(tree.root);
136+
tree.postOrderTraverse(tree.root);
137+
138+
System.out.println("search data with key 3");
139+
System.out.println(tree.findNode(3));
140+
141+
142+
}
143+
144+
}
145+
146+
//define the nodes in the binary search tree
147+
class Node{
148+
int key;
149+
String data;
150+
151+
Node leftChild;
152+
Node rightChild;
153+
154+
Node(int key, String data){
155+
this.key=key;
156+
this.data=data;
157+
}
158+
159+
public String toString(){
160+
return this.data+" has a key "+ this.key;
161+
}
162+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/2b/803e9f101db000151d15c07ec223227e

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
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+
67+
public static void main(String[] args) {
68+
// TODO Auto-generated method stub
69+
BinarySearchTree tree=new BinarySearchTree();
70+
tree.addNewNode(1, "Boss");
71+
tree.addNewNode(2, "President");
72+
tree.addNewNode(3, "Head");
73+
tree.addNewNode(4, "Manager");
74+
tree.addNewNode(5, "Secretary");
75+
tree.addNewNode(6, "Salesman");
76+
77+
//tree.inOrderTraverse(tree.root);
78+
//tree.preOrderTraverse(tree.root);
79+
tree.postOrderTraverse(tree.root);
80+
81+
}
82+
83+
}
84+
85+
//define the nodes in the binary search tree
86+
class Node{
87+
int key;
88+
String data;
89+
90+
Node leftChild;
91+
Node rightChild;
92+
93+
Node(int key, String data){
94+
this.key=key;
95+
this.data=data;
96+
}
97+
98+
public String toString(){
99+
return this.data+" has a key "+ this.key;
100+
}
101+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/2e/203068af19b000151d15c07ec223227e

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
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+
10+
public static void main(String[] args) {
11+
// TODO Auto-generated method stub
12+
13+
}
14+
15+
}
16+
17+
class Node{
18+
int key;
19+
String data;
20+
21+
Node leftChild;
22+
Node rightChild;
23+
24+
Node(int key, String name){
25+
this.key=key;
26+
this.data=data;
27+
}
28+
29+
public String toString(){
30+
return data+" has a key"+key;
31+
}
32+
}

0 commit comments

Comments
 (0)