Binary Tree Template Program Plan: Main.cpp: Include required header files. Inside the “main ()” function, 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. 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 ()”, and “display_PostOrder ()”. 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.

Question

Want to see the full answer?

Answer 1

Question

Chapter 21, Problem 1PC

Program Plan Intro

Binary Tree Template

Program Plan:

Main.cpp:

Include required header files.

Inside the “main ()” function,

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.

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 ()”, and “display_PostOrder ()”.

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.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Students have asked these similar questions

Binary Trees (C++) You will create a class for Emploveelnfo that contains: • Employee ID Number – int Employee Name – string Implement a binary tree whose nodes hold an instance of your Emploveelnfo class. The nodes should be sorted on the Employee ID number. You will have a binary tree class header and implementation file. You can write your main to use the following information to test your tree: Employee Name James B W Bevis Employee ID Number 6702 Romney Wordsworth Revis Jacara Clegg Forbes Kalin Tros 1255 1071 2390 1558 7406 Archibald Beechcroft Penthor Mul Bartlet Finchley 7562 3004 4922 Latham Bine 8483 Jeff Myrtlebank Your program should read an employee ID and display a message telling the user whether it was found in the tree or not. Your main will have one binary tree object and all of the operations on the binary tree will be class methods. Other functions to add • Add function to display the tree • Allow user to add a new employee • Allow user to remove an employee NOTE –…

C++ PROGRAMMINGBinary Search Trees SEE ATTACHED PHOTO FOR THE PROBLEM INSTRUCTIONS It doesn't have to be long, as long as you explain what the important parts of the code do. (The code is already implemented and correct, only the explanation needed) #include "node.h" #include <iostream> using namespace std; class BSTree { node* root; int size; node* create_node(int num, node* parent) { node* n = (node*) malloc( sizeof(node) ); n->element = num; n->parent = parent; n->right = NULL; n->left = NULL; return n; } bool search(node* curr, int num) { if (curr == NULL) { return false; } if (num == curr->element) { return true; } if (num < curr->element) { return search(curr->left, num); } return search(curr->right, num); } node* search_node(node* curr, int num) { if (num ==…

Pythin: A binary search tree, write a function that finds and returns the median value. Assume that the class member variable. [_size] contains the number of elements in the binary search tree. What is the time complexity of your function? def find_median(self):