Need to write the following functions in table.cpp, and add function prototypes
ID: 2246627 • Letter: N
Question
Need to write the following functions in table.cpp, and add function prototypes for them to table.h and invoke the functions in main.cpp.
* int sumOfNodes(node * root)
Recursively calculate the sum of all the nodes in the tree.
* void copyLeaf(node * src, node *& dest)
Recursively copy all the leaves from the source tree to the destination tree. The destination tree must be a binary search
tree.
--------------------------------------------------------------------------------------------
main.cpp
#include "table.h"
#include <iostream>
using namespace std;
int main()
{
node * root = NULL;
build(root);
display(root);
/* PLACE YOUR FUNCTION CALL HERE */
display(root);
destroy(root);
return 0;
}
-----------------------------------------------------------------
table.h
#ifndef TABLE_H
#define TABLE_H
//table.h
#include <iostream>
#include <cstring>
#include <cctype>
using namespace std;
struct node
{
int data;
node * left;
node * right;;
};
void build(node * & root); //supplied
void display(node * root); //supplied
void destroy(node * & root); //supplied
/* ************** PLACE YOUR PROTOTYPE HERE ***************** */
#endif
------------------------------------------------------------
table.cpp
#include "table.h"
//Please put the impelementation of the required functions here
----------------------------------------------------------------------------------------
Please make sure the functions are done recursively, and are done in C++
Explanation / Answer
main.cpp:
#include "table.h"
#include <iostream>
using namespace std;
int main()
{
node * root = NULL;
build(root);
display(root);
/* PLACE YOUR FUNCTION CALL HERE */
cout << "Sum of the values in all node of the tree is: " << sumOfNodes(root) << endl;
node * copiedTree = NULL;
copyLeaf(root, copiedTree);
cout << "The copied tree from the leaves of original tree is: " << endl;
display(copiedTree);
display(root);
destroy(root);
return 0;
}
table.h:
#ifndef TABLE_H
#define TABLE_H
//table.h
#include <iostream>
#include <cstring>
#include <cctype>
using namespace std;
struct node
{
int data;
node * left;
node * right;
};
void build(node * & root); //supplied
void display(node * root); //supplied
void destroy(node * & root); //supplied
/* ************** PLACE YOUR PROTOTYPE HERE ***************** */
int sumOfNodes(node * root);
void copyLeaf(node * src, node *& dest);
#endif
table.cpp:
#include "table.h"
int sumOfNodes(node * root) {
if(root == NULL) {
return 0;
}
else {
// current node value + left/right tree node values
return root->data + sumOfNodes(root->left) + sumOfNodes(root->right);
}
}
// create new node, helper method
node* newNode(int data) {
// new is like 'malloc' that allocates memory
node* n = new(node);
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}
void insertIntoTree(node *& root, int data) {
// if root is null, make it root
if(root == NULL) {
root = newNode(data);
} else {
int rootData = root->data;
// check whether new node should go in left subtree or right
if(data < rootData) {
// if there is place to insert data at left side
if(root->left == NULL) {
root->left = newNode(data);
} else {
insertIntoTree(root->left, data);
}
} else if(data > rootData) {
// if there is place to insert data at right side
if(root->right == NULL) {
root->right = newNode(data);
} else {
insertIntoTree(root->right, data);
}
}
}
}
void copyLeaf(node * src, node *& dest){
if(src == NULL) {
return;
} else {
if(!src->left && !src->right) {
// it is a leaf, insert it into other tree
insertIntoTree(dest, src->data);
} else {
// recurse for left and right subtree
copyLeaf(src->left, dest);
copyLeaf(src->right, dest);
}
}
}
/*
Your other functions
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.