binary_search_tree.cpp

#include <iostream>

using namespace std;

class Node {

    int value;
    Node* parent;
    Node* left;
    Node* right;

  public:

    Node(int v) {value = v; left = NULL; right = NULL; parent = NULL;}
    int getValue(void) {return value;}
    Node* getParent(void) {return parent;}
    //int getParentValue(void) {return}
    Node* getLeft(void) {return left;}
    Node* getRight(void) {return right;}
    void setParent(Node* p) {parent = p;}
    void setLeft(Node* l) {left = l; if(l != NULL) l->parent = this;}
    void setRight(Node* r) {right = r; r->parent = this;}
};

class SortedArray {

    int sorted_array[40];
    int size_ar;
  public:
    SortedArray() {size_ar = 0;}
    void Insert(int num) {sorted_array[size_ar] = num; size_ar++;}
    int getSize() {return size_ar;}
    void print() {

        for(unsigned int i=0; i<size_ar; i++)
            cout << sorted_array[i] << endl;
    }
};

class Queue {

    Node* elements[40];
    int first;
    int last;

  public:
    Queue(){first = 0; last = -1;}
    void Enqueue(Node* node) {elements[++last] = node;}
    Node* Dequeue() {return elements[first++];}
    bool QueueNotEmpty() {return first <= last;}

};
Node* Find(Node* n, int key){

    //cout << n->getValue() << endl;

    if (n == NULL){
        cout << "Node of value " << key <<" not found!" << endl;
        return NULL;
    }

    if((key == n->getValue()))
        //cout << "Key found: " << n->getValue() << endl;
        return n;

    if (key < n->getValue())
        Find(n->getLeft(),key);

    else
        Find(n->getRight(), key);
}

Node* MinorKey(Node* n){

    if (n->getLeft() == NULL){
        cout << "The minor key is: " << n->getValue() << endl;
        return n;
    } else {
        return MinorKey(n->getLeft());
    }
}

Node* BiggerKey(Node* n){

    if (n->getRight() == NULL) {
        cout << "The bigger key is: " << n->getValue() << endl;
        return n;
    } else {
       return BiggerKey(n->getRight());
    }
}

void Insert(Node* n, int key){

    cout << n->getValue() << endl;
    if (key < n->getValue()){

        if (n->getLeft() == NULL){

            Node* aux = new Node(key);
            n->setLeft(aux);
            cout << "Node inserted: " << aux->getValue() << endl;
        } else {
            Insert(n->getLeft(), key);
        }
     } else {

        if (n->getRight() == NULL){

            Node* aux = new Node(key);
            n->setRight(aux);
            cout << "Node inserted: " << aux->getValue() << endl;
        } else{
            Insert(n->getRight(), key);
        }
     }
}


bool Delete(Node* n, int key) {

    Node* node = Find(n, key);

    if (node->getLeft() == NULL && node->getRight() == NULL) {
        cout << "Node deleted: " << node->getValue() << endl;

        if (node->getValue() <= node->getParent()->getValue()){
            node->getParent()->setLeft(NULL);
            node = NULL;
            return true;
        } else {
            node->getParent()->setRight(NULL);
            node = NULL;
            return true;
        }
    }

    if (node->getLeft() != NULL && node->getRight() == NULL) {
        cout<< "Node deleted: " << node->getValue() << endl;

        if (node->getValue() <= node->getParent()->getValue()){

            cout << "1" << endl;
            node->getParent()->setLeft(node->getLeft());
            node->getLeft()->setParent(node->getParent());
            node = NULL;
            return true;
        } else {

            node->getParent()->setLeft(node->getRight());
            node->getRight()->setParent(node->getParent());
            node = NULL;
            return true;
        }
    }

    if(node->getLeft() == NULL && node->getRight() != NULL) {
        cout<< "Node deleted: " << node->getValue() << endl;

        if(node->getValue() <= node->getParent()->getValue()) {

            node->getParent()->setLeft(node->getRight());
            node->getRight()->setParent(node->getParent());
            node = NULL;
            return true;
        } else {

            node->getParent()->setRight(node->getRight());
            node->getRight()->setParent(node->getParent());
            node = NULL;
            return true;
        }
    }

    /*if (n->getLeft() != NULL && n->getRight() != NULL) {

        Node* node = MinorKey(n->getRight());
        cout << node->getValue() << endl;

        node->setParent(n->getParent());
        n->getRight()->setParent(node);
        node
        if(n->getValue() >= n->getParent()->getValue())
            n->getParent()->setRight(node);
        else
            n->getParent()->setLeft(node);
    }*/

}

SortedArray my_array;

Node* DepthFirstSearch(Node* n){

    if (n != NULL){

        DepthFirstSearch(n->getLeft());
        my_array.Insert(n->getValue());
        DepthFirstSearch(n->getRight());
    }
}

Queue q;

void BreadthFirstSearch(Node* n){

    if (n != NULL){

        q.Enqueue(n);
        cout << n->getValue() << endl;
        while(q.QueueNotEmpty()) {

            Node* aux = q.Dequeue();


            if (aux->getLeft() != NULL)
                 BreadthFirstSearch(aux->getLeft());

            if (aux->getRight() != NULL)
                 BreadthFirstSearch(aux->getRight());

        }
    }

}

int PathLength(Node* n, int key) {

    int len = 0;

    if (n->getValue() == key)
        return len;

    else {

        while(n->getValue() != key) {

            if (key < n->getValue())
                n = n->getLeft();
            else
                n = n->getRight();
            len++;
        }
    }
    return len;
}

int main (){

    Node n1(21);
    Insert(&n1,13);
    Insert(&n1,30);
    Insert(&n1,16);
    Insert(&n1,28);
    Insert(&n1,50);
    Insert(&n1,15);
    Insert(&n1,18);
    Insert(&n1,42);
    /*Node n2(13);
    Node n3(30);
    Node n4(16);
    Node n5(28);
    Node n6(50);
    Node n7(15);
    Node n8(18);
    Node n9(42);

    n1.setLeft(&n2);
    n1.setRight(&n3);
    n2.setRight(&n4);
    n4.setLeft(&n7);
    n4.setRight(&n8);
    n3.setLeft(&n5);
    n3.setRight(&n6);
    n6.setLeft(&n9);*/
    cout << endl;
    cout << "Node 18 path length: " << PathLength(&n1, 18) << endl;

    cout << endl;
    cout << "Search:" << endl;
    Node* aux = Find(&n1, 15);
    cout << "Node found: " << aux->getValue() << endl;
    cout << endl;

    cout << "Search:" << endl;
    aux = Find(&n1, 42);
    cout << "Node found: " << aux->getValue() << endl;
    cout << endl;

    MinorKey(&n1);
    BiggerKey(&n1);
    cout << endl;

    Insert(&n1,40);
    cout << endl;
    Insert(&n1,14);
    cout << endl;

    cout << "Search:" << endl;
    aux = Find(&n1, 14);
    cout << "Node found: " << aux->getValue() << endl;
    cout << endl;

    Find(&n1, 200);
    cout << endl;

    Insert(&n1,2);
    cout << endl;

    aux = MinorKey(&n1);
    cout << "Parent of the minor key " << aux->getValue() << " is " << (aux->getParent()->getValue()) << endl;
    cout << endl;

    //Delete(&n1, 2);

    //cout << endl;
    //Find(&n1,2);

    //cout<< endl;
    Insert(&n1, 1);
    cout << endl;

    Delete(&n1, 2);
    cout << endl;

    Find(&n1, 2);
    cout << endl;

    aux = MinorKey(&n1);
    cout << "Parent of the minor key " << aux->getValue() << " is " << (aux->getParent()->getValue()) << endl;

    cout << endl;
    Insert(&n1, 29);
    cout << endl;

    Delete(&n1, 28);
    cout << endl;

    Find(&n1, 28);
    cout << endl;

    aux = Find(&n1, 29);
    cout << endl;

    cout << "Parent of the node 29 is " << (aux->getParent()->getValue()) << endl;

    cout << endl;
    DepthFirstSearch(&n1);

    cout << endl;
    cout << "Sorted Array size: " << my_array.getSize() << endl;

    cout << endl;
    cout << "Sorted elements: " << endl;
    my_array.print();

    cout << endl;
    cout << "BFS: " << endl;
    BreadthFirstSearch(&n1);


    return 0;
}