A. (c++) Write a program to store a tree as an array. In your test program, be s

Question

A. (c++) 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”.

B. (c++) Write a function to add an element to an existing tree.

C. (c++) Write a function to delete an element from an existing tree.

D. (c++) Write a function to perform an “in-order” traversal on an existing tree.

E. (c++) Write a function to perform an “pre-order” traversal on an existing tree.

F. (c++) Write a function to perform an “post-order” traversal on an existing tree.

G. (c++) Write a function to perform an “level-order” traversal on an existing tree.

H. (c++) Write a function to find the children of a specified node.

I. (c++) Write a function to find the parent of a specified node.

please comment throughout the code. thanks

Explanation / Answer

program.cpp

#include<iostream>
using namespace std;

public:
int size;
int* array;

void insertInTree(int x);
void searhInTree(int x);
void traverseInOrder(int currentIndex);
void traversePostOrder(int currentIndex);
void traversePreOrder(int currentIndex);
void parent(int x);
int sizeExtend(int x);

BinarySearchTree (int size) {
this -> size = sizeExtend(size);
this -> array = new int[this -> size];
for(int x = 0; x < this -> size; x++){
array[x] = NULL;
}
}
};

int BinarySearchTree::sizeExtend(int x) {
int value = 0;
for(int y = 0; y < x + 1; y++) {
value = (2 * value) + 2;
}
return value;
}

void BinarySearchTree::insertInTree(int x) {
int currentIndex = 0;
cout << "Adding: " << x;
while(true) {
if(array[currentIndex] == NULL){
array[currentIndex] = x;
cout << " Inserted at index: " << currentIndex << endl;
break;
}else if(array[currentIndex] <= x) {
if(array[currentIndex] == x){
cout << "ERROR!-- Repeating element" << endl;
break;
}else
cout << " Right ";
currentIndex = (2 * currentIndex + 2);
}else if(array[currentIndex] >= x) {
if(array[currentIndex] == x){
cout << "ERROR!-- Repeating element" << endl;
break;
}else
cout << " Left ";
currentIndex = (2 * currentIndex + 1);
}

}
}

void BinarySearchTree::searhInTree(int x){
int currentIndex = 0;
while (true) {
if (array[currentIndex] == NULL) {
cout << "Not Found" << endl;
break;
}
if (array[currentIndex] == x) {
cout << "Found at index: " << currentIndex << endl;
break;
}
else if(array[currentIndex] < x) {
currentIndex = (2 * currentIndex + 2);
}
else if(array[currentIndex] > x) {
currentIndex = (2 * currentIndex + 1);
}

}

}

void BinarySearchTree::parent(int x){
while (x != 0) {
x = (x-1) / 2;
cout << "---";
}

}

void BinarySearchTree::traverseInOrder(int currentIndex){
if(array[currentIndex] != NULL) {
traverseInOrder(2 * currentIndex + 1);
parent(currentIndex);
cout << array[currentIndex] << endl;
traverseInOrder(2 * currentIndex + 2);

}
}

void BinarySearchTree::traversePreOrder(int currentIndex) {
if(array[currentIndex] != NULL){
traversePreOrder(2 * currentIndex + 1);
traversePreOrder(2 * currentIndex + 2);
parent(currentIndex);
cout << array[currentIndex] << " " << endl;
}

}

void BinarySearchTree::traversePostOrder(int currentIndex) {
if(array[currentIndex] != NULL) {
traversePostOrder(2 * currentIndex + 1);
parent(currentIndex);
cout << array[currentIndex] << " " << endl;
traversePostOrder(2 * currentIndex + 2);
}
}

int main () {
BinarySearchTree frank(5);
frank.insertInTree(4);
frank.insertInTree(6);
frank.insertInTree(9);
frank.insertInTree(3);
frank.insertInTree(2);
frank.searhInTree(1);
frank.traverseInOrder(0);
};

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.