Implement in C++ PROBLEM 4 (135 points) 4.1 Write a program to store a tree as a
ID: 3815980 • Letter: I
Question
Implement in C++
PROBLEM 4 (135 points)
4.1 Write a program to store a tree as an array. In your test program, be sure to print the array values, and to print the values in tree “format”.
4.2 Write a function to add an element to an existing tree.
4.3 Write a function to delete an element from an existing tree.
4.4 Write a function to perform an “in-order” traversal on an existing tree.
4.5 Write a function to perform an “pre-order” traversal on an existing tree.
4.6 Write a function to perform an “post-order” traversal on an existing tree.
4.7 Write a function to perform an “level-order” traversal on an existing tree.
4.8 Write a function to find the children of a specified node.
4.9 Write a function to find the parent of a specified node.
Explanation / Answer
#include<iostream>
using namespace std;
public:
int size;
int* array;
void AddElement(int x);
void inOrder(int PresentIndex);
void preOrder(int PresentIndex);
void postOrder(int PresentIndex);
void parent(int x);
int extendSize(int x);
BST(int size)
{
this -> size = extendSize(size);
cout << this -> size << endl;
this -> array = new int[this -> size];
for(int x = 0; x < this -> size; x++){
array[x] = NULL;
}
}
};
int BST::extendSize(int x) {
int value = 0;
for(int y = 0; y < x + 1; y++) {
value = (2 * value) + 2;
}
return value;
}
void BST::AddElement(int x) {
int PresentIndex = 0;
cout << "Adding: " << x;
while(true) {
if(array[PresentIndex] == NULL){
array[PresentIndex] = x;
cout << " Inserted at index: " << PresentIndex << endl;
break;
}else if(array[PresentIndex] <= x) {
if(array[PresentIndex] == x){
cout << "ERROR!-- Repeating element" << endl;
break;
}else
cout << " Right ";
PresentIndex = (2 * PresentIndex + 2);
}else if(array[PresentIndex] >= x) {
if(array[PresentIndex] == x){
cout << "ERROR!-- Repeating element" << endl;
break;
}else
cout << " Left ";
PresentIndex = (2 * PresentIndex + 1);
}
}
}
void BST::Search(int x){
int PresentIndex = 0;
while (true) {
if (array[PresentIndex] == NULL) {
cout << "Not Found" << endl;
break;
}
if (array[PresentIndex] == x) {
cout << "Found at index: " << PresentIndex << endl;
break;
}
else if(array[PresentIndex] < x) {
PresentIndex = (2 * PresentIndex + 2);
}
else if(array[PresentIndex] > x) {
PresentIndex = (2 * PresentIndex + 1);
}
}
}
void BST::parent(int x){
while (x != 0) {
x = (x-1) / 2;
cout << "---";
}
}
void BST::inOrder(int PresentIndex){
if(array[PresentIndex] != NULL) {
inOrder(2 * PresentIndex + 1);
parent(PresentIndex);
cout << array[PresentIndex] << endl;
inOrder(2 * PresentIndex + 2);
}
}
void BST::postOrder(int PresentIndex) {
if(array[PresentIndex] != NULL){
postOrder(2 * PresentIndex + 1);
postOrder(2 * PresentIndex + 2);
parent(PresentIndex);
cout << array[PresentIndex] << " " << endl;
}
}
void BST::preOrder(int PresentIndex) {
if(array[PresentIndex] != NULL) {
preOrder(2 * PresentIndex + 1);
parent(PresentIndex);
cout << array[PresentIndex] << " " << endl;
preOrder(2 * PresentIndex + 2);
}
}
int main () {
BSTbinary(5);
binary.AddElement(4);
binary.AddElement(6);
binary.AddElement(9);
binary.AddElement(3);
binary.AddElement(2);
binary.Search(1);
binary.inOrder(0);
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.