THIS IS C++ DATA STRUCTURES. DO NOT USE ANY LIBRARIES BESIDES <IOSTREAM> // Use
ID: 3759654 • Letter: T
Question
THIS IS C++ DATA STRUCTURES. DO NOT USE ANY LIBRARIES BESIDES <IOSTREAM>
// Use this "struct" for the function below.
// The function is in a class located at .h file. But, I do not think that is needed to code this function.
struct BinaryTreeNode {
int data;
BinaryTreeNode* left_child;
BinaryTreeNode* right_child;
};
// The Clear method for the BinaryTree class. Needs to call "delete" on each
// node, and set head to nullptr.
void BinaryTree::Clear() {}
// Already done for you
// The ToString method for the BinaryTree clsss. This will print out a binary
// tree, in the order of it's values. That means it does a "depth first"
// traversal of the tree (Google that). Take a look at the helper
// ToStringRecursiveDepthFirst for how that is done with recursion.
// The values are printed in the format:
// [ d<the depth in the tree this node is at>-<value> d<...>-<...> ]
// So [ d1-1 d0-2 d1-3 d2-4 ] is a tree that looks like:
//
// 2 // Depth 0
// ___|___
// | |
// 1 3 // Depth 1
// |
// ___
// |
// 4 // Depth 2
//
// If you hate that format, you are welcome to change the code here, or in the
// ToStringRecursiveDepthFirst helper so that it looks less, terrible.
std::string BinaryTree::ToString()
{
return "[ " + ToStringRecursiveDepthFirst(head, 0) + "]";
}
Explanation / Answer
string ToStringRecursiveDepthFirst(BinaryTreeNode *head, int d) {
if (head == nullptr) {
return "";
}
string str = ToStringRecursiveDepthFirst(head->left_child, d+1);
str = str + "d";
str = str + to_string(d) + "-" + to_string(head->data) + " ";
str = str + ToStringRecursiveDepthFirst(head->right_child, d+1);
return str;
}
std::string BinaryTree::ToString()
{
return "[ " + ToStringRecursiveDepthFirst(head, 0) + "]";
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.