Help needed related cpp program ! Thanx What you Need to do 1- For nodeCount met
ID: 3918635 • Letter: H
Question
Help needed related cpp program ! Thanx
What you Need to do
1- For nodeCount method you have to go to the tree class itself and create a nodeCount method and define the method for both public version and private version (in public version nodeCount will not have any argument and the private version will have one argument because it is the one that keeps the recursion going that means a public version of the traversals will return int and does not have the node pointer and private version of the traversals will also return int with the node pointer parameter) the trick is how do you verify the node count the only way you can communicate is return value of the method you cannot use by reference or movement or pointer variables you cannot have any kind of global variables
Also remember because it using recursion you will have multiple node counts on the stack which you will have node counts that public and node counts it is private
So when you make a recursive call is going to return some data and you need to grab that data and that would tell u the left sides count and the right sides count and u should add one more for itself and that value can be returned
2- For leavesCount the node with no children ho do you figure out if a node or if a tree has no children for right and left
3- For single child count (note with only one child it is similar to leavesCount except you have to ask does the node have one and exactly one child be careful to put an or is there a node on the left or is a node on the right which means is that logically true there is a node on the left or a node on the right (yes)
4- For levelCount here you have to passing a level count what is the target level also you need to pass in what is my current level and any time i go recursively deeper i increment that level count by one and the just have to check is my current level count equal to the target level count if so i can return a value
Given Code :
#include <iostream>
#include <string>
using std::endl;
using std::cout;
using std::cin;
using std::string;
void pressAnyKeyToContinue() {
printf("Press any key to continue ");
cin.get();
}
//This helps with testing, do not modify.
bool checkTest(string testName, int whatItShouldBe, int whatItIs) {
if (whatItShouldBe == whatItIs) {
cout << "Passed " << testName << endl;
return true;
}
else {
cout << "***Failed test " << testName << " *** " << endl << " Output was " << whatItIs << endl << " Output should have been " << whatItShouldBe << endl;
return false;
}
}
#include <iostream>
#include <memory>
using std::cout;
using std::cin;
using std::endl;
using std::unique_ptr;
using std::make_unique;
template <typename T>
class Tree {
public:
~Tree();
void insert(const T& item);
void preOrder();
void inOrder();
void postOrder();
private:
struct Node {
T data{};
unique_ptr<Node> left;
unique_ptr<Node> right;
~Node() { cout << "I'm a node with value " << data << " and I'm destruting" << endl; }
};
void preOrder(Node * curr);
void inOrder(Node * curr);
void postOrder(Node * curr);
unique_ptr<Node> root;
};
template <typename T>
Tree<T>::~Tree() {
root.reset();
}
template <typename T>
void Tree<T>::insert(const T& item) {
// Specific: It's empty
if (!root) {
root = make_unique<Node>();
root->data = item;
return;
}
// Generalized: Not empty
Node* curr = root.get();
do {
if (item < curr->data) {
if (curr->left) {
curr = curr->left.get();
}
else {
curr->left = make_unique<Node>();
curr->left->data = item;
break;
}
}
else {
if (curr->right) {
curr = curr->right.get();
}
else {
curr->right = make_unique<Node>();
curr->right->data = item;
break;
}
}
} while (true);
}
template <typename T>
void Tree<T>::preOrder() {
preOrder(root.get());
cout << endl;
}
template <typename T>
void Tree<T>::preOrder(Node * curr) {
if (curr) {
cout << curr->data << " ";
preOrder(curr->left.get());
preOrder(curr->right.get());
}
}
template <typename T>
void Tree<T>::inOrder() {
inOrder(root.get());
cout << endl;
}
template <typename T>
void Tree<T>::inOrder(Node * curr) {
if (curr) {
inOrder(curr->left.get());
cout << curr->data << " ";
inOrder(curr->right.get());
}
}
template <typename T>
void Tree<T>::postOrder() {
postOrder(root.get());
cout << endl;
}
template <typename T>
void Tree<T>::postOrder(Node * curr) {
if (curr) {
postOrder(curr->left.get());
postOrder(curr->right.get());
cout << curr->data << " ";
}
}
int main() {
Tree<int> myTree;
myTree.insert(37);
myTree.insert(32);
myTree.insert(73);
myTree.insert(95);
myTree.insert(42);
myTree.insert(12);
myTree.insert(00);
myTree.insert(49);
myTree.insert(98);
myTree.insert(7);
myTree.insert(27);
myTree.insert(17);
myTree.insert(47);
myTree.insert(87);
myTree.insert(77);
myTree.insert(97);
myTree.insert(67);
myTree.insert(85);
myTree.insert(15);
myTree.insert(5);
myTree.insert(35);
myTree.insert(55);
myTree.insert(65);
myTree.insert(75);
myTree.insert(25);
myTree.insert(45);
myTree.insert(3);
myTree.insert(93);
myTree.insert(83);
myTree.insert(53);
myTree.insert(63);
myTree.insert(23);
myTree.insert(13);
myTree.insert(43);
myTree.insert(33);
myTree.preOrder();
// Comment in the following tests and implement them.
//checkTest("Test #1, number of nodes", 35, myTree.nodeCount());
//checkTest("Test #2, number of leaves, (i.e. nodes with no children)", 11, myTree.leavesCount());
//checkTest("Test #3, number of nodes with one child", 14, myTree.singleChildCount());
//checkTest("Test #4, number of nodes on level 1 (the root level)", 1, myTree.levelCount(1));
//checkTest("Test #5, number of nodes on level 2", 2, myTree.levelCount(2));
//checkTest("Test #6, number of nodes on level 3", 4, myTree.levelCount(3));
//checkTest("Test #7, number of nodes on level 4", 6, myTree.levelCount(4));
//checkTest("Test #8, number of nodes on level 5", 7, myTree.levelCount(5));
//checkTest("Test #9, number of nodes on level 6", 7, myTree.levelCount(6));
//checkTest("Test #10, number of nodes on level 7", 7, myTree.levelCount(7));
//checkTest("Test #11, number of nodes on level 8", 1, myTree.levelCount(8));
//checkTest("Test #12, number of nodes on level 9", 0, myTree.levelCount(9));
pressAnyKeyToContinue();
return 0;
}
Assignment - Binary Tree Recursion Goal: To gain experience working with recursion in the context of binary trees. Implement the following methods nodeCount() - Returns an integer as to the total count of nodes in the tree. leavsesCount() - Returns an integer as to the total count of nodes that have zero children. singleChildCount() - Returns an integer as to the total count of nodes that have exactly 1 child. levelCount() - Returns an the number of nodes on that level of a tree (root node is level1 General strategy is to do recursion like the preOrder, inOrder, and postOrder traversal methods, where there will be a public method callable by the application developer, and a private method that keeps the recursion going The difference in this assignment compared to the lecture video is that the return values for these methods should be int, not void. When a method returns, it should return the accumulation of 1) the count on the left child side, 2) the count on the right child side, and 3) the node it is pointing to, if the particular node applies to the rules for the method. You cannot use global variables to store your count. Further, you cannot pass any parameter data by pointer(*)/by reference (&)/through move semantics (&&). The count must be accumulated through the return value.Explanation / Answer
int getfullCount(struct Node* root)
{
if (root == NULL)
return 0;
int res = 0;
res += (getfullCount(root->left) +
getfullCount(root->right));
return res;
}
int getLeafCount(struct node* node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
int getSingleChildCount(struct Node* root)
{
if (root == NULL)
return 0;
int res = 0;
if ((root->left == NULL && root->right != NULL) ||
(root->left != NULL && root->right == NULL))
res++;
res += (getSingleChildCount(root->left) +
getSingleChildCount(root->right));
return res;
}
Int printGivenLevel(struct node* root, int level)
{
if (root == NULL)
return 0;
if (level == 1)
return 1;
else if (level > 1)
{
return printGivenLevel(root->left, level-1) + printGivenLevel(root->right, level-1);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.