이진 검색 트리는 모든 노드가 다음과 같은 몇 가지 속성을 갖는 정렬된 이진 트리입니다 -
- 노드의 오른쪽 하위 트리에는 상위 노드의 키보다 큰 키가 있습니다.
- 노드의 왼쪽 하위 트리에는 상위 노드의 키보다 작거나 같은 키가 있습니다.
- 각 노드는 2개 이하의 하위 노드를 가질 수 없습니다.
다음은 무작위 이진 검색 트리를 구현하는 C++ 프로그램입니다.
알고리즘
Begin class BST to declare following functions: search() = To search an item in BST. initialize temp = root; while(temp != NULL) Increase depth if(temp->info == data) print Data and depth else if(temp->info >data) temp = temp->l; else temp = temp->r; insert() = To insert items in the tree: If tree is empty insert data as root. If tree is not empty data<root Insert data as left child. Else Insert data as right child. del() = To delete an item from tree. casea() = Called from del() if l = r = null. caseb() = Called from del() if l != null, r = null. caseb() = Called from del() if l = null, r != null. casec() = Called from del() if l != null, r != null. inorder() to traverse the node as inorder as: left – root – right. preorder() to traverse the node as preorder as: root – Left – right. postorder() to traverse the node as preorder as: left – right – root End
예시 코드
# include <iostream>
# include <cstdlib>
using namespace std;
struct nod//node declaration {
int info;
struct nod *l;
struct nod *r;
}*r;
class BST {
public:
//declaration of functions
void search(nod *, int);
void find(int, nod **, nod **);
void insert(nod *, nod *);
void del(int);
void casea(nod *,nod *);
void caseb(nod *,nod *);
void casec(nod *,nod *);
void preorder(nod *);
void inorder(nod *);
void postorder(nod *);
void show(nod *, int);
BST() {
r = NULL;
}
};
void BST::find(int i, nod **par, nod **loc)//find the position of element {
nod *ptr, *ptrsave;
if (r == NULL) {
*loc = NULL;
*par = NULL;
return;
}
if (i == r->info) {
*loc = r;
*par = NULL;
return;
} if (i < r->info)
ptr = r->l;
else
ptr = r->r;
ptrsave = r;
while (ptr != NULL) {
if (i == ptr->info) {
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (i < ptr->info)
ptr = ptr->l;
else
ptr = ptr->r;
}
*loc = NULL;
*par = ptrsave;
}
void BST::search(nod *root, int data) {
int depth = 0;
nod *temp = new nod;
temp = root;
while(temp != NULL) {
depth++;
if(temp->info == data) {
cout<<"\nData found at depth: "<<depth<<endl;
return;
} else if(temp->info >data)
temp = temp->l;
else
temp = temp->r;
}
cout<<"\n Data not found"<<endl;
return;
}
void BST::insert(nod *tree, nod *newnode) {
if (r == NULL) {
r = new nod;
r->info = newnode->info;
r->l = NULL;
r->r = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->info == newnode->info) {
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info >newnode->info) {
if (tree->l != NULL) {
insert(tree->l, newnode);
} else {
tree->l= newnode;
(tree->l)->l = NULL;
(tree->l)->r= NULL;
cout<<"Node Added to Left"<<endl;
return;
}
} else {
if (tree->r != NULL) {
insert(tree->r, newnode);
} else {
tree->r = newnode;
(tree->r)->l= NULL;
(tree->r)->r = NULL;
cout<<"Node Added to Right"<<endl;
return;
}
}
}
void BST::del(int i) {
nod *par, *loc;
if (r == NULL) {
cout<<"Tree empty"<<endl;
return;
}
find(i, &par, &loc);
if (loc == NULL) {
cout<<"Item not present in tree"<<endl;
return;
}
if(loc->l == NULL && loc->r == NULL) {
casea(par, loc);
cout<<"item deleted"<<endl;
}
if (loc->l!= NULL && loc->r == NULL) {
caseb(par, loc);
cout<<"item deleted"<<endl;
}
if (loc->l== NULL && loc->r != NULL) {
caseb(par, loc);
cout<<"item deleted"<<endl;
}
if (loc->l != NULL && loc->r != NULL) {
casec(par, loc);
cout<<"item deleted"<<endl;
}
free(loc);
}
void BST::casea(nod *par, nod *loc ) {
if (par == NULL) {
r = NULL;
} else {
if (loc == par->l)
par->l = NULL;
else
par->r = NULL;
}
}
void BST::caseb(nod *par, nod *loc) {
nod *child;
if (loc->l!= NULL)
child = loc->l;
else
child = loc->r;
if (par == NULL) {
r = child;
} else {
if (loc == par->l)
par->l = child;
else
par->r = child;
}
}
void BST::casec(nod *par, nod *loc) {
nod *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->r;
while (ptr->l!= NULL) {
ptrsave = ptr;
ptr = ptr->l;
}
suc = ptr;
parsuc = ptrsave;
if (suc->l == NULL && suc->r == NULL)
casea(parsuc, suc);
else
caseb(parsuc, suc);
if (par == NULL) {
r = suc;
} else {
if (loc == par->l)
par->l = suc;
else
par->r= suc;
}
suc->l = loc->l;
suc->r= loc->r;
}
void BST::preorder(nod *ptr) {
if (r == NULL) {
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL) {
cout<<ptr->info<<" ";
preorder(ptr->l);
preorder(ptr->r);
}
}
void BST::inorder(nod *ptr) {
if (r == NULL) {
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL) {
inorder(ptr->l);
cout<<ptr->info<<" ";
inorder(ptr->r);
}
}
void BST::postorder(nod *ptr) {
if (r == NULL) {
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL) {
postorder(ptr->l);
postorder(ptr->r);
cout<<ptr->info<<" ";
}
}
void BST::show(nod *ptr, int level) {
int i;
if (ptr != NULL) {
show(ptr->r, level+1);
cout<<endl;
if (ptr == r)
cout<<"Root->: ";
else {
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->info;
show(ptr->l, level+1);
}
}
int main() {
int c, n,item;
BST bst;
nod *t;
while (1) {
cout<<"1.Insert Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Search Element"<<endl;
cout<<"4.Inorder Traversal"<<endl;
cout<<"5.Preorder Traversal"<<endl;
cout<<"6.Postorder Traversal"<<endl;
cout<<"7.Display the tree"<<endl;
cout<<"8.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>c;
switch©//perform switch operation {
case 1:
t = new nod;
cout<<"Enter the number to be inserted : ";
cin>>t->info;
bst.insert(r, t);
break;
case 2:
if (r == NULL) {
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>n;
bst.del(n);
break;
case 3:
cout<<"Search:"<<endl;
cin>>item;
bst.search(r,item);
break;
case 4:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(r);
cout<<endl;
break;
case 5:
cout<<"Preorder Traversal of BST:"<<endl;
bst.preorder(r);
cout<<endl;
break;
case 6:
cout<<"Postorder Traversal of BST:"<<endl;
bst.postorder(r);
cout<<endl;
break;
case 7:
cout<<"Display BST:"<<endl;
bst.show(r,1);
cout<<endl;
break;
case 8:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
}
출력
1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 6 Root Node is Added 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 7 Node Added to Right 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 5 Node Added to Left 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 1 Enter the number to be inserted : 4 Node Added to Left 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 3 Search: 7 Data found at depth: 2 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 3 Search: 1 Data not found 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 4 Inorder Traversal of BST: 4 5 6 7 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 5 Preorder Traversal of BST: 6 5 4 7 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 6 Postorder Traversal of BST: 4 5 7 6 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 7 Display BST: 7 Root->: 6 5 4 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 2 Enter the number to be deleted : 1 Item not present in tree 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 5 Preorder Traversal of BST: 6 5 4 7 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 2 Enter the number to be deleted : 5 item deleted 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 7 Display BST: 7 Root->: 6 4 1.Insert Element 2.Delete Element 3.Search Element 4.Inorder Traversal 5.Preorder Traversal 6.Postorder Traversal 7.Display the tree 8.Quit Enter your choice : 8