I need help creating main function for BinaryTree : Here are the header files :
ID: 3786695 • Letter: I
Question
I need help creating main function for BinaryTree :
Here are the header files :
PrintExpressionTour.H:
#ifndef _PRINTEXPRESSIONTOUR_H_
#define _PRINTEXPRESSIONTOUR_H_
#include "EulerTour.h"
#include <iostream>
template <typename E, typename R>
class PrintExpressionTour : public EulerTour<E, R> {
protected: // ...same type name shortcuts as in EvaluateExpressionTour
public:
inline void execute( const BinaryTree& T ) { // execute the tour
initialize( T );
std::cout << "Expression: "; eulerTour( T.root() ); std::cout << std::endl;
}
protected: // leaf: print value
virtual void visitExternal( const Position& p, Result& r ) const {
std::cout << *p;
}
// left: open new expression
virtual void visitLeft( const Position& p, Result& r ) const {
std::cout << "(";
}
// below: print operator
virtual void visitBelow( const Position& p, Result& r ) const {
std::cout << *p;
}
// right: close expression
virtual void visitRight( const BinaryTree::Position& p, Result& r ) const {
std::cout << ")";
}
};
#endif // _PRINTEXPRESSIONTOUR_H_
BinaryTree.h:
#ifndef _BINARYTREE_H_
#define _BINARYTREE_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_
EulerTour.h:
#ifndef _EULERTOUR_H_
#define _EULERTOUR_H_
#include "BinaryTree.h"
template <typename E, typename R> // element and result types
class EulerTour { // a template for Euler tour
protected:
struct Result { // stores tour results
R leftResult; // result from left subtree
R rightResult; // result from right subtree
R finalResult; // combined result
};
//typedef BinaryTree<E> BinaryTree; // the tree
typedef typename BinaryTree::Position Position; // a position in the tree
protected: // data member
const BinaryTree* tree; // pointer to the tree
public:
void initialize( const BinaryTree& T ) // initialize
{
tree = &T;
}
protected: // local utilities
R eulerTour( const Position& p ) const {
Result r = initResult();
if ( p.isExternal() ) { // external node
visitExternal( p, r );
} else { // internal node
visitLeft( p, r );
r.leftResult = eulerTour( p.left() ); // recurse on left
visitBelow( p, r );
r.rightResult = eulerTour( p.right() ); // recurse on right
visitRight( p, r );
}
return result( r );
} // perform the Euler tour who will implement this?
// functions given by subclasses
virtual void visitExternal( const Position& p, Result& r ) const {}
virtual void visitLeft( const Position& p, Result& r ) const {}
virtual void visitBelow( const Position& p, Result& r ) const {}
virtual void visitRight( const Position& p, Result& r ) const {}
Result initResult() const {
return Result();
}
R result( const Result& r ) const {
return r.finalResult;
}
};
#endif
BinaryTree.cpp:
#include "BinaryTree.h"
void BinaryTree::expandExternal( const Position& p ) {
Node* v = p.v; // p's node
v->left = new Node; // add a new left child
v->left->par = v; // v is its parent
v->right = new Node; // and a new right child
v->right->par = v; // v is its parent
n += 2; // two more nodes
}
BinaryTree::PositionList BinaryTree::positions() const {
PositionList pl;
preorder( _root, pl ); // preorder traversal
return PositionList( pl ); // return resulting list
}
// preorder traversal
void BinaryTree::preorder( Node* v, PositionList& pl ) const {
pl.push_back( Position( v ) ); // add this node
if ( v->left != NULL ) // traverse left subtree
preorder( v->left, pl );
if ( v->right != NULL ) // traverse right subtree
preorder( v->right, pl );
}
BinaryTree::BinaryTree() // constructor
: _root( NULL ), n( 0 ) {}
int BinaryTree::size() const // number of nodes
{
return n;
}
bool BinaryTree::empty() const // is tree empty?
{
return size() == 0;
}
BinaryTree::Position BinaryTree::root() const // get the root
{
return Position( _root );
}
void BinaryTree::addRoot() // add root to empty tree
{
_root = new Node; n = 1;
}
I need to make another "main.cpp" for this BinaryTree:
I have started with the following:
#include <cstdio>
#include <cstdlib>
#include "BinaryTree.h"
#include "PrintExpressionTour.h"
int main()
{
// Need help on this part creating code for the Tree...
system( "pause" );
return EXIT_SUCCESS;
}
Help Anyone? Thank you
// 4 7 3 2 5 9 3 3Explanation / Answer
Depth and Height
Þ n = 2ni + 1
Position p points to the same node storing the same object. Now, however, the formerly external node has two external children.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.