Starting Out with C++ from Control Structures to Objects (8th Edition)
8th Edition
ISBN: 9780133769395
Author: Tony Gaddis
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Concept explainers
Question
Chapter 20, 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 ()”.
- 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.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solutionStudents 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):
Chapter 20 Solutions
Starting Out with C++ from Control Structures to Objects (8th Edition)
Ch. 20.1 - Prob. 21.1CPCh. 20.1 - Prob. 21.2CPCh. 20.1 - Prob. 21.3CPCh. 20.1 - Prob. 21.4CPCh. 20.1 - Prob. 21.5CPCh. 20.1 - Prob. 21.6CPCh. 20.2 - Prob. 21.7CPCh. 20.2 - Prob. 21.8CPCh. 20.2 - Prob. 21.9CPCh. 20.2 - Prob. 21.10CP
Ch. 20.2 - Prob. 21.11CPCh. 20.2 - Prob. 21.12CPCh. 20 - Prob. 1RQECh. 20 - Prob. 2RQECh. 20 - Prob. 3RQECh. 20 - Prob. 4RQECh. 20 - Prob. 5RQECh. 20 - Prob. 6RQECh. 20 - Prob. 7RQECh. 20 - Prob. 8RQECh. 20 - Prob. 9RQECh. 20 - Prob. 10RQECh. 20 - Prob. 11RQECh. 20 - Prob. 12RQECh. 20 - Prob. 13RQECh. 20 - Prob. 14RQECh. 20 - Prob. 15RQECh. 20 - Prob. 16RQECh. 20 - Prob. 17RQECh. 20 - Prob. 18RQECh. 20 - Prob. 19RQECh. 20 - Prob. 20RQECh. 20 - Prob. 21RQECh. 20 - Prob. 22RQECh. 20 - Prob. 23RQECh. 20 - Prob. 24RQECh. 20 - Prob. 25RQECh. 20 - Prob. 1PCCh. 20 - Prob. 2PCCh. 20 - Prob. 3PCCh. 20 - Prob. 4PCCh. 20 - Prob. 5PCCh. 20 - Prob. 6PCCh. 20 - Prob. 7PCCh. 20 - Prob. 8PC
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
- C++ Data Structures (Binary Trees)- Write the definition of the function nodeCount that returns the number of nodes in the binary tree. Add this function to the class binaryTreeType and create a program to test this function. Here are the headers: binaryTree.h //Header File Binary Search Tree #ifndef H_binaryTree #define H_binaryTree #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct nodeType { elemType info; nodeType<elemType> *lLink; nodeType<elemType> *rLink; }; //Definition of the class template <class elemType> class binaryTreeType { public: const binaryTreeType<elemType>& operator= (const binaryTreeType<elemType>&); //Overload the assignment operator. bool isEmpty() const; //Function to determine whether the binary tree is empty. //Postcondition: Returns true if the binary tree is empty; // otherwise, returns false. void inorderTraversal() const; //Function to do an inorder…arrow_forwardC++ DATA STRUCTURES Implement the TNode and Tree classes. The TNode class will include a data item name of type string,which will represent a person’s name. Yes, you got it right, we are going to implement a family tree!Please note that this is not a Binary Tree. Write the methods for inserting nodes into the tree,searching for a node in the tree, and performing pre-order and post-order traversals.The insert method should take two strings as input. The second string will be added as a child node tothe parent node represented by the first string. Hint: The TNode class will need to have two TNode pointers in addition to the name data member:TNode *sibling will point to the next sibling of this node, and TNode *child will represent the first child ofthis node. You see two linked lists here??? Yes! You’ll need to use the linked listsarrow_forwardCO LL * Question Completion Status: QUESTION 3 Write a recursive function, OnlyChild(..), that returns the number of nodes in a binary tree that has only one child. Consider binaryTreeNode structure is defined as the following. struct binaryTreeNode int info; binaryTreeNode *llink: binaryTreeNode *rlink; The function is declared as the following. You must write the function as a recursive function. You will not get any credits if a non-recursive solution is used. int OnlyChild(binaryTreeNode *p); For the toolbar, press ALT+F10 (PC) or ALT+FN+F10 (Mac). Paragraph Arial 10pt B. ^三へ三 三山 三Ex? X2 = E E E 9 Click Save and Submit to save and submit. Click Save All Answers to save all ansuwers. Is E English (United States) Focus || 15 stv MacBook Air D00 O00 F4 F5 F8 64arrow_forward
- C++arrow_forwardAVL Tree Implementation program Important note: You must separate your program into three files: header file (*.h), implementation file (*.cpp) and main file (*.cpp). Write a program to build an AVL tree by accepting the integers input from users. For each input, balance the tree and display it on the screen; you then calculate the indorder traversals as well. There should be a menu to drive the program. It should be similar as follows: AVL Tree Implementation A: Insert an integer to tree and show the balanced tree at each insertion. B: Display the balanced tree and show inorder traversal. C: Exit To be sure, your program is correctly working, use the following data to test AVL tree: 15, 18, 10, 7, 57, 6, 13, 12, 9, 65, 19, 16, 23 You should perform more test with different data sets.arrow_forwardCourse: Data Structure and Algorithms Language: C++ Question is well explained Question #2Implement a class for Circular Doubly Linked List (with a dummy header node) which stores integers in unsorted order. Your class definitions should look like as shown below: class CDLinkedList;class DNode {friend class CDLinkedList;private int data;private DNode next;private DNode prev;};class CDLinkedList {private:DNode head; // Dummy header nodepublic CDLinkedList(); // Default constructorpublic bool insert (int val); public bool removeSecondLastValue (); public void findMiddleValue(); public void display(); };arrow_forward
- *Please using JAVA only* Objective Program 3: Binary Search Tree Program The primary objective of this program is to learn to implement binary search trees and to combine their functionalities with linked lists. Program Description In a multiplayer game, players' avatars are placed in a large game scene, and each avatar has its information in the game. Write a program to manage players' information in a multiplayer game using a Binary Search (BS) tree for a multiplayer game. A node in the BS tree represents each player. Each player should have an ID number, avatar name, and stamina level. The players will be arranged in the BS tree based on their ID numbers. If there is only one player in the game scene, it is represented by one node (root) in the tree. Once another player enters the game scene, a new node will be created and inserted in the BS tree based on the player ID number. Players during the gameplay will receive hits that reduce their stamina. If the players lose…arrow_forwardC++ PROGRAMMINGTopic: Binary Search Trees Explain the c++ code below.: SEE ATTACHED PHOTO FOR THE CODE IDEAIt 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) node* findNewRoot(node* curr) { if(curr->left == NULL) { return curr; } return findNewRoot(curr->left); } bool remove(int num) { bool isPresent = search(num); if(isPresent){ bool rem = false; int numOfChild; node* realRoot = search_node(root,num); if(realRoot->left == NULL && realRoot->right == NULL) { numOfChild = 0; } else if((realRoot->left != NULL && realRoot->right == NULL) || (realRoot->left == NULL && realRoot->right != NULL) ) { numOfChild = 1; } else if(realRoot->left != NULL && realRoot->right != NULL) { numOfChild = 2; } if(numOfChild == 0) { bool leadRoot = false; if(realRoot == root) {…arrow_forwardC++ pleasearrow_forward
- 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; };arrow_forwardLanguage/Type: C++ binary trees pointers recursion Write a function named hasPath that interacts with a tree of BinaryTreeNode structures representing an unordered binary tree. The function accepts three parameters: a pointer to the root of the tree, and two integers start and end, and returns true if a path can be found in the tree from start down to end. In other words, both start and end must be element data values that are found in the tree, and end must be below start, in one of start's subtrees; otherwise the function returns false. If start and end are the same, you are simply checking whether a single node exists in the tree with that data value. If the tree is empty, your function should return false. For example, suppose a BinaryTreeNode pointer named tree points to the root of a tree storing the following elements. The table below shows the results of several various calls to your function: 67 88 52 1 21 16 99 45 Call Result Reason hasPath(tree, 67, 99) true path exists…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