Question

write a program (in main.cpp) to do the following: a. build a binary search tree t1. b. do a postorder traversal of t1 and, while doing the postorder traversal, insert the nodes into a second binary search tree t2 . c. do a preorder traversal of t2 and, while doing the preorder traversal, insert the node into a third binary search tree t3. d. do an inorder traversal of t3. e. output the heights and the number of leaves in each of the three binary search trees.

Answer 1

Answer:

#include <iostream>

using namespace std;

struct TreeNode

{

   int value;

   TreeNode *left;

   TreeNode *right;

};

class Tree

{

  private:

     TreeNode *root;

     void insert(TreeNode *&, TreeNode *&);

     void destroySubTree(TreeNode *);

     void deleteNode(int, TreeNode *&);

     void makeDeletion(TreeNode *&);

     void displayInOrder(TreeNode *) const;

     void displayPreOrder(TreeNode *) const;

     void displayPostOrder(TreeNode *) const;

     int height(TreeNode *) const;

     int nodeCount(TreeNode *) const;

     int leafCount(TreeNode *) const;

  public:

     Tree()

        { root = NULL; }

     ~Tree()

        { destroySubTree(root); }

     void insertNode(int);

     bool searchNode(int);

     void remove(int);

     void displayInOrder() const

        { displayInOrder(root); }

     void displayPreOrder() const

        { displayPreOrder(root); }

     void displayPostOrder() const

        { displayPostOrder(root); }

     int height() const

        { return height(root); }

     int nodeCount() const

        { return nodeCount(root); }

     int leafCount() const

        { return leafCount(root); }

};

void Tree::insert(TreeNode *&nodePtr, TreeNode *&newNode)

{

  if (nodePtr == NULL)

     nodePtr = newNode;

  else if (newNode->value < nodePtr->value)

     insert(nodePtr->left, newNode);

  else

     insert(nodePtr->right, newNode);

}

void Tree::insertNode(int num)

{

  TreeNode *newNode;

  newNode = new TreeNode;

  newNode->value = num;

  newNode->left = newNode->right = NULL;

  insert(root, newNode);

}

void Tree::destroySubTree(TreeNode *nodePtr)

{

  if (nodePtr)

  {

     if (nodePtr->left)

        destroySubTree(nodePtr->left);

     if (nodePtr->right)

        destroySubTree(nodePtr->right);

     delete nodePtr;

  }

}

void Tree::deleteNode(int num, TreeNode *&nodePtr)

{

  if (num < nodePtr->value)

     deleteNode(num, nodePtr->left);

  else if (num > nodePtr->value)

     deleteNode(num, nodePtr->right);

  else

     makeDeletion(nodePtr);

}

void Tree::makeDeletion(TreeNode *&nodePtr)

{

  TreeNode *tempNodePtr;

  if (nodePtr == NULL)

     cout << "Cannot delete empty node.\n";

  else if (nodePtr->right == NULL)

  {

     tempNodePtr = nodePtr;

     nodePtr = nodePtr->left;

     delete tempNodePtr;

  }

  else if (nodePtr->left == NULL)

  {

     tempNodePtr = nodePtr;

     nodePtr = nodePtr->right;

     delete tempNodePtr;

  }

  else

  {

     tempNodePtr = nodePtr->right;

     while (tempNodePtr->left)

        tempNodePtr = tempNodePtr->left;

     tempNodePtr->left = nodePtr->left;

     tempNodePtr = nodePtr;

     nodePtr = nodePtr->right;

     delete tempNodePtr;

  }

}

void Tree::remove(int num)

{

  deleteNode(num, root);

}

bool Tree::searchNode(int num)

{

  TreeNode *nodePtr = root;

  while (nodePtr)

  {

     if (nodePtr->value == num)

        return true;

     else if (num < nodePtr->value)

        nodePtr = nodePtr->left;

     else

        nodePtr = nodePtr->right;

  }

  return false;

}

void Tree::displayInOrder(TreeNode *nodePtr) const

{

  if (nodePtr)

  {

     displayInOrder(nodePtr->left);

     cout << nodePtr->value << endl;

     displayInOrder(nodePtr->right);

  }

}

void Tree::displayPreOrder(TreeNode *nodePtr) const

{

  if (nodePtr)

  {

     cout << nodePtr->value << endl;

     displayPreOrder(nodePtr->left);

     displayPreOrder(nodePtr->right);

  }

}

void Tree::displayPostOrder(TreeNode *nodePtr) const

{

  if (nodePtr)

  {

     displayPostOrder(nodePtr->left);

     displayPostOrder(nodePtr->right);

     cout << nodePtr->value << endl;

  }

}

int Tree::height(TreeNode *nodePtr) const

{

  if (nodePtr == NULL)

     return 0;

  else

  {

     int lHeight = height(nodePtr->left);

     int rHeight = height(nodePtr->right);

     if (lHeight > rHeight)

        return (lHeight + 1);

     else

        return (rHeight + 1);

  }

}

int Tree::nodeCount(TreeNode *nodePtr) const

{

  if (nodePtr == NULL)

     return 0;

  else

     return (nodeCount(nodePtr->left) + nodeCount(nodePtr->right) + 1);

}

int Tree::leafCount(TreeNode *nodePtr) const

{

  if (nodePtr == NULL)

     return 0;

  else if (nodePtr->left == NULL && nodePtr->right == NULL)

     return 1;

  else

     return (leafCount(nodePtr->left) + leafCount(nodePtr->right));

}

int main()

{

  Tree tree;

  int num;

  cout << "Enter numbers to be inserted in the tree, then enter -1 to stop.\n";

  cin >> num;

  while (num != -1)

  {

     tree.insertNode(num);

     cin >> num;

  }

  cout << "Here are the values in the tree, listed in order:\n";

  tree.displayInOrder();

  cout << "Here are the values in the tree, listed in preorder:\n";

  tree.displayPreOrder();

  cout << "Here are the values in the tree, listed in postorder:\n";

  tree.displayPostOrder();

  cout << "Here are the heights of the tree:\n";

  cout << tree.height() << endl;

  cout << "Here are the number of nodes in the tree:\n";

  cout << tree.nodeCount() << endl;

  cout << "Here are the number of leaves in the tree:\n";

  cout << tree.leafCount() << endl;

  return 0;

}