Starting Out With C++: Early Objects (10th Edition)
Starting Out With C++: Early Objects (10th Edition)
10th Edition
ISBN: 9780135235003
Author: Tony Gaddis, Judy Walters, Godfrey Muganda
Publisher: PEARSON
bartleby

Concept explainers

Question
Book Icon
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 ()”.
    • 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”.

Blurred answer
Students have asked these similar questions
Python binary search tree:  a function that takes in a root, p, and checks whether the tree rooted in p is a binary search tree or not. What is the time complexity of your function? def is_bst(self, p: Node):
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; };
Knowledge Booster
Background pattern image
Computer Science
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
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Text book image
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Text book image
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
Text book image
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Text book image
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Text book image
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education