20130330

How to write cpp program for BST Binary Search Tree


/*BST-Binary Search Tree Program for  insertion and traversal
How to write C++ Program for BST-Binary Search Tree
Cpp program for BST Binary Search Tree implementation with class*/
-->
//bst-Binary Search tree
#include<iostream>
using namespace std;

class BST
{
private:
struct node
{
int data;
node *left;
node *right;
};
node* start;

public:
BST(){start=NULL;}
void insert(int data);
void traverse();
void inorder(node *);
void preorder(node *);
void postorder(node *);
};

void BST:: insert(int d)
{
node *newnode;
newnode=new node;
newnode->data=d;
newnode->left=NULL;
newnode->right=NULL;

node *ptr;
ptr=start;
if(start==NULL)
{
start=newnode;
}
else
{
while(ptr!=NULL)
{
if(d<ptr->data)
{
if(ptr->left==NULL)
{
ptr->left=newnode;
ptr=NULL;
}
else
{
ptr=ptr->left;
}
}
else
{
//if(d>ptr->data)
//{
if(ptr->right==NULL)
{
ptr->right=newnode;
ptr=NULL;
}
else
{
ptr=ptr->right;
}
// }
}
}
}
}

void BST::traverse()
{
cout<<"\n Inorder:\n";
inorder(start);
cout<<"\n Preorder:\n";
preorder(start);
cout<<"\n Postorder:\n";
postorder(start);

}
void BST::inorder(node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->left);
cout<<ptr->data<<"\t";
inorder(ptr->right);
}
}
void BST::preorder(node *ptr)
{
if(ptr!=NULL)
{
cout<<ptr->data<<"\t";
preorder(ptr->left);
preorder(ptr->right);
}
}
void BST::postorder(node *ptr)
{
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->data<<"\t";

}
}


int main()
{
BST b;
b.insert(8);
b.insert(3);
b.insert(10);
b.insert(1);
b.insert(6);
b.insert(7);
b.insert(4);
b.insert(10);
b.insert(14);
b.insert(13);

b.traverse();




return 0;
}
/*
$ g++ bst_revision.cxx
$ ./a.out

Inorder:
1 3 4 6 7 8 10 10 13 14
Preorder:
8 3 1 6 4 7 10 10 14 13
Postorder:
1 4 7 6 3 13 14 10 10 8
*


Depth-first
  • Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)
  • In-order traversal sequence: A, B, C, D, E, F, G, H ,I (left, root, right)
  • Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)
Breadth-first
  • Level-order traversal sequence: F, B, G, A, D, I, C, E, H
Inorder:
1 2 3 4 5 6 7 8 9
Pre order:
6 2 14 3 5 7 9 8
Post order:

No comments:

Post a Comment