-
Notifications
You must be signed in to change notification settings - Fork 0
/
Bst.java
117 lines (107 loc) · 3.48 KB
/
Bst.java
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 Bst<T extends Comparable<T>> {
T data;
Bst<T>left;
Bst<T>right;
Bst(T data){
this.data=data;
this.left=null;
this.right=null;
}
int check=0;
/*
if old_data.compareto(new_data); if result <0 then
new element is greater than old element
* if result>0 than new element is smaller than old element
if result==0 than new element is equal to old element
*/
public boolean insert(T o) throws Exception {
if(data.compareTo(o)<0){
if(right==null){
right=new Bst<T>(o);
return true;
}
right.insert(o);
}
else if (data.compareTo(o)>0) {
if(left==null){
left=new Bst<T>(o);
return true;
}
left.insert(o);
}
return false;
}
public void show(Bst<T> temp_root) { //inorder traversal
if(temp_root!=null){
show(temp_root.left);
System.out.println(temp_root.data);
show(temp_root.right);
}
}
public void show_root(Bst<T> temp_root){
if(temp_root!=null){
System.out.println("root element is :"+temp_root.data);
}else{
System.out.println("tree haven't any element ");
}
}
public int height_tree(Bst<T> temp_root){
if(temp_root!=null){
if(temp_root.left==null&& temp_root.right==null){
return 0;
}else{
return 1+Math.max(height_tree(temp_root.left), height_tree(temp_root.right));
}
}else{
return 0;
}
}
public void search(T data, Bst<T> temp_root){
try{
if(temp_root==null){
System.out.println("tree is empty");
}else{
if(temp_root.data==data){
check++;
System.out.println("founded at :"+check);
return;
}else{
if(temp_root.data.compareTo(data)>0){ // if element is smaller than root
check++;
if(temp_root.left!=null){
search(data, temp_root.left);
}else{
System.out.println("not available");
return;
}
}else if(temp_root.data.compareTo(data)<0){ // if element is grater than root
check++;
if(temp_root.right!=null){
search(data, temp_root.right);
}else{
System.out.println("not available");
return;
}
}
}
}
}catch(NullPointerException ex){
}
}
public static void main(String[] args) throws Exception {
Bst<Integer> temp_root=new Bst<Integer>(5);
temp_root.insert(1);
temp_root.insert(2);
temp_root.insert(3);
temp_root.insert(4);
temp_root.insert(6);
temp_root.insert(7);
temp_root.insert(8);
temp_root.insert(9);
temp_root.insert(10);
// temp_root.show(temp_root);
// temp_root.show_root(temp_root);
temp_root.search(10, temp_root);
// System.out.println("height of tree"+temp_root.height_tree(temp_root));
}
}