Help with creating code for Binary Tree? Looking at the figure, struct a Tree: H
ID: 3786835 • Letter: H
Question
Help with creating code for Binary Tree?
Looking at the figure, struct a Tree:
Here is the header file :
#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
//#include <Windows.h>
#include <list>
#include <string>
typedef std::string Elem; // base element type
class BinaryTree {
protected:
struct Node { // a node of the tree
Elem elt; // element value
Node* par; // parent
Node* left; // left child
Node* right; // right child
Node() : elt(), par( NULL ), left( NULL ), right( NULL ) {} // constructor
};
public:
class Position { // position in the tree
private:
Node* v; // pointer to the node
public:
Position( Node* _v = NULL ) : v( _v ) {} // constructor
Elem& operator*() const // get element
{
return v->elt;
}
Position left() const // get left child
{
return Position( v->left );
}
Position right() const // get right child
{
return Position( v->right );
}
Position parent() const // get parent
{
return Position( v->par );
}
bool isRoot() const // root of the tree?
{
return v->par == NULL;
}
bool isExternal() const // an external node?
{
return v->left == NULL && v->right == NULL;
}
friend class BinaryTree; // give tree access
};
typedef std::list<Position> PositionList; // list of positions
public:
BinaryTree(); // constructor
int size() const; // number of nodes
bool empty() const; // is tree empty?
Position root() const; // get the root
PositionList positions() const; // list of nodes
void addRoot(); // add root to empty tree
void expandExternal( const Position& p ); // expand external node
Position removeAboveExternal( const Position& p ); // remove p and parent
// housekeeping functions omitted...
protected: // local utilities
void preorder( Node* v, PositionList& pl ) const; // preorder utility
private:
Node* _root; // pointer to the root
int n; // number of nodes
};
#endif // _BINARYTREE_H_
// 4 7 3 2 5 9 3 3Explanation / Answer
//EXAMPLE PROGRAM FOR BINARY TREE
# include <iostream.h>
# include <stdlib.h>
# include <conio.h>
struct node
{
node *left;
int item;
node *right;
};
class btree
{
public:
void create(node *record,int n)
{
if(n > record->item)
{
if(record->right==NULL)
{
record->right=new node;
record=record->right;
record->item=n;
record->left=NULL;
record->right=NULL;
}
else
create(record->right,n);
}
else
{
if(n<record->item)
{
if(record->left==NULL)
{
record->left=new node;
record=record->left;
record->item=n;
record->left=NULL;
record->right=NULL;
}
else
create(record->left,n);
}
else
cout<<" No. is duplicate ";
return;
}
}
void inorder(node *record)
{
if(record!=NULL)
{
inorder(record->left);
cout<<record->item<<" ";
inorder(record->right);
}
return;
}
void preorder(node *record)
{
if(record!=NULL)
{
cout<<record->item<<" ";
preorder(record->left);
preorder(record->right);
}
return;
}
void postorder(node *record)
{
if(record!=NULL)
{
postorder(record->left);
postorder(record->right);
cout<<record->item<<" ";
}
}
};
void main()
{
node *tree;
btree b;
int num,choice;
clrscr();
tree=new node;
cout<<" BINARY TREE TRAVERSAL ";
cout<<" 1. INORDER ";
cout<<" 2. PREORDER ";
cout<<" 3. POSTORDER ";
cout<<" 4. EXIT ";
cout<<" First enter the no's at last enter -999 ";
cin>>num;
tree->item=num;
tree->left=NULL;
tree->right=NULL;
while(num!=-999)
{
cin>>num;
if(num==-999)
break;
b.create(tree,num);
}
do
{
cout<<" Enter your choice ";
cin>>choice;
switch(choice)
{
case 1:
cout<<" Inorder Traversal ";
b.inorder(tree);
continue;
case 2:
cout<<" Preorder Traversal ";
b.preorder(tree);
continue;
case 3:
cout<<" Postorder Traversal ";
b.postorder(tree);
continue;
}
}
while(choice!=4);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.