C++ program to traverse a binary tree in Pre-order
Do you like this story?
/* Write C++ program that uses non-recursive functions to traverse a binary tree in Pre-order */
#include
#include
#include
using namespace std;
class node
{
public:
class node *left;
class node *right;
int data;
};
class tree: public node
{
public:
int stk[50],top;
node *root;
tree()
{
root=NULL;
top=0;
}
void insert(int ch)
{
node *temp,*temp1;
if(root== NULL)
{
root=new node;
root->data=ch;
root->left=NULL;
root->right=NULL;
return;
}
temp1=new node;
temp1->data=ch;
temp1->right=temp1->left=NULL;
temp=search(root,ch);
if(temp->data>ch)
temp->left=temp1;
else
temp->right=temp1;
}
node *search(node *temp,int ch)
{
if(root== NULL)
{
cout <<"no node present";
return NULL;
}
if(temp->left==NULL && temp->right== NULL)
return temp;
if(temp->data>ch)
{ if(temp->left==NULL) return temp;
search(temp->left,ch);}
else
{ if(temp->right==NULL) return temp;
search(temp->right,ch);
} }
void display(node *temp)
{
if(temp==NULL)
return ;
display(temp->left);
cout<data <<" ";
display(temp->right);
}
void preorder( node *root)
{
node *p,*q;
p=root;
q=NULL;
top=0;
while(p!=NULL)
{
cout <data << " ";
if(p->right!=NULL)
{
stk[top]=p->right->data;
top++;
}
p=p->left;
if(p==NULL && top>0)
{
p=pop(root);
}
}
}
node * pop(node *p)
{
int ch;
ch=stk[top-1];
if(p->data==ch)
{
top--;
return p;
}
if(p->data>ch)
pop(p->left);
else
pop(p->right);
}
};
main()
{
tree t1;
int ch,n,i;
while(1)
{
cout <<"\n1.INSERT\n2.DISPLAY 3.PREORDER TRAVERSE\n4.EXIT\nEnter your choice:";
cin >> ch;
switch(ch)
{
case 1: cout <<"enter no of elements to insert:";
cout<<"\n enter the elements";
cin >> n;
for(i=1;i<=n;i++)
{ cin >> ch;
t1.insert(ch);
}
break;
case 2: t1.display(t1.root);break;
case 3: t1.preorder(t1.root); break;
case 4: exit(1);
}
}
}
OUTPUT
#include
#include
#include
using namespace std;
class node
{
public:
class node *left;
class node *right;
int data;
};
class tree: public node
{
public:
int stk[50],top;
node *root;
tree()
{
root=NULL;
top=0;
}
void insert(int ch)
{
node *temp,*temp1;
if(root== NULL)
{
root=new node;
root->data=ch;
root->left=NULL;
root->right=NULL;
return;
}
temp1=new node;
temp1->data=ch;
temp1->right=temp1->left=NULL;
temp=search(root,ch);
if(temp->data>ch)
temp->left=temp1;
else
temp->right=temp1;
}
node *search(node *temp,int ch)
{
if(root== NULL)
{
cout <<"no node present";
return NULL;
}
if(temp->left==NULL && temp->right== NULL)
return temp;
if(temp->data>ch)
{ if(temp->left==NULL) return temp;
search(temp->left,ch);}
else
{ if(temp->right==NULL) return temp;
search(temp->right,ch);
} }
void display(node *temp)
{
if(temp==NULL)
return ;
display(temp->left);
cout<
display(temp->right);
}
void preorder( node *root)
{
node *p,*q;
p=root;
q=NULL;
top=0;
while(p!=NULL)
{
cout <
if(p->right!=NULL)
{
stk[top]=p->right->data;
top++;
}
p=p->left;
if(p==NULL && top>0)
{
p=pop(root);
}
}
}
node * pop(node *p)
{
int ch;
ch=stk[top-1];
if(p->data==ch)
{
top--;
return p;
}
if(p->data>ch)
pop(p->left);
else
pop(p->right);
}
};
main()
{
tree t1;
int ch,n,i;
while(1)
{
cout <<"\n1.INSERT\n2.DISPLAY 3.PREORDER TRAVERSE\n4.EXIT\nEnter your choice:";
cin >> ch;
switch(ch)
{
case 1: cout <<"enter no of elements to insert:";
cout<<"\n enter the elements";
cin >> n;
for(i=1;i<=n;i++)
{ cin >> ch;
t1.insert(ch);
}
break;
case 2: t1.display(t1.root);break;
case 3: t1.preorder(t1.root); break;
case 4: exit(1);
}
}
}
OUTPUT
1.INSERT
2.DISPLAY 3.PREORDER TRAVERSE
4.EXIT
Enter your choice:1
enter no of elements to insert
enter the elements7
5 24 36 11 44 2 21
1.INSERT
2.DISPLAY 3.PREORDER TRAVERSE
4.EXIT
Enter your choice:2
2 5 11 21 24 36 44
1.INSERT
2.DISPLAY 3.PREORDER TRAVERSE
4.EXIT
Enter your choice:3
5 2 24 11 21 36 44
1.INSERT
2.DISPLAY 3.PREORDER TRAVERSE
4.EXIT
Enter your choice:4
This post was written by: Rajendra Prasad
Rajendra Prasad is a professional blogger, web designer and front end web developer. Follow him on Facebook
