Chapter 20, Problem 6PC

Program Plan Intro

Tree Assignment Operator and Copy Constructor

Program Plan:

Main.cpp:

• Include required header files.
• Inside the “main ()” function,
  • Create an object “BT” for “IntBinaryTree” class.
  • Insert nodes into the binary tree by using the function “insert_Node ()”.
  • Display those nodes by using the function “display_InOrder ()”.
  • Display those nodes by using the function “display_PreOrder ()”.
  • Display those nodes by using the function “display_PostOrder ()”.
  • Delete two nodes from the binary tree by using the function “remove ()”.
  • Display remaining nodes by using the function “display_InOrder ()”.

BinaryTree.h:

• Include required header files.
• Declare a class named “IntBinaryTree”. Inside the class,
  • Inside the “public” access specifier,
    • Give the structure declaration for the creation of node.
      • Declare a variable “value”.
      • Create two pointers named “left_Node” and “right_Node” to access the value left and right nodes respectively.
    • 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 ()”, and “copyTree()”.
  • Inside “public” access specifier,
    • Give the definition for constructor, copy constructor and destructor.
    • Give function declaration.
• Give function definition for copy constructor.
• 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.
• 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”.
• 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.
• 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.
• Give function definition for “remove ()”.
  • Call the function “delete_Node ()”
• 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.
  • Otherwise,
    • Call the function “make_Deletion ()”.
• 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.
  • Otherwise,
    • 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.
• 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.
• Give function definition for “display_PreOrder ()”.
  • Print the value.
  • Call the function “display_PreOrder ()” recursively.
  • Call the function “display_PreOrder ()” recursively.
• Give function definition for “display_PostOrder ()”.
  • Call the function “display_PostOrder ()” recursively.
  • Call the function “display_PostOrder ()” recursively.
  • Print value
• Give function definition for the assignment operator.
  • Call the function “destroy_SubTree ()”.
  • Call the function “copyTree ()”.
  • Return the pointer “this”.
• The copy constructor function and assignment operator function calls the “copyTree ()” function.
  • Create a new node
  • Check if the pointer “nPtr” is not null
    • Allocate memory for the new node.
    • Assign the value of “nPtr” to the value “newNode”.
    • Call the function “copyTree ()” by passing left node pointer.
    • Call the function “copyTree ()” by passing right node pointer.
    • Return the new node.