\"Templated Binary Tree\" implementing function help ? I need to implement heade

Question

"Templated Binary Tree" implementing function help ?

I need to implement header file which i am working on.

Void expandExternal and void preorder part :

1. Header File :

#ifndef BINARYTREE_H
#define BINARYTREE_H

#include <list>

////////////////////////////////////
// Templated Node Interface
///////////////////////////////////
template <typename E>           // base element type
class Node {             // a node of the tree
public:
Node() : elt(), par(NULL), left(NULL), right(NULL) { }  // constructor

private:
E    elt;             // element value
Node*   par;            // parent
Node*   left;            // left child
Node*   right;            // right child

template <class U> friend class BinaryTree;
template <class U> friend class Position;
};

////////////////////////////////////
// Templated Binary Tree Interface
///////////////////////////////////

template <typename E>      // base element type
class BinaryTree
{
public:                   // public types

//Defines a node position
class Position
{
public:
  Position(Node <E>* _v = NULL) : v(_v) { }  // constructor

  //Returns the element at the position
  E& operator*()
  {
   return v->elt;
  }

  //Returns a Position object
  Position left() const    // get left child
  {
   return Position(v->left);
  }

  //Returns a Position object
  Position right() const    // get right child
  {
   return Position(v->right);
  }

  //Returns a Position object
  Position parent() const    // get parent
  {
   return Position(v->par);
  }

  //Returns true or false
  bool isRoot() const    // root of tree?
  {
   return v->par == NULL;
  }

  //Returns true or false
  bool isExternal() const    // an external node?
  {
   return v->left == NULL && v->right == NULL;
  }

  //Returns true or false
  bool isInternal() const    // an external node?
  {
   return ! isExternal();
  }

private:
  Node<E>* v;
  template <class U> friend class BinaryTree;
};//End Position class definition

/* Position List type definition*/

typedef std::list<Position> PositionList;

public: //Binary member functions
BinaryTree() : _root(NULL), n(0) { }
~BinaryTree();   // The destructor need to properly deletes all nodes in the tree to prevent memory leaks.

int size() const;  // Returns and integer tof the number of nodes.

bool empty() const;  // Returns a true if the tree is empty else false.
Position root() const; // Return the position of the root node.
void addRoot();   // Creates and adds the initial root node to the tree this must be added first.

void expandExternal(const Position& p);    //Expands each external node with a left and right child that are empty.

//            What goes here?

PositionList positions() const;      // Returns a std:list of the nodes in the tree call preorder() function.
void preorder(Node<E>* v, PositionList& pl) const; // Traversal algorithm for the tree to populate the PositionList

//              What goes here?

private:
Node <E> * _root;         // pointer to the root
int n;            // number of nodes
};

#endif

Thank you

Explanation / Answer

for the main function, try writing the code like this :

struct Node{

Comparable element;
Node *left;
Node *right;
Node(const Comparable & theElement, Node *lt, Node *rt )
: element( theElement ), left( lt ), right( rt ) {}
}; // Node{}
Node *root;
Node * findMin( Node *t ) const;   
Node * findMax( Node *t ) const;

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.