This program is to implement a binary search tree in c++

#include

using

namespace std;

struct

node{

int

data;

node *left, *right;

node( int

d = 0

, node *l = NULL

, node *r = NULL

): data(d), left(l), right(r){}

};

class

tree{

public:

node *root;

tree(){

root = NULL

;

}

void

inorder(){

cout<<

"The inorder traversal is :";

inorder(root);

cout<

}

void

inorder(node *temp){

if

(temp){

inorder(temp->left);

cout<data<<"\t"

;

inorder(temp->right);

}

}

void

preorder(){

cout<<

"The preorder traversal is :";

preorder(root);

cout<

}

void

preorder(node *temp){

if

( temp){

cout<data<<"\t"

;

preorder(temp->left);

preorder(temp->right);

}

}

void

postorder(){

cout<<

"The postorder traversal is :";

postorder(root);

cout<

}

void

postorder(node *temp){

if

( temp){

postorder(temp->left);

postorder(temp->right);

cout<data<<"\t"

;

}

}

void

insert( int

data ){

insert(data, root);

}

void

insert( int

data, node *&temp){

if

( !temp)

temp = new

node(data);

else

if

( temp->data < data )

insert(data, temp->right);

else

if

( temp->data > data)

insert(data, temp->left);

}

node *findmin(node *temp){

while

( temp->left != NULL

)

temp = temp->left;

return

temp;

}

void

remove(int

data){

remove(data, root);

}

void

remove( int

data, node *&temp){

if

( temp == NULL

)

cout<<"data not found\n"

;

else

if

( temp->data < data)

remove(data, temp->right);

else

if

(temp->data > data)

remove(data, temp->left);

else

if

( temp->right && temp->left){

node *min = findmin(temp->right);

temp->data = min->data;

remove(min->data, temp->right);

}else

{

node *curr = temp;

if

( !temp->left)

temp = temp->right;

else

temp = temp->left;

delete

curr;

}

}

};

int

main(){

int

choice, data;

tree obj;

do

{

cout<<

"Enter choice:\n1-Insert\n2-Delete\n3-Inorder Traversal\n4-Preorder Traversal\n5-Postorder Traversal\n6-Quit\t:";

cin>>choice;

switch

(choice){

case

1

:

cout<<

"Enter data for insert:\t";

cin>>data;

obj.insert(data);

break

;

case

2

:

cout<<

"Enter data for removal:\t";

cin>>data;

obj.remove(data);

break

;

case

3

:

obj.inorder();

break

;

case

4

:

obj.preorder();

break

;

case

5

:

obj.postorder();

break

;

case

6

: break

;

}

}while

( choice != 6

);

return

0

;

}

Resources

Top Categories

Product

Company