TREES with C++
A tree is a finite set of one or more nodes such that there is a specially designated node called the root and the remaining nodes are partitioned into n0 disjoint sets T1, ….,Tn, where each of these sets is a tree. The sets are called the subtrees of the root.
Binary Trees
Binary trees are characterized by the fact that any node can have at most two children; i.e., there is no node with degree greater than two. A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left and right subtrees.
ADT of binary tree
AbstractDataType binaryTree
{
instances
collection of elements; if not empty, the collection is partitioned into a root, left subtree, and right subtree; each subtree is also a binary tree;
operations
empty( ) :return true if the stack is empty, return false otherwise;
size( ) :return the number of elements / nodes in the tree
preorder(visit) :preorder traversal of binary tree; visit is the visit function to use;
inorder(visit) :inorder traversal of a binary tree
postorder(visit):postorder traversal of a binary tree.
}
Algorithms for non-recursive tree traversals in C++
Preorder traversal
1.define a stack
2.traverse the left sub-tree and output each visited node while pushing it in on the stack until the leftmost node has been visited.
3.If the right subtree is not null, pop the stack, then visit that sub-tree. Output that visited node while pushing it on the stack. If null, pop the stack.
4.Do 2 and 3 until the stack is empty.
Inorder traversal
1.define a stack
2.traverse the left sub-tree and push each visited node on the stack until the leftmost node has been visited.
3.If the right sub-tree in not null, pop the stack and output it, then visit the right sub-tree and push it on the stack. If null, pop the stack and output it.
4.Do 2 and 3 until the stack is empty.
Postorder traversal
1.define a stack
2.traverse the left sub-tree and push each visited node on the stack until the leftmost node has been visited.
3.If the right sub-tree in not null, visit the right sub-tree and push it on the stack. If null, pop the stack and output it.
4.Do 2 and 3 until the stack is empty.
Binary Search Tree in C++
A Binary search tree is a binary tree. It may be empty. If it not empty, then it satisfies the following properties.
1.Every element has a key and no two elements have the same key.
2.The keys in the left subtree are smaller than the key in the root.
3.The keys in the right subtree are larger than the key in the root.
4.The left and right subtrees are also binary search trees.
ADT of Binary Search Tree
AbstractDataType bsTree
{
instances
binary trees, each node has a pair whose first component is a key and whose second component is the value associated with the key; all keys are distinct; keys in the left subtree of any node are smaller than the key in the node; those in the right subtree are larger.
operations
find(k) :return the pair with the key k.
insert(p) :insert the pair p into the search tree
erase(k) :delete the pair with key k;
ascend( ):output all pairs in ascending order of key.
}
A binary search tree can support the operations search, insert and delete among others.
Searching a binary search tree : since the definition of a binary search tree is recursive, it is easier to write a recursive search procedure.
Insertion into a binary search tree
If the root is 0, then the search tree contains no elements and the search is unsuccessful. Otherwise, we compare x with the key in the root. If x equals the key, then the search terminates successfully. If x is less than the key in the root, then no element in the right subtree can have key value x, and only the left subtree is to be searched. If x is larger than the key in the root, only the right subtree needs to be searched.
6.Write C++ programs that use non-recursive functions to traverse the given binary tree in
a) Preorder
b) inorder and
c) postorder.
#include<iostream.h>
#include<conio.h>
struct node
{
node *lchild;
int data;
node *rchild;
// friend class bintree;
};
class stack
{
int m;
int top;
node **s;
public :
stack(int);
void push(node *);
node * pop();
int isempty();
int isfull();
// void display();
// ~stack();
};
stack::stack(int maxsize)
{
m=maxsize;
top=-1;
s=new node*[m];
}
void stack::push(node *x)
{
if(isfull())
cout<<"Stack is full"<<endl;
else
{
top++;
s[top]=x;
}
}
node* stack ::pop()
{
/* if(isempty())
return -1;
else*/
{
node *x=s[top];
top--;
return x;
}
}
int stack::isempty()
{
if(top==-1)
return 1;
else
return 0;
}
int stack :: isfull()
{
if(top==m-1)
return 1;
else
return 0;
}
/*void stack::display()
{
if(isempty())
cout<<"Empty list"<<endl;
else
{
for(int i=top;i>=0;i--)
cout<<s[i]<<" ";
cout<<endl;
}
}
stack::~stack()
{
delete [] s;
}*/
class bintree
{
node *root;
public:
bintree();
void create(int);
void del(int x);
void preorder();
void preorder(node*);
void inorder(node*);
void postorder(node*);
void traversal();
int nodect();
int leafct();
int nle(node *);
int depth(node *);
};
bintree::bintree()
{
root=0;
}
void bintree::del(int x)
{
node *head;
node *pre,*p,*q;
head= new node;
head->lchild=root;
head->rchild=0;
pre=head;
p=pre->lchild;
while((p!=0)&&(p->data!=x))
{
pre=p;
if(x<p->data)
p=p->lchild;
else
p=p->rchild;
}
if((pre->rchild==p)&&(p->rchild==p->lchild))
pre->rchild=0;
else if((pre->lchild==p)&&(p->rchild==p->lchild))
pre->lchild=0;
else if(p->rchild==0)
pre->lchild=p->lchild;
else if(p->lchild==0)
pre->rchild=p->rchild;
else if((p->lchild!=0)&&(p->rchild!=0))
{
if(pre->lchild==p)
{
pre->lchild=p->rchild;
//node *q;
q=p->rchild;
while(q->lchild!=0)
q=q->lchild;
q->lchild=p->lchild;
}
else if(pre->rchild==p)
{
pre->rchild=p->rchild;
q=p->rchild;
while(q->lchild!=0)
q=q->lchild;
q->lchild=p->lchild;
}
}
cout<<"\n"<<p->data<<endl;
delete p;
root=head->lchild;
delete head;
}
void bintree::create(int x)
{
node *p,*temp,*parent;
p=new node;
p->data=x;
p->lchild=0;
p->rchild=0;
if(root==0)
root=p;
else
{
temp=root;
while(temp!=0)
{
parent=temp;
if(p->data<temp->data)
temp=temp->lchild;
else
temp=temp->rchild;
}
if(p->data<parent->data)
parent->lchild=p;
else
parent->rchild=p;
}
}
void bintree:: traversal()
{
int ch,x;
cout<<"Enter your choice"<<endl;
cout<<"1,4.preorder"<<endl;
cout<<"2. inorder"<<endl;
cout<<"3. postorder"<<endl;
cout<<"5. number of lev.."<<endl;
cout<<"6. depth of tree is "<<endl;
cout<<"7. delete the element...."<<endl;
cin>>ch;
while(ch<8)
{
switch(ch)
{
case 1:
preorder();
break;
case 2:
inorder(root);
break;
case 3:
postorder(root);
break;
case 4:
preorder(root);
break;
case 5:int r=nle(root);
cout<<"rec leaves are " <<r<<endl;
break;
case 6:r=depth(root);
cout<<"rec depth of tree... " <<r<<endl;
break;
case 7:cout<<"in order "<<endl;
inorder(root);
cout<<"\n enter the ele...."<<endl;
cin>>x;
del(x);
cout<<"\n after del..\n";
inorder(root);
break;
}
cout<<"enter your choice"<<endl;
cin>>ch;
}
}
void bintree:: preorder()
{
stack st(10);
node *p=root;
st.push(0);
while(p!=0)
{
cout<<p->data<<" ";
if(p->rchild!=0)
st.push(p->rchild);
if(p->lchild!=0)
p=p->lchild;
else
p=st.pop();
}
cout<<endl;
}
int bintree:: nodect()
{
stack st(10);
node *p=root;
st.push(0);
int count=0;
while(p!=0)
{
count++;
if(p->rchild!=0)
st.push(p->rchild);
if(p->lchild!=0)
p=p->lchild;
else
p=st.pop();
}
cout<<endl;
return count;
}
int bintree:: leafct()
{
stack st(10);
node *p=root;
st.push(0);
int count=0;
while(p!=0)
{
if((p->lchild==0)&&(p->rchild==0))
count++;
if(p->rchild!=0)
st.push(p->rchild);
if(p->lchild!=0)
p=p->lchild;
else
p=st.pop();
}
cout<<endl;
return count;
}
int bintree::nle(node *root)
{
node *p;
p=root;
if(p==0)
return(0);
else
if(p->lchild==p->rchild)
return(1);
else
return((nle(p->lchild))+(nle(p->rchild)));
}
int max(int x,int y)
{ if(x>y)
return(x);
else
return(y);
}
int bintree::depth(node *root)
{
node *p;
p=root;
if(p==0)
return(0);
else
if(p->lchild==p->rchild)
return(0);
else
return(1+max(depth(p->lchild),depth(p->rchild)));
}
void bintree:: inorder(node *temp)
{
if(temp!=0)
{
inorder(temp->lchild);
cout<<temp->data<<" ";
inorder(temp->rchild);
}
}
void bintree:: preorder(node *temp)
{
if(temp!=0)
{ cout<<temp->data<<" ";
preorder(temp->lchild);
preorder(temp->rchild);
} }
void bintree:: postorder(node *temp)
{
if(temp!=0)
{
postorder(temp->lchild);
postorder(temp->rchild);
cout<<temp->data<<" ";
}
}
void main()
{
clrscr();
int x,r;
char ch='y';
bintree bt;
while(ch=='y')
{
cout<<"Enter the element";endl;
cin>>x;
bt.create(x);
cout<<"Do u want to continue"<<endl;
cin>>ch;
}
r=bt.nodect();
cout<<"No of nodes are "<<r<<endl;
r=bt.leafct();
cout<<"No of leaves are "<<r<<endl;
bt.traversal();
getch();
}
No comments:
Post a Comment