Chapter 21, Problem 4PC

Program Plan Intro

Height of the Binary Tree

Program Plan:

• Create a template prefix and define the template class BinaryTree to perform the following functions:
  • Declare the required variables.
  • Declare the function prototypes.
  • Define the no-argument generic constructor BinaryTree() to initialize the root value as null.
  • Call the functions insertNode(), remove(), displayInOrder(), and treeHeight().
  • Define the generic function insert() to insert the node in position pointed by the tree node pointer in a tree.
  • Define the generic function insertNode() to create a new node and it should be passed inside the insert() function to insert a new node into the tree.
  • Define the generic function remove()which calls deleteNode() to delete the node.
  • Define the generic function deleteNode() which deletes the node stored in the variable num and it calls the makeDeletion() function to delete a particular node passed inside the argument.
  • Define the generic function makeDeletion()which takes the reference to a pointer to delete the node and the brances of the tree corresponding below the node are reattached.
  • Define the generic function displayInOrder()to display the values in the subtree pointed by the node pointer.
  • Define the generic function getTreeHeight() to count the height of the tree.
  • Define the generic function TreeHeight()which calls getTreeHeight() to display the height of the tree.
• In main() function,
  • Create a tree with integer data type to hold the integer values.
  • Call the function treeHeight() to print the initial height of the tree.
  • Call the function insertNode() to insert the node in a tree.
  • Call the function displayInOrder() to display the nodes inserted in the  order.
  • Call the function remove() to remove the nodes from tree.
  • Call the function treeHeight() to print the height of the tree after deleting the nodes.