Chapter 20, Problem 7PC

Program Plan Intro

Queue Converter

Program Plan:

DynIntQueue.h:

• Include required header files.
• Declare a class named “DynIntQueue”; inside the class,
  • Inside the “private” access specifier,
    • Create a structure named “QueueNode”.
      • Declare a variable “value”.
      • Create a pointer named “next”.
    • Create two pointers named “front” and “rear”.
    • Declare a variable “numItems”.
  • Inside “public” access specifier,
    • Declare constructor and destructor.
    • Declare the functions “enqueue()”, “dequeue()”, “isEmpty()”, “isFull()”, and “clear()”.

DynIntQueue.cpp:

• Include required header files.
• Give definition for the constructor.
  • Assign the values.
• Give definition for the destructor.
  • Call the function “clear()”.
• Give function definition for “enqueue()”.
  • Make the pointer “newNode” as null.
  • Assign “num” to “newNode->value”.
  • Make “newNode->next” as null.
  • Check whether the queue is empty using “isEmpty()” function.
    • If the condition is true then, assign “newNode” to “front” and “rear”.
    • If the condition is not true then,
      • Assign “newNode” to “rear->next”.
      • Assign “newNode” to “rear”.
    • Increment the variable “numItems”.
• Give function definition for “dequeue()”.
  • Assign “temp” pointer as null.
  • Check if the queue is empty using “isEmpty()” function.
    • If the condition is true then print “The queue is empty”.
    • If the condition is not true then,
      • Assign the value of front to the variable “num”.
      • Make “front->next” as “temp”.
      • Delete the front value.
      • Make temp as front.
      • Decrement the variable “numItems”.
• Give function definition for “isEmpty()”.
  • Assign “true” to a Boolean variable
  • Check if “numItems” is true.
    • If the condition is true then assign “false” to the variable.
  • Return the Boolean variable.
• Give function definition for “clear()”.
  • Declare a variable.
    • Dequeue values from queue till the queue becomes empty using “while” condition.

IntBinaryTree.h:

• Include required header files.
• Declare a class named “IntBinaryTree”. Inside the class,
  • Inside the “private” access specifier,
    • Give the structure declaration for the creation of node.
      • Declare a variable
      • Create two pointers named “left” and “right” 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 ()”, “copyTree ()”, and “setQueue ()”.
  • Inside “public” access specifier,
    • Give the definition for constructor and destructor.
    • Give function declaration for binary tree operations.

IntBinaryTree.cpp:

• Include required header files.
• Give 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.
  • Else,
    • 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.
  • 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.
• 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 assignment operator.
  • Call the function “destroy_SubTree()”
  • Call the copy constructor.
  • Return the pointer.
• Copy tree function is called by copy constructor and assignment operator function
  • Create a pointer named “newNode”.
  • Check if “nPtr” is not equal to null
    • Allocate memory dynamically.
    • Assign pointer value to the new node.
    • Call the function “copyTree()” by passing “nPtr” of left.
    • Call the function “copyTree()” by passing “nPtr” of right
  • Return the new node.
• Function definition for “setQueue()”.
  • Check if the pointer “nodePtr” exists.
  • Call the function “setQueue()” recursively by passing the left node.
  • Call the function “setQueue()” recursively by passing the right node.
  • Call the function “enqueue()” recursively by passing the left node.

Main.cpp:

• Include required header files.
• Inside “main()” function,
  • Declare a variable “value” and assign it to 0.
  • Create an object “intBT” for “IntBinaryTree” class.
  • Insert 5 values using “insert_Node()” function.
  • Display all the values by using the function “display_InOrder()”.
  • Create an object “iqueue” for “DynIntQueue” class.
  • Load the address to the pointer “qPtr”.
  • Pass this pointer to the function “treeToQueue ()”.
  • Do until the queue is not empty.
    • Declare a variable.
    • Call the function “dequeue()”.
    • Display the value.