Tree Code in C++ A. Write a program to store a tree as an array. In your test pr

Question

Tree Code in C++

A. 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. Write a function to add an element to an existing tree.

C. Write a function to delete an element from an existing tree.

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

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

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

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

H. Write a function to find the children of a specified node.

I. Write a function to find the parent of a specified node.

Explanation / Answer

#include<iostream>
using namespace std;

public BST
{
private:
    int size;
    int* array;

    void add(int x);
    void find(int x);
    void inorder(int currentIndex);
    void preOrder(int currentIndex);
    void postOrder(int currentIndex);
    void parent(int x);
    int extendSize(int x);
public:
    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::add(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 BST::find(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 BST::parent(int x){
    while (x != 0) {
        x = (x-1) / 2;
        cout << "---";
    }

}

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

    }
}

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

}

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

int main () {
    BST frank(5);
    object.add(4);
    object.add(6);
    object.add(9);
    object.add(3);
    object.add(2);
    object.find(1);
    object.inorder(0);
};

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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