Respuesta :
Answer:
//Stack template
template <class T>
class BinaryTree
{
private:
struct TreeNode
{
T value; //The value in the node
TreeNode *left; //Pointer to left child node
TreeNode *right; //Pointer to right child node
};
TreeNode *root; //Pointer to the root node
//Private member functions
void insert(TreeNode*&, TreeNode *&);
void destroySubTree(TreeNode *);
void deleteNode(T, TreeNode *&);
void makeDeletion(TreeNode *&);
void displayInOrder(TreeNode *) const;
void displayPreOrder(TreeNode *) const;
void displayPostOrder(TreeNode *) const;
int counter(TreeNode *);
int leafCounter(TreeNode *);
int getTreeHeight(TreeNode* nodePtr);
int countNodes(TreeNode *&nodePtr) ;
int countLeaves(TreeNode* nodePtr);
public:
//Constructor
BinaryTree()
{root = NULL;}
//Destructor
~BinaryTree ()
{destroySubTree(root);}
//Binary tree operations
void insertNode(T);
bool searchNode(T);
void remove(T);
int treeHeight();
int numNodes();
int numLeafNodes();
void displayInOrder() const
{displayInOrder(root);}
void displayPreOrder() const
{displayPreOrder(root);}
void displayPostOrder() const
{displayPostOrder(root);}
// Node counter
int counter()
{
int n = counter(root);
return n;
}
// Leaf counter
int leafCounter()
{
int leaf = leafCounter(root);
return leaf;
}
// Height of the tree
int height()
{
int h = treeHeight();
return h;
}
};
//**********************************************************
//Insert accepts a TreeNode pointer and a pointer to a node*
//The function inserts the node into the tree pointed to by*
//the TreeNode pointer. This function is called recursively*
//**********************************************************
template <class T>
void BinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
if (nodePtr == NULL)
nodePtr = newNode; // Insert the node
else if (newNode->value < nodePtr->value)
insert(nodePtr->left, newNode); // Search the left branch
else
insert(nodePtr->right, newNode);// Search the right branch
}
//*******************************************************
//insertNode create as new node to hold num as its value*
//and passes it to the insert function. *
//*******************************************************
template <class T>
void BinaryTree<T>::insertNode(T item)
{
TreeNode *newNode; //Pointer to a new node
//Create a new node and store num in it
newNode = new TreeNode;
newNode->value = item;
newNode->left = newNode->right = NULL;
//Insert the node
insert(root, newNode);
}
//***********************************************
//destroySubTree is called by the destructor. It*
//deletes all nodes in the tree *
//***********************************************
template <class T>
void BinaryTree<T>::destroySubTree(TreeNode *nodePtr)
{
if (nodePtr)
{
if (nodePtr->left)
destroySubTree(nodePtr->left);
if (nodePtr->right)
destroySubTree(nodePtr->right);
delete nodePtr;
}
}
//***********************************************
//searchNode determines if a value is present in*
//the tree. If so, the function returns true. *
//Otherwise, it returns false. *
//***********************************************
template <class T>
bool BinaryTree<T>::searchNode(T item)
{
TreeNode *nodePtr = root;
while (nodePtr)
{
if (nodePtr->value == item)
return true;
else if (item < nodePtr->value)
nodePtr = nodePtr->left;
else
nodePtr = nodePtr->right;
}
return false;
}
//**********************************************
//remove calls deleteNode to delete the *
//node whose value member is thedame as num *
//**********************************************
template <class T>
void BinaryTree<T>::remove(T item)
{
deleteNode(item, root);
}
//**********************************************
//deleteNode deletes the node whose value *
//memeber id the same as num *
//**********************************************
template <class T>
void BinaryTree<T>::deleteNode(T item, TreeNode *&nodePtr)
{
if (item < nodePtr->value)
deleteNode(item, nodePtr->left);
else if (item > nodePtr->value)
deleteNode(item, nodePtr->right);
else
makeDeletion(nodePtr);
}
