Starting Out with C++: Early Objects (9th Edition)
9th Edition
ISBN: 9780134400242
Author: Tony Gaddis, Judy Walters, Godfrey Muganda
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Question
Chapter 19, Problem 3RQE
A node without child is referred a “leaf node”.
Program Plan Intro
Binary tree:
A complete binary tree is a binary tree with the property that every node must have exactly two children, and at the last level the nodes should be from left to right.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
Graphs: 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*…
JAVA :
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
Chapter 19 Solutions
Starting Out with C++: Early Objects (9th Edition)
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
Similar questions
- Given Code: #include<iostream>#include<queue> struct treeNode{ char dataItem; struct treeNode *firstChild; struct treeNode *nextSibling;}; /* Preorder Traversalpreorder (v)visit(v)for each child w of vpreorder(w)*/void preorder(treeNode *currNode){ if(currNode != NULL){ std::cout << currNode->dataItem << " "; preorder(currNode->firstChild); preorder(currNode->nextSibling); } return;} /* Postorder Traversalpostorder (v)for each child w of vpostOrder(w)visit(v)*/void postorder(treeNode *currNode){ if(currNode != NULL){ preorder(currNode->firstChild); preorder(currNode->nextSibling); std::cout << currNode->dataItem << " "; } return;} /*Inorder Traversalif(v==NULL) returninOrder(v.left)visit(v)inOrder(v.right)*/void inorder(treeNode *currNode){ if(currNode != NULL){ inorder(currNode->firstChild); std::cout << currNode->dataItem…arrow_forwardNonearrow_forwardplease convert to C languange #include<bits/stdc++.h>using namespace std; class tree{ //tree node public: int data; tree *left; tree *right;}; bool hasRootToLeafSum(tree *root, int s){ bool path=false; //declare boolean variable path //base condition checking if(root==NULL && s==0) return true; s-=root->data; //subtract current root value //checking whether leaf node reached and remaining sum =0 if(s==0 && root->left==NULL && root->right==NULL) return true; //recursively done for both subtrees if(root->left){//for left subtree path=path||hasRootToLeafSum(root->left, s); } if(root->right){//for right subtree path=path||hasRootToLeafSum(root->right, s); } return path;} tree* newnode(int data){ //creating new nodes tree* node = (tree*)malloc(sizeof(tree)); node->data = data; node->left = NULL; node->right = NULL;…arrow_forward
- Course: Data Structure and Algorithims Language: Java Kindly make the program in 2 hours. Task is well explained. You have to make the proogram properly in Java: Restriction: Prototype cannot be change you have to make program by using given prototype. TAsk: Create a class Node having two data members int data; Node next; Write the parametrized constructor of the class Node which contain one parameter int value assign this value to data and assign next to null Create class LinkList having one data members of type Node. Node head Write the following function in the LinkList class publicvoidinsertAtLast(int data);//this function add node at the end of the list publicvoid insertAthead(int data);//this function add node at the head of the list publicvoid deleteNode(int key);//this function find a node containing "key" and delete it publicvoid printLinkList();//this function print all the values in the Linklist public LinkListmergeList(LinkList l1,LinkList l2);// this function…arrow_forwardListQueue Node Node Node front= next next= next = nul1 rear = data "Thome" data "Abreu" data - "Jones" size - 3 The above is a queue of a waiting list. The ListQueue has a node (front) to record the address of the front element of a queue. It also has another node (rear) to record the address of the tail element of a queue. 4. How do you push a node with data, "Chu" to the above queue? front.next = new Node("Chu", front); a. b. front = new Node ("Chu", front) rear = new Node("Chu", rear) с. d. = new Node ("Chu", rear.next) rear Describe the reason of your choice. Your answer is (a, b, c, or d) Will the push action take time in 0(1) or 0(n)? Next Page Type here to searcharrow_forwardMake an array of linked list for the following C code: // Node structure containing power and coefficient of// variablestruct Node {int coeff;int pow;struct Node* next;}; // Function to create new nodevoid create_node(int x, int y, struct Node** temp){struct Node *r, *z;z = *temp;if (z == NULL) {r = (struct Node*)malloc(sizeof(struct Node));r->coeff = x;r->pow = y;*temp = r;r->next = (struct Node*)malloc(sizeof(struct Node));r = r->next;r->next = NULL;}else {r->coeff = x;r->pow = y;r->next = (struct Node*)malloc(sizeof(struct Node));r = r->next;r->next = NULL;}} // Function Adding two polynomial numbersvoid polyadd(struct Node* poly1, struct Node* poly2,struct Node* poly){while (poly1->next && poly2->next) {// If power of 1st polynomial is greater then 2nd,// then store 1st as it is and move its pointerif (poly1->pow > poly2->pow) {poly->pow = poly1->pow;poly->coeff = poly1->coeff;poly1 = poly1->next;} // If power of…arrow_forward
- #ifndef H_binarySearchTree #define H_binarySearchTree #include <iostream> #include <cassert> #include "binaryTree.h" //************************************************************* // Author: D.S. Malik // // This class specifies the basic operations to implement a // binary search tree. // Revised by Dr. Ji on Npv 30 2021 //************************************************************* using namespace std; template<class elemType> class bSearchTreeType: public binaryTreeType<elemType> { public: bool search(const elemType& searchItem) const; //Function to determine if searchItem is in the binary //search tree. //Postcondition: Returns true if searchItem is found in the // binary search tree; otherwise, returns false. void insert(const elemType& insertItem); //Function to insert insertItem in the binary search tree. //Postcondition: If no node in the binary search tree has the // same info as insertItem, a node with the info insertItem // is created and…arrow_forwardA BST is constructed in the usual way using the node definition below. Write a function int child2( bst node t *curr) that returns the number of nodes that have 2 children. typedef struct BST NODE T {int data;struct BST NODE T *left, *right; } bst node t; int child2( bst node t *curr){ }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_forward
- // FILL IN THE BLANKS (LINKED-LISTS CODE) (C++)#include<iostream>using namespace std; struct ________ {int data ;struct node *next; }; node *head = ________;node *createNode() { // allocate a memorynode __________;temp = new node ;return _______ ;} void insertNode(){node *temp, *traverse;int n;cout<< "Enter -1 to end "<<endl;cout<< "Enter the values to be added in list"<<endl;cin>>n; while(n!=-1){temp = createNode(); // allocate memorytemp->data = ________;temp->next = ________;if ( ___________ == NULL){head = _________;} else {traverse = ( );while (traverse->next != ________{traverse = traverse-> ___________;} traverse->next= temp;} cout<<"Enter the value to be added in the list"<<endl;cin>>n; }} void printlist(){node *traverse = head; // if head == NULLwhile (traverse != NULL) { cout<<traverse->data<<" ";traverse = traverse->next;}} int main(){int option; do{cout<<"\n =============== MAIN…arrow_forwardA tree is implemented using a node structure defined as: struct node{ int data; struct node *left; strict node *right; }; Write a function whose prototype is: int smallest(struct node *); which accepts a tree (pointer to the root) and returns the smallest node in the right sub-tree of the root. If root is NULL, or if there is no right sub-tree, returm the number -999.arrow_forwarddata structures-java language quickly plsarrow_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