STARTING OUT WITH C++ MPL
9th Edition
ISBN: 9780136673989
Author: GADDIS
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Concept explainers
Question
Chapter 19, 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 ()”.
- Give the structure declaration for the creation of node.
- Inside “public” access specifier,
- Give the definition for constructor and destructor.
- Give function declaration.
- Inside the “private” access specifier,
- 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.
- Check if “nodePtr” is null.
- 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.
- Check if the node pointer points to left node
- 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.
- Check if the value of node pointer is equal to “num”.
- 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 ()”.
- Check if the number is less than the node pointer value.
- 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.
- If the condition is true then,
- 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.
- If the condition is true then,
- 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.
- Check if the node pointer exists.
- 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”.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solutionStudents have asked these similar questions
Get the Longest Path
Write a member function called DLList BST::
get longest_path() that returns a DLL of the longest path in
the tree. For example, the red nodes in the following tree are on
the longest path and should be added to the list. In case there
are multiple longest paths, retrieve any of them.
Binary search tree. Write a function named totalSum that takes as parameter the root of the binary search tree(with the following type) and returns the total sum of the numbers in the tree. struct tree{ int data;
struct tree *left, *right;
};
quick Solution please
Chapter 19 Solutions
STARTING OUT WITH C++ MPL
Ch. 19.1 - Prob. 19.1CPCh. 19.1 - Prob. 19.2CPCh. 19.1 - Prob. 19.3CPCh. 19.1 - Prob. 19.4CPCh. 19.1 - Prob. 19.5CPCh. 19.1 - Prob. 19.6CPCh. 19.2 - Prob. 19.7CPCh. 19.2 - Prob. 19.8CPCh. 19.2 - Prob. 19.9CPCh. 19.2 - Prob. 19.10CP
Ch. 19.2 - Prob. 19.11CPCh. 19.2 - Prob. 19.12CPCh. 19 - Prob. 1RQECh. 19 - Prob. 2RQECh. 19 - Prob. 3RQECh. 19 - Prob. 4RQECh. 19 - Prob. 5RQECh. 19 - Prob. 6RQECh. 19 - Prob. 7RQECh. 19 - Prob. 8RQECh. 19 - Prob. 9RQECh. 19 - Prob. 10RQECh. 19 - Prob. 11RQECh. 19 - Prob. 12RQECh. 19 - Prob. 13RQECh. 19 - Prob. 14RQECh. 19 - Prob. 15RQECh. 19 - Prob. 16RQECh. 19 - Prob. 17RQECh. 19 - Prob. 18RQECh. 19 - Prob. 19RQECh. 19 - Prob. 20RQECh. 19 - Prob. 1PCCh. 19 - Prob. 2PCCh. 19 - Prob. 3PCCh. 19 - Prob. 4PCCh. 19 - Prob. 5PCCh. 19 - Prob. 6PCCh. 19 - Prob. 7PCCh. 19 - Prob. 8PCCh. 19 - Prob. 9PCCh. 19 - Prob. 10PC
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
- Programming questions:typedef struct node { int data; struct node *left, *right;}BT;The node structure of the binary tree (BT) is shown above. There is a binary tree T, please complete the function: int degreeone(BT *T) to compute how many degree 1 node in the BT. The T is the root pointer, and the function shoule return the total number of degree 1 node.arrow_forwardtypedef struct node{int data;struct node *left,*right;}BST;The node structure of BST is shown above. Please design an efficient algorithm to return the maximum keyword value in BST. Completion function: int findmax (BST *T)arrow_forwardstruct insert_into_bst { // Function takes a constant Book as a parameter, inserts that book indexed by // the book's ISBN into a binary search tree, and returns nothing. void operator()(const Book& book) { // // TO-DO (7) ||| ///// // Write the lines of code to insert the key (book's ISBN) and value // ("book") pair into "my_bst". END-TO-DO (7) | } std::map& my_bst; };arrow_forward
- You have a large data set of an area with income and number of people having that income. You want to create an efficient search system using Binary Search Tree (BST) to search an income and related count. Input to be read from in.txt file, Consider a file (you have to create in.txt file and copy the sample data shown below) with total number of people (N) in the first line and next N lines will contain the income and corresponding count separated by space. Output: display the result in console. Do not spend too much time to produce exact output format as we will check the output manually. Tasks: [you have to write a set of functions and test them. Some of them are fairly small] 1. Create a binary search tree based on the income as the key. However, you should also store the corresponding count within the BST node. 2. Print the data in the tree in the inorder traversal to see the keys are in sorted order. Print them like comma separated tuple (income, count). (income, count)..... 3.…arrow_forwardC Programming language Part 1: You need to define a data structure for a doubly linked list and a binary search tree. Also, you need to implement the following functions: Insert Sorted LINKEDLIST insertSorted(LINKEDLIST head, int num): head points to the first node in the sorted linked list; num is a number to be inserted in in correct place in the linked list pointed at “head”. The linked list should be sorted after inserting “num”. This function returns the head of the modified head. BSTREE insert(BSTREE root, int num): root points to a node in a binary search tree; num is a number to be inserted in the tree rooted at “root”. This function returns the root of the modified tree. Find an element LINKEDLIST find(LINKEDLIST head,int num): head points to the first node of a linked list; num is a number to be searched for in the linked list started at “head”. This function returns a pointer to the node containing “num” or NULL if num is not found BSTREE find(BSTREE root,int…arrow_forwardEx1. DLL2BST Add a constructor that constructs the binary search tree from the given DLList. BST<T>::BST(const DLL<T>& list)arrow_forward
- I have an assignment that requires me to read strings from a text file and insert them into a binary search tree. I am having a hard time reading the data from the file and passing it through a function. This is the code I have right now: struct tree_node {char *data;tree_node *left;tree_node *right;}; char **Read();tree_node *create_node(char **val); int main(){tree_node *root= NULL, *temp_node;char **val = (char**)malloc(sizeof(char*)*17);for (int i = 0; i < 17; i++) {val[i] = (char*)malloc(sizeof(char)*strlen(*val));}temp_node = create_node(val);root = insert(root, temp_node);printf("In Order: ");inorder(root);printf("\n");return 0;} char **Read() {int size;FILE *fp = fopen("in.txt", "r");fscanf(fp, "%d", &size);char** value = (char**)malloc(sizeof(char*));for(int i = 0; i < size; i++) {fscanf(fp, "%s", &value[i]);} fclose(fp);return value;} tree_node *create_node(char **val) {tree_node* temp = (tree_node*)malloc(sizeof(tree_node));for(int i = 0; i < 17; i++)for(int…arrow_forwardUSE PYTHON Write a function to traverse the binary search tree using inorder traversal in python. Dont use python libraries or OOP conceptsarrow_forwardC++ please Please complete Programming Exercise 4, from pages 1402, from chapter 19 from your textbook. Write a function, singleParent, that returns the number of nodes in abinary tree that have only one child. Add this function to the classbinaryTreeType and create a program to test this function. (Note: Firstcreate a binary search tree.)arrow_forward
- B. Project descriptionFor this project, you will create two ADTs:• A generic ADT Binary Search Tree• An ADT Class database: This ADT contains a list of class sections. Therefore, a class representing a class sectionmust be created.arrow_forwardIn JAVA code Write an algorithm for deleting a node of a Binary Search Tree. Take note that the Binary Search Tree property must be satisfied after a node is removed from a Binary Search Tree.arrow_forwardMultiple choice in data structures void doo(node<int>*root){ if(root !=0) { node<int>*p=root; while(root->next!=0) root=root->next; p->data=root->data; } What is this code do? a. swap the first item with the last item in the linked list b. set the first item in the linked list as the last item c. doesn't do anything because the root parameter is passed by value d. change the root item in the binary tree with the farthest leaf itemarrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education