Chapter 21, Problem 3PC

Program Plan Intro

Leaf Counter

Program Plan:

Main.cpp:

• Include required header files.
• Inside the “main ()” function,
  • Display the number of leaf nodes by calling the function “num_LeafNodes ()”.
  • Insert nodes into the binary tree by using the function “insert_Node ()”.
  • Display those nodes by using the function “display_InOrder ()”.
  • Now, display the number of leaf nodes by calling the function “num_LeafNodes ()”.
  • Delete two nodes from the binary tree by using the function “remove ()”.
  • Display remaining nodes by using the function “display_InOrder ()”.
  • Finally, display the number of leaf nodes by calling the function “num_LeafNodes ()”.

BinaryTree.h:

• Include required header files.
• Create a class template.
• Declare a class named “BinaryTree”. Inside the class,
  • Inside the “private” access specifier,
    • Give the structure declaration for the creation of node.
      • Create an object for the template.
      • Create two pointers named “left_Node” and “right_Node” to access the value left and right nodes respectively.
    • Declare a variable “leafCount”.
    • Create a pointer named “root” to access the value of root node.
    • Give function declaration for “insert ()”, “destroy_SubTree ()”, “delete_Node ()”, “make_Deletion ()”, “display_InOrder ()”, “display_PreOrder ()”, “display_PostOrder ()”, “count_Nodes ()”, “count_Leaves ()”.
  • Inside “public” access specifier,
    • Give the definition for constructor and destructor.
    • Give function declaration.
• Declare template class.
• Give function definition for “insert ()”.
  • Check if “nodePtr” is null.
    • If the condition is true then, insert node.
  • Check if value of new node is less than the value of node pointer
    • If the condition is true then, Insert node to the left branch by calling the function “insert ()” recursively.
  • Else
    • Insert node to the right branch by calling the function “insert ()” recursively.
• Declare template class.
• Give function definition for “insert_Node ()”.
  • Create a pointer for new node.
  • Assign the value to the new node.
  • Make left and right node as null
  • Call the function “insert ()” by passing parameters “root” and “newNode”.
• Declare template class.
• Give function definition for “destroy_SubTree ()”.
  • Check if the node pointer points to left node
    • Call the function recursively to delete the left sub tree.
  • Check if the node pointer points to the right node
    • Call the function recursively to delete the right sub tree.
  • Delete the node pointer.
• Declare template class.
• Give function definition for “search_Node ()”.
  • Assign false to the Boolean variable “status”.
  • Assign root pointer to the “nodePtr”.
  • Do until “nodePtr” exists.
    • Check if the value of node pointer is equal to “num”.
      • Assign true to the Boolean variable “status”
    • Check if the number is less than the value of node pointer.
      • Assign left node pointer to the node pointer.
    • Else
      • Assign right node pointer to the node pointer.
  • Return the Boolean variable.
• Declare template class.
• Give function definition for “remove ()”.
  • Call the function “delete_Node ()”
• Declare template class.
• Give function definition for “delete_Node ()”
  • Check if the number is less than the node pointer value.
    • Call the function “delete_Node ()” recursively.
  • Check if the number is greater than the node pointer value.
    • Call the function “delete_Node ()” recursively.
  • Else,
    • Call the function “make_Deletion ()”.
• Declare template class.
• Give function definition for “make_Deletion ()”
  • Create pointer named “tempPtr”.
  • Check if the nodePtr is null.
    • If the condition is true then, print “Cannot delete empty node.”
  • Check if right node pointer is null.
    • If the condition is true then,
      • Make the node pointer as the temporary pointer.
      • Reattach the left node child.
      • Delete temporary pointer.
  • Check is left node pointer is null
    • If the condition is true then,
      • Make the node pointer as the temporary pointer.
      • Reattach the right node child.
      • Delete temporary pointer.
  • Else,
    • Move right node to temporary pointer
    • Reach to the end of left-Node using “while” condition.
      • Assign left node pointer to temporary pointer.
    • Reattach left node sub tree.
    • Make node pointer as the temporary pointer.
    • Reattach right node sub tree
    • Delete temporary pointer.
• Declare template class.
• Give function definition for “display_InOrder ()”.
  • Check if the node pointer exists.
    • Call the function “display_InOrder ()” recursively.
    • Print the value
    • Call the function “display_InOrder ()” recursively.
• Declare template class.
• Give function definition for “display_PreOrder ()”.
  • Print the value.
  • Call the function “display_PreOrder ()” recursively.
  • Call the function “display_PreOrder ()” recursively.
• Declare template class.
• Give function definition for “display_PostOrder ()”.
  • Call the function “display_PostOrder ()” recursively.
  • Call the function “display_PostOrder ()” recursively.
  • Print value
• Declare template class.
• Give function definition for “numNodes ()”.
  • Call the function “count_Nodes ()”.
• Declare template class.
• Give function definition for “count_Nodes ()”.
  • Declare a variable named “count”.
  • Check if the node pointer is null
    • Assign 0 to count.
  • Else,
    • Call the function “count_Nodes ()” recursively.
  • Return the variable “count”.
• Declare template class.
• Give function definition for “num_LeafNodes()”.
  • Assign 0 to “leafCount”
  • Call the function “count_Leaves ()”
  • Return the variable.
• Declare template class.
• Give function definition for “count_Leaves()”.
  • Call the function “count_Leaves ()” recursively by passing left node pointer as the parameter.
  • Call the function “count_Leaves ()” recursively by passing right node pointer as the parameter.
  • Check if left and right node pointers are null.
    • Increment the variable “leafCount”.