-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinarySearchTree.h
102 lines (94 loc) · 2.24 KB
/
BinarySearchTree.h
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
#include<bits/stdc++.h>
using namespace std;
class BST {
struct node {
int data;
node* left;
node* right;
};
node* root;
node* makeEmpty(node* t) {
if(t == NULL) return NULL;
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
return NULL;
}
node* insert(int x, node* t)
{
if(t == NULL)
{
t = new node;
t->data = x;
t->left = t->right = NULL;
}
else if(x < t->data) t->left = insert(x, t->left);
else if(x > t->data) t->right = insert(x, t->right);
return t;
}
node* findMin(node* t)
{
if(t == NULL) return NULL;
else if(t->left == NULL) return t;
else return findMin(t->left);
}
node* findMax(node* t) {
if(t == NULL) return NULL;
else if(t->right == NULL) return t;
else return findMax(t->right);
}
node* remove(int x, node* t) {
node* temp;
if(t == NULL) return NULL;
else if(x < t->data) t->left = remove(x, t->left);
else if(x > t->data) t->right = remove(x, t->right);
else if(t->left && t->right)
{
temp = findMin(t->right);
t->data = temp->data;
t->right = remove(t->data, t->right);
}
else
{
temp = t;
if(t->left == NULL) t = t->right;
else if(t->right == NULL) t = t->left;
delete temp;
}
return t;
}
void inorder(node* t) {
if(t == NULL) return;
inorder(t->left);
cout << t->data << " ";
inorder(t->right);
}
node* find(node* t, int x) {
if(t == NULL) return NULL;
else if(x < t->data) return find(t->left, x);
else if(x > t->data) return find(t->right, x);
else return t;
}
public:
BST() {
root = NULL;
}
~BST() {
root = makeEmpty(root);
}
void insert(int x) {
root = insert(x, root);
}
void remove(int x) {
root = remove(x, root);
}
void display() {
inorder(root);
cout << endl;
}
void search(int x) {
root = find(root, x);
}
};