TITLE IMPLEMENTING AND MANIPULATING EXPRESSION TREES INTRODUCTION A binary tree
ID: 3767533 • Letter: T
Question
TITLE
IMPLEMENTING AND MANIPULATING EXPRESSION TREES
INTRODUCTION
A binary tree is a tree in which each node may have up to two children, and these children are distinguished as the left child and the right child. Binary trees may represent arithmetic expressions involving binary operators. Expressions represented in this way are easy to process recursively, and an expression tree can be scanned to produce preorder, inorder, and postorder versions of the expression it represents.
DESCRIPTION
Implement a program that implements and exercises expression trees. Use a (non-template) class to provide an ExpressionTree type. The class will implement the tree type as a linked binary tree. Interior nodes will hold operators --- +, -, *, / --- and leaves will hold operands; that is, the values of single digits: 0, 1, 2, ... , 9. The main program will open a file, named by the user, that contains fully parenthesized infix expressions, one per line. These expressions must use single digits as numerical operands. The program will then call class member functions to print prefix, infix, and postfix versions of each expression and its integer value.
INPUT
The program will read the name of the input file from the terminal and infix expressions from the named file. White space in the input expressions should have no effect on the results.
OUTPUT
The program will prompt for the name of the data file and will print to the terminal prefix, infix, and postfix versions of the expressions read from the data file as well as their values.
ERRORS
The program can assume that the input is as described, in particular that data files contain correct fully-parenthesized infix expressions. The program should be able to handle white space in the input file. Otherwise, it need not detect any errors.
EXAMPLE
If the data file data.dat contains these lines:
then a run of the program might look like this:
OTHER REQUIREMENTS
The implementation of the ExpressionTree type must be encapsulated in a class. In addition to a default constructor, a destructor, and a function that re-initializes an existing tree to be empty, the class must include these functions:
build_tree(in_f) - Read a fully-parenthesized infix expression from the file in_f and build the corresponding expression tree. The invoking tree becomes the expression tree.
pre_order(out_f) - Print to the output stream out_f the prefix version of the expression that the invoking tree represents.
in_order(out_f) - Print to the output stream out_f the infix version of the expression that the invoking tree represents.
post_order(out_f) - Print to the output stream out_f the postfix version of the expression that the invoking tree represents.
value() - Return the integer value of the expression that the invoking tree represents.
Write recursive procedures to carry out the three printing operations, and note that the infix procedure must print left and right parentheses at the appropriate times. The evaluation and tree-building functions must also be recursive.
Do NOT use the examples above as test cases for your program. You must design your own tests.
HINTS
When recursive functions operate on pointer-based class objects, as here, there must be two functions: a public one and a recursive private one that the public one calls.
Explanation / Answer
#include <iostream.h>
#include <stdlib.h>
enum {TRUE = 1,FALSE = 0};
typedef struct _node
{
int info;
struct _node *left;
struct _node *right;
}node;
class btree
{
private:
node *root;
void InsertLeft(node* & ,node*);
void InsertRight(node* &,node*);
public:
btree();
node* GetRoot(void);
void MakeTree(void);
void DisplayTree(node*,int);
void Inorder(node* );
void Preorder(node*);
void Postorder(node*);
};
btree::btree()
{
char create='Y';
root = new node;
cout<<"Enter a number which will become a root"<<endl;
cin>>root->info;
root->left = NULL;
root->right = NULL;
}
node* btree::GetRoot(void)
{
return(root);
}
void btree::MakeTree(void)
{
node *newnode;
char create;
do
{
newnode = new node;
cout<<"Enter a number"<<endl;
cin>>newnode->info;
newnode->left=NULL;
newnode->right=NULL;
if(newnode->info < root->info)
InsertLeft(newnode,root);
else
InsertRight(newnode,root);
cout<<"Create another node[y/n]"<<endl;
cin>>create;
}while(create=='Y' || create=='y');
}
void btree::InsertLeft(node* &newnode,node* current)
{
if(current->left==NULL)
current->left=newnode;
else
{
current = current->left;
if(newnode->info < current->info)
InsertLeft(newnode,current);
else
InsertRight(newnode,current);
}
}
void btree::InsertRight(node* &newnode,node* current)
{
if(current->right==NULL)
current->right=newnode;
else
{
current = current->right;
if(newnode->info < current->info)
InsertLeft(newnode,current);
else
InsertRight(newnode,current);
}
}
void btree::DisplayTree(node *current,int Level)
{
if(current)
{
DisplayTree(current->right,Level+1);
cout<<endl;
for(int i=0;i<Level;i++)
cout<<" ";
cout<<current->info;
DisplayTree(current->left,Level+1);
}
}
void btree::Inorder(node *current)
{
if(current!=NULL)
{
Inorder(current->left);
cout<<current->info;
Inorder(current->right);
}
}
void btree::Preorder(node *current)
{
if(current!=NULL)
{
cout<<current->info;
Preorder(current->left);
Preorder(current->right);
}
}
void btree::Postorder(node *current)
{
if(current!=NULL)
{
Postorder(current->left);
Postorder(current->right);
cout<<current->info;
}
}
void main()
{
int opt;
int num;
char ch='y';
btree bt;
do
{
cout<<" Enter your option ";
cout<<"1. Make a Tree ";
cout<<"2. display the tree ";
cout<<"3. Inorder traversal ";
cout<<"4. preorder traversal ";
cout<<"5. postorder traversal ";
cout<<"6. Exit ";
cin>>opt;
switch(opt)
{
case 1:
bt.MakeTree();
break;
case 2:
bt.DisplayTree(bt.GetRoot(),1);
break;
case 3:
bt.Inorder(bt.GetRoot());
break;
case 4:
bt.Preorder(bt.GetRoot());
break;
case 5:
bt.Postorder(bt.GetRoot());
break;
case 6:
exit(0);
default:
cout<<" Invalid Entry ";
}
}while(ch=='Y' || ch=='y');
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.