(In C++ Language please) Write a program to store a binary tree in an array. The
ID: 3696033 • Letter: #
Question
(In 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
is_full_binary(root) { queue q = new queue() q.push(pair(0,root)) int currentNodes = 0 int current = 0 while q.isEmpty() == false { level, node = q.pop() q.push(pair(level+1, node.left)) // make sure such exist before... q.push(pair(level+1, node.right)) //same here if level == current currentNodes++ else { if currentNodes != 2^current return false currentNodes = 0 current = level } } return true }
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.