(C++ Language please) Write a program to store a binary tree in an array. The tr
ID: 3696326 • Letter: #
Question
(C++ Language please) Write a program to store a binary tree in an array. The tree may be full, complete, or neither full nor complete.
Define a class, TreeBag, to handle operations of the data structure. The TreeBag class should contain a private member array (either static or dynamic - your choice). The array should be filled with -1s as part of the constructor. There should be the following member functions (at least):
bool insert(int) - Allows the user to insert a value into the tree. The new value will be placed at the first available spot, without regard to parent. The function will return a true if the value was entered into the array.
bool addChild(int, int) - Allows the user to add a child to a specific parent. The first parameter is the element number of the parent; the second parameter is the value to be entered. The function will return a true if the value was entered into the array. If the array cell at the position of the left child already has a value (other than -1), the program must check the position of the right child. If that position is available, the value will be inserted there.
void getChildren(int, int&, int&) - A function to return the values held in both the left and right children of the parent. The parameters are: cell number of the parent, value of the left child, and value of the right child.
void printTreeBag() - Prints out a graphical representation of the contents of the tree, maintaining the relationship of parent and child(ren).
Explanation / Answer
Solution: Please follow these coding as shown in below...
#include <iostream>
#include <cstdlib>
#include <cstdio>
template<class E>
struct TNode{
E value;
TNode<E>* leftChild;
TNode<E>* rightChild;
TNode<E>(){
this->value = NULL;
this->leftChild = NULL;
this->rightChild = NULL;
}
TNode<E>(E value){
this->value = value;
this->leftChild = NULL;
this->rightChild = NULL;
}
};
template<class E>
class TreeBag{
private:
TNode<E>* root;
/**
build and return the pointer to a binary tree for given array 'arr' and array size 'len'
*/
TNode<E>* build(E* arr, int len){
TNode<E> *subRoot = new TNode<E>(arr[0]);
if (len == 1){
return subRoot; // terminating function - at the leaf
}
E* elementsToLeft = new E[len]; // array to store the left subtree children
E* elementsToRight = new E[len]; // array to store the right sub tree children
int counterLeft = 0;
int counterRight = 0;
for (int i = 1; i < len; i = (i * 2) + 1){
for (int j = i; j < i + ((i + 1) / 2); j++){
elementsToLeft[counterLeft] = arr[j]; // appending the array which has children of left sub tree
counterLeft++;
if ((j + (i + 1) / 2)<len){ // check whether there are childs to store in the right sub tree....
elementsToRight[counterRight] = arr[j + (i + 1) / 2]; // appending the array which has children of left sub tree
counterRight++;
}
}
}
subRoot->leftChild = build(elementsToLeft, counterLeft); // recursive call> array- left sub tree's children and size
subRoot->rightChild = build(elementsToRight, counterRight); // recursive call> array- right sub tree's children and size
return subRoot;
}
public:
/**
add the value specified by newvalueas the left child of the tree node specified by parent,if the node does not have a left childalready.
returns 1 if addition is successful and returns -1 in failure.
*/
template <class E>
int intaddLeftChild(TNode<E>* parent, E newvalue){
if (parent->leftChild != NULL){ return -1; }
TNode<E> *temp = new TNode<E>(newvalue);
parent->leftChild = temp;
return 1;
}
/**add the value specified by newvalueas the right child of the tree node specified by parent, if the node does not have a right childalready.
returns 1 if addition is successful and returns -1 in failure.
*/
template <class E>
int intaddRightChild(TNode<E>* parent, E newvalue){
if (parent->rightChild != NULL){ return -1; }
TNode<E> *temp = new TNode<E>(newvalue);
parent->rightChild = temp;
return 1;
}
/**
create and return the pointer to a Binary tree from an array
input an array. eg:- int i[] = {3,5,7} ; create_tree(i);
*/
template<class E, int N>
TNode<E>* create_tree(E(&elements)[N]){
int length = N;
return build(elements, N);
}
};
int main(){
//to demonstrate
int nums[] = { 7,5,9,1,7,3};
TreeBag<int> mal;
TNode<int>* BinaryTree = mal.create_tree(nums); // store the made binary tree from nums and point it by the pointer, BinaryTree.
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.