Starting Out with C++: Early Objects
8th Edition
ISBN: 9780133360929
Author: Tony Gaddis, Judy Walters, Godfrey Muganda
Publisher: Addison-Wesley
expand_more
expand_more
format_list_bulleted
Concept explainers
Question
Chapter 19, Problem 1PC
Program Plan Intro
Simple Binary Search Tree Class
Program Plan:
- Include the required header files.
- Define the class BTreeNode.
- Create constructor by passing the three parameters.
- Declare the object for binary tree.
- Declare class BST has friend.
- Define the class BST.
- Define the search() function.
- Call search() function recursively and then return the result.
- Declare insert() function prototype.
- Define inorder() function.
- Call inorder() function recursively and then return the result.
- Declare the private search() function prototype.
- Declare the private inorder() function prototype.
- Define the search() function.
- In the search() function,
- Check whether the tree is empty. If yes, return false, there is no node in tree.
- Check whether the tree is equal to x. If yes, return true, the search value is found
- Check whether the tree is greater than x. If yes, call search() function by passing left node and result is returned.
- Otherwise, call search() function by passing right node and result is returned.
- In the insert() function,
- Check whether the tree is empty. If yes, create an object for binary tree.
- Loop executes until the tree is not empty. If yes,
- Check whether x is less than or equal to tree. If yes, x goes to left node of binary tree.
- Otherwise, x goes to right node of binary tree.
- In the inorder() function,
- Check whether the tree is empty. If yes, exit the statement.
- Call inorder() function by passing left node.
- List the inorder elements from tree.
- Call inorder() function by passing right node.
- Define the “main()” function.
- Read the five inputs from user.
- Call insert() function to insert all elements into binary tree.
- Call inorder() function to inorder the elements present in binary tree.
- Call search() function to search the specified values and then displays it.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solutionStudents have asked these similar questions
Course: 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(); };
CO
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
64
Array_based circular queue:
Define the class Queue using one dimensional circular array representation with no implementation; i.e. declare the data members, and the function members only (Enqueue, Dequeue, IsEmpty, GetHead etc.).
Implement the Ennqueue method of the above class
Chapter 19 Solutions
Starting Out with C++: Early Objects
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. 9PC
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++arrow_forwardGraphs: Depth First Traversal Starting with the same graph program as last assignment, implement a depth first traversal method. Test iy on nodes 1, 2, and 3 as start nodes. Graph program: #include <iostream>#include <vector>#include <string>using namespace std; class Edge;//-------------------------------------------------------------////class Node{public:Node(string iname){name = iname;}string name;int in_count = 0;bool visited = false; vector<Edge *> out_edge_list;};//-------------------------------------------------------------////class Edge{public:Edge(string iname, double iweight, Node *ifrom, Node *ito){name = iname;weight = iweight;from = ifrom;to = ito;} string name;double weight;Node *from;Node *to;bool visited = false;}; //-------------------------------------------------------------////class Graph{public:vector<Node *> node_list;vector<Edge *> edge_list; //----------------------------------------------------------//Node*…arrow_forwardDATA STRUCTURE C++: Binary trees What is the definition of the public method setRootData for binary tree? Implement it using a recursive helper in a way that the resulting binary tree stayed balanced.arrow_forward
- Computer Science JAVA Write a program that maintains the names of your friends and relatives and thus serves as a friends list. You should be able to enter, delete, modify, or search this data. You should assume that the names are unique. use a class to represent the names in the friends list and another class to represent the friends list itself. This class should contain a Binary Search Tree of names as a data field. (TreeNode Class BinarySearchTree Class FriendsList Class)arrow_forwardC++ PROGRAMMINGTopic: Binary Search Trees Explain the c++ code below.: 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) node* left(node* p) { return p->left; } node* right(node* p) { return p->right; } node* sibling(node* p){ if(p != root){ node* P = p->parent; if(left(P) != NULL && right(P) != NULL){ if(left(P) == p){ return right(P); } return left(P); } } return NULL; } node* addRoot(int e) { if(size != 0){ cout<<"Error"<<endl; return NULL; } root = create_node(e,NULL); size++; return root; } node* addLeft(node* p, int e) {…arrow_forward5. Assume the following definition for a node of a binary tree. public class Node { public int data; public Node left; public Node right; public Node (int d) { data = d; left = null; right = null; } } (a) Write a recursive function height (Node root) which calculates and returns the height of the binary tree rooted at the given root node. public static int height (Node root) { } (b) Consider the following recursive function: public static void fun (int a, int b, int c) int d - 3 - (b + c); if (a > 1) fun (a-1, ь, d); System.out.println (a + " " + b +" " + c) ; if(a > 1) fun (a-1, d, c); What is the output generated by calling: fun (3, 0, 2)? Answer:arrow_forward
- 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):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
- C programming I need help writing a code that uses a struct pointer into a binary tree and using the same pointer into an arrayarrow_forwardpython assignment Matrix class Implement a matrix class (in matrix.py). a) The initializer should take a list of lists as an argument, where each outer list is a row, and each value in an inner list is a value in the corresponding row. b) Implement the __str__ method to nicely format the string representation of the matrix: one line per row, two characters per number (%2d) and a space between numbers. For example: m = Matrix([[1,0,0],[0,1,0],[0,0,1]]) print(m)> 1 0 0> 0 1 0> 0 0 1 c) Implement a method scale(factor) that returns a new matrix where each value is multiplied by scale. For example: m = Matrix([[1,2,3],[4,5,6],[7,8,9]])n = m.scale(2)print(n)> 2 4 6> 8 10 12>14 16 18print(m)> 1 2 3> 4 5 6> 7 8 9 d) Implement a method transpose() that returns a new matrix that has been transposed. Transposing flips a matrix over its diagonal: it switches rows and columns. m = Matrix([[1,2,3],[4,5,6],[7,8,9]])print(m)> 1 2 3> 4 5 6> 7 8…arrow_forward7. ASK class DoublyLinkedList<E> {// define ListNode elements specific for this type of list, indicating current, previous and next// consider head as name for previous node, and tail for the next one.private ListNode<E> head;private ListNode<E> current;private ListNode<E> tail; // default constructorpublic DoublyLinkedList(){//*** Task #1: implement a default constructor here, initializing the nodes to null } // method that calculates the length of the listpublic int length(){//*** Task #2: implement the method navigating through the list until you run out of elements } // method that adds a node at the beginning of the listpublic void addANodeToStart(E addData){//*** Task #3: implement this method, taking into consideration that the head will be replaced by a new node. You may want to use a temporary variable } // accessor method that gets data at current nodepublic E getDataAtCurrent(){//*** Task #4: implement this method making sure to take into account…arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
- C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning