Homework SourseBinary Tree implementing main function help Header File Ple
Binary Tree implementing main function help :
Header File: Please do correct if something is wrong or needs to be excluded.
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <list>
#include <iostream>
#include <cstdlib>
#include <algorithm>
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;
};
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.
int height() const; // Returns height of the tree
int depth() const; // Returns depth of the tree
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.
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
Position removeAboveExternal(const Position& p); //remove p and parent
private:
Node <E> * _root; // pointer to the root
int n; // number of nodes
};
template <typename E> int BinaryTree<E>::size() const { return n; }
template <typename E> bool BinaryTree<E>::empty() const { return size() == 0; }
template <typename E> typename BinaryTree<E>::Position BinaryTree<E>::root() const { return Position(_root); }
template <typename E> int BinaryTree<E>::height() const { return height() == 0; }
template <typename E> int BinaryTree<E>::depth() const { return depth() == 0; }
template <typename E>
void BinaryTree<E>::expandExternal(const Position& p) {
Node* v = p.v;
v->left = new Node;
v->left->par = v;
v->right = new Node;
v->right->par = v;
n += 2;
}
template <typename E>
typename BinaryTree<E>::Position BinaryTree<E>::removeAboveExternal(const Position& p) {
Node* w = p.v;
Node* v = w->par;
Node* sib = (w == v->left ? v->right : v->left);
if (v == _root) {
_root = sib;
sib->par = NULL;
}
else {
Node* gpar = v->par;
if (v == gpar->left) gpar->left = sib;
else gpar->right = sib;
sib->par = gpar;
}
delete w; delete v;
n -= 2;
return Position(sib);
}
template <typename E>
typename BinaryTree<E>::PositionList BinaryTree<E>::positions() const {
PositionList pl;
preorder(_root, pl);
return PositionList(pl);
}
template <typename E>
void BinaryTree<E>::preorder(Node<E>* v, PositionList& pl) const {
pl.push_back(Position(v));
if (v->left != NULL) preorder(v->left, pl);
if (v->right != NULL) preorder(v->right, pl);
}
#endif
Main.cpp :
#include <list>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include \"BinaryTree.h\"
using namespace std;
template<typename E>
int depth(const BinaryTree<int> & T, const BinaryTree<int>::Position& p)
{
BinaryTree<E> TreeDepth;
if (!TreeDepth.empty())
{
if (TreeDepth.empty())
return 0;
if (v->left == NULL && v->right == NULL)
return 1;
if (!v->left)
return depth(v->right) + 1;
if (!v->right)
return depth(v->left) + 1;
}
return ((max(depth(v->left), depth(v->right)) + 1));
}
template<typename E>
int height(const BinaryTree<int>& T)
{
BinaryTree<E> treeHeight;
if (!treeHeight.empty())
return 0;
return (max(height(v->left), height(v->right)));
}
int main(void)
{
BinaryTree<int> myTree;
return EXIT_SUCCESS;
}
I need to implement depth() and height() fucntion in the main function.
Is this right? If not, can canyone help to fix it? thank you
Solution
#include
