TheAlgorithms/C++
1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
binary_search_tree.cpp
Go to the documentation of this file.
1
9
#include <iostream>
10
11
struct
node {
12
int
val;
13
node *left;
14
node *right;
15
};
16
17
struct
Queue {
18
node
*t[100];
19
int
front;
20
int
rear;
21
};
22
23
Queue
queue
;
24
25
void
enqueue(
node
*n) {
queue
.t[
queue
.rear++] = n; }
26
27
node
*dequeue() {
return
(
queue
.t[
queue
.
front
++]); }
28
29
void
Insert(
node
*n,
int
x) {
30
if
(x < n->val) {
31
if
(n->left == NULL) {
32
node
*temp =
new
node
;
33
temp->val = x;
34
temp->left = NULL;
35
temp->right = NULL;
36
n->left = temp;
37
}
else
{
38
Insert(n->left, x);
39
}
40
}
else
{
41
if
(n->right == NULL) {
42
node
*temp =
new
node
;
43
temp->val = x;
44
temp->left = NULL;
45
temp->right = NULL;
46
n->right = temp;
47
}
else
{
48
Insert(n->right, x);
49
}
50
}
51
}
52
53
int
findMaxInLeftST(
node
*n) {
54
while
(n->right != NULL) {
55
n = n->right;
56
}
57
return
n->val;
58
}
59
60
void
Remove(
node
*p,
node
*n,
int
x) {
61
if
(n->val == x) {
62
if
(n->right == NULL && n->left == NULL) {
63
if
(x < p->val) {
64
p->right = NULL;
65
}
else
{
66
p->left = NULL;
67
}
68
}
else
if
(n->right == NULL) {
69
if
(x < p->val) {
70
p->right = n->left;
71
}
else
{
72
p->left = n->left;
73
}
74
}
else
if
(n->left == NULL) {
75
if
(x < p->val) {
76
p->right = n->right;
77
}
else
{
78
p->left = n->right;
79
}
80
}
else
{
81
int
y = findMaxInLeftST(n->left);
82
n->val = y;
83
Remove(n, n->right, y);
84
}
85
}
else
if
(x < n->val) {
86
Remove(n, n->left, x);
87
}
else
{
88
Remove(n, n->right, x);
89
}
90
}
91
92
void
BFT(
node
*n) {
93
if
(n != NULL) {
94
std::cout << n->val <<
" "
;
95
enqueue(n->left);
96
enqueue(n->right);
97
BFT(dequeue());
98
}
99
}
100
101
void
Pre(
node
*n) {
102
if
(n != NULL) {
103
std::cout << n->val <<
" "
;
104
Pre(n->left);
105
Pre(n->right);
106
}
107
}
108
109
void
In(
node
*n) {
110
if
(n != NULL) {
111
In(n->left);
112
std::cout << n->val <<
" "
;
113
In(n->right);
114
}
115
}
116
117
void
Post(
node
*n) {
118
if
(n != NULL) {
119
Post(n->left);
120
Post(n->right);
121
std::cout << n->val <<
" "
;
122
}
123
}
124
125
int
main
() {
126
queue
.
front
= 0;
127
queue
.rear = 0;
128
int
value;
129
int
ch;
130
node
*root =
new
node
;
131
std::cout <<
"\nEnter the value of root node :"
;
132
std::cin >> value;
133
root->val = value;
134
root->left = NULL;
135
root->right = NULL;
136
do
{
137
std::cout <<
"\n1. Insert"
138
<<
"\n2. Delete"
139
<<
"\n3. Breadth First"
140
<<
"\n4. Preorder Depth First"
141
<<
"\n5. Inorder Depth First"
142
<<
"\n6. Postorder Depth First"
;
143
144
std::cout <<
"\nEnter Your Choice : "
;
145
std::cin >> ch;
146
int
x;
147
switch
(ch) {
148
case
1:
149
std::cout <<
"\nEnter the value to be Inserted : "
;
150
std::cin >> x;
151
Insert(root, x);
152
break
;
153
case
2:
154
std::cout <<
"\nEnter the value to be Deleted : "
;
155
std::cin >> x;
156
Remove(root, root, x);
157
break
;
158
case
3:
159
BFT(root);
160
break
;
161
case
4:
162
Pre(root);
163
break
;
164
case
5:
165
In(root);
166
break
;
167
case
6:
168
Post(root);
169
break
;
170
}
171
}
while
(ch != 0);
172
173
return
0;
174
}
queue
Definition
queue.hpp:9
queue::front
value_type front() const
Definition
queue.hpp:72
main
int main()
Main function.
Definition
generate_parentheses.cpp:110
Queue
Definition
binary_search_tree.cpp:17
node
Definition
binary_search_tree.cpp:11
data_structures
binary_search_tree.cpp
Generated by
1.13.2