Main.cpp #include <iostream> using namespace std; // General tree node ADT *****
ID: 3817539 • Letter: M
Question
Main.cpp
#include <iostream>
using namespace std;
// General tree node ADT ************************************************************************
template <typename E>
class GTNode
{
private:
E element;
GTNode<E> *Parent;
GTNode<E> *leftChild;
GTNode<E> *rightSib;
public:
// Constructor
GTNode(const E& v)
{
Parent = leftChild = rightSib = NULL;
element = v;
}
// Constructor
GTNode(const E& v, GTNode<E>* par)
{ element=v, leftChild=rightSib=NULL, Parent=par;}
// Return nodes value
E value() { return element; }
// True if node is a leaf
bool isLeaf()
{ return leftChild == NULL; }
// Return node's parent
GTNode* parent()
{ return Parent; }
// Return node's first child
GTNode* leftmostChild()
{ return leftChild; }
// Return node's right sibling
GTNode* rightSibling()
{ return rightSib; }
// Set node's value
void setValue(E& val)
{ element = val; }
// Insert as the first child
void insertFirst(GTNode<E>* n)
{
n->rightSib = leftChild;
n->Parent = this;
leftChild = n;
}
// Insert as the right sibling
void insertNext(GTNode<E>* n)
{
n->rightSib = rightSib;
n->Parent = Parent;
rightSib = n;
}
// Remove first child from tree
void removeFirst()
{
if (leftChild == NULL) return;
GTNode<E>* temp = leftChild;
leftChild = leftChild->rightSib;
delete temp;
}
// Remove right sibling from tree
void removeNext()
{
if (rightSib == NULL) return;
GTNode<E>* temp = rightSib;
rightSib = rightSib->rightSib;
delete temp;
}
};
// General tree ADT ************************************************************************
template <typename E>
class GTree
{
private:
GTNode<E> *root;
void print_postorder_Help(GTNode<E> *rt)
{
// ********** Student code ******************
}
public:
// Constructor
GTree() { root=NULL;}
// Send all nodes to free store
void clear() { root = NULL; }
// Return the root of the tree
GTNode<E>* Root() { return root; }
// Combine two trees
void newroot(GTNode<E> *rt)
{
clear();
root=rt;
}
int depth(GTNode<E> * t)
{
// ********** Student code ******************
}
// Print a tree
void print_postorder() { print_postorder_Help(root); }
};
int main()
{
// ********** Student code ******************
/* ======================================= This is an example ====================================================
//create a Tree
GTree<char> gt;
//create some node
GTNode<char> *nA, *nB, *nC, *nD;
nA= new GTNode<char>('A', NULL); nB= new GTNode<char>('B', NULL); nC= new GTNode<char>('C', NULL);nD= new GTNode<char>('D', NULL);
gt.newroot(nA);
// connect nodes
nA->insertFirst(nD);
nA->insertFirst(nC);
nA->insertFirst(nB);
// display the tree
cout<<"The Original Tree: ";
gt.print_preorder();
cout<<endl<<endl;
// display the sequential representation
cout<<"The Sequential Tree: ";
gt.print_sequential();
cout<<endl<<endl;
===================================================================================================================== */
}
Explanation / Answer
2. A Binary Search Tree(BST) is a tree in which all the nodes have certain properties
The Basic operations of a Binary search tree are
/*IMPLEMENTATION OF BINARY SEARCH TREE.*/
#include<iostream.h>
#include<conio.h>
template <class T>
class bst //declaration of class to create Node.
{
private:
T data;
bst *leftchild;
bst *rightchild,*root;
public:
bst()
{
root=NULL;
}
bst *top()
{
return root;
}
void insert(T);
void deletion(T);
void find(T);
};
template <class T>
void bst<T>::insert(T x)
{
bst *p,*pp;//pp holds parent node address
p=root;
pp=NULL;
while(p!=NULL)
{
pp=p;
if(x<p->data)
p=p->leftchild;
else
p=p->rightchild;
}
bst *nn;//nn means newnode
nn= new bst;
nn->data=x;
nn->leftchild=nn->rightchild=NULL;
if(root==NULL)
{
root =nn;
return;
}
if(x<pp->data)
pp->leftchild=nn;
else
pp->rightchild=nn;
}
//Deletion Operation
template <class T>
void bst<T>::deletion(T x)
{
bst *p,*pp;
p=root;
pp=NULL;
//find whether the given element available or not.
while(p!=NULL&&p->data!=x)
{
pp=p;
if(x<p->data)
p=p->leftchild;
else
p=p->rightchild;
}
if(p==NULL)
{
cout<<" element Not Found ";
return;
}
//deleting node with two childrens.
if(p->leftchild!=NULL&&p->rightchild!=NULL)
{
bst *s=p->leftchild;//s holds root of left subtree of deleting element p.
bst *ps=p; //ps holds address of parent of s.
//finding largest element of left subtree.
while(s->rightchild!=NULL)
{
ps=p;
s=s->rightchild;
}
cout<<"deleting node has two childrens ->"<<p->data;
delete p;
p->data=s->data;
p=s;
pp=ps;
return;
}
if(p->leftchild==NULL&&p->rightchild==NULL)
{
if(pp==NULL)
{
root=NULL;
cout<<" Deleted node is root -> "<<p->data;
delete p;
return;
}
if(pp->leftchild==p)
{
pp->leftchild=NULL;
cout<<"Deleting node is left leaf: ->"<<p->data;
delete p;
return;
}
else
{
pp->rightchild=NULL;
cout<<"Deleting node is right leaf: ->"<<p->data;
delete p;
return;
} }
//P Has either Left or right Child
bst *c;
if(p->leftchild!=NULL)
c=p->leftchild;
else
c=p->rightchild;
if(p==root)
{
root=c;
}
else
{
if(p==pp->leftchild)
{
pp->leftchild=c;
cout<<"Deleting node has one left sub-tree ->"<<p->data;
delete p;
return;
}
else
{
pp->rightchild=c;
cout<<"Deleted node has one right sub-tree ->"<<p->data;
delete p;
return;
}
}
}
template<class T>
void bst<T>::find(T x)
{
bst *p;
if(root==NULL)
{
cout<<"TREE EMPTY";
}
else
{
p=root;
while(p!=NULL)
{
if(x<p->data) //if key element is less than root then search towords left child
p=p->leftchild;
else
if(x>p->data) //if key element greater than root find right subtree.
p=p->rightchild;
else
{
cout<<" Element Found ie:"<<p->data;
break;
} }}
if(p==NULL)
cout<<" element not found ";
}
void main()
{
clrscr();
bst<int> bs;
int op,x,y;
do
{ cout<<" 1.insert 2.deletion 3.find 4.exit: ";
cout<<" enter your chioce: ";
cin>>op;
switch(op)
{
case 1:cout<<" enter element to insert: ";
cin>>x;
bs.insert(x);
break;
case 2:cout<<" enter element to delete: ";
cin>>y;
bs.deletion(y);
break;
case 3: cout<<"Enter element to Find: ";
cin>>x;
bs.find(x);
break;
case 4:break;
}
}while(op!=4);
getch();
}
3. a)Post -order Traversal
In post-order Traversal method ,we traverse the left subtree,then right subtree and finally the root node.
#include<iostream.h>
#include<conio.h>
template<class T>
class node
{
public:
T data;
node *lptr,*rptr;
};
template<class T>
class bst:public node<T>
{
public:
node<T> *root,*temp;
bst()
{
root=NULL;
}
void create(int);
void inorder(node<T> *root);
void preorder(node<T> *root);
void postorder(node<T> *root);
};
template<class T>
void bst<T>::create(int x)
{
T x1;
node<T> *newnode,*part;
for(int i=0;i<x;i++)
{
newnode=new node<T>;
cout<<"enter element"<<endl;
cin>>x1;
newnode->data=x1;
newnode->lptr=NULL;
newnode->rptr=NULL;
if(root==NULL)
root=newnode;
else
{
temp=root;
while(temp!=NULL)
{
part=temp;
if(newnode->data>temp->data)
temp=temp->rptr;
else
if(newnode->data<temp->data)
temp=temp->lptr;
else
cout<<"element not inserted";
}
if(newnode->data<part->data)
part->lptr=newnode;
else
part->rptr=newnode;
}}}
template<class T>
class stack:public node<T>
{
int top;
node<T> *s[100];
public:
stack()
{
top=-1;
}
void push(node<T> *n)
{
s[++top]=n;
}
node<T> *pop()
{
return s[top--];
}
int isempty()
{
if(top==-1)
return(1);
else
return(0);
} };
template<class T>
void bst<T>::inorder(node<T> *root)
{
stack<T> s1;
node<T> *temp;
if(root!=NULL)
{
temp=root;
do
{
while(temp!=NULL)
{
s1.push(temp);
temp=temp->lptr;
}
if(!s1.isempty())
{
temp=s1.pop();
cout<<temp->data<<" ";
temp=temp->rptr;
}
else
break;
}
while(1);
}
else
cout<<"EMPTY TREE";
}
template<class T>
void bst<T>::preorder(node<T> *root)
{
stack<T> s1;
node<T> *temp;
temp=root;
s1.push(temp);
while(!s1.isempty())
{
temp=s1.pop();
if(temp!=NULL)
{
cout<<temp->data<<" ";
s1.push(temp->rptr);
s1.push(temp->lptr);
} } }
void main()
{
clrscr();
bst<int> b;
b.create(5);
cout<<"INORDER";
b.inorder(b.root);
cout<<"Preorder";
b.preorder(b.root);
cout<<"POSTORER";
b.postorder(b.root);
getch();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.