Laborator-4-Arbori-binari-de-cautare.txt

#include <iostream>

using namespace std;

struct Node
{
    Node* st;
    Node* dr;
    int info;
};

class Tree
{
public:
    Node* root;
    void add(int value); //done
    Node* del(Node*, int value); //done
    void RSD(Node*); //done
    void SRD(Node*); //done
    void SDR(Node*); //done
    Node* findMaxim(Node* ); //done
    bool find(int value);//done
    int height(Node* ); //done
    int* sortedArray();
};

void Tree::add(int value)
{
    Node* newNode = new Node;
    newNode->st = NULL;
    newNode->dr = NULL;
    newNode->info = value;

    if(root == NULL)
    {
        root = newNode;
        return;
    }

    Node* temp = root;
    while(1)
    {
        if(value > temp->info && temp->dr == NULL)
        {
            temp->dr = newNode;
            break;
        }
        if(value < temp->info && temp->st == NULL)
        {
            temp->st = newNode;
            break;
        }
        if(value > temp->info)
            temp = temp->dr;
        else if(value < temp->info)
            temp = temp->st;
    }
}

bool Tree::find(int value)
{
    Node* temp = root;
    if(temp == NULL)
        return false;
    else if (temp->info == value)
        return true;

    while(temp != NULL && temp->info != value)
    {
        if(temp->info > value)
        {
            if(temp->st != NULL)
                temp = temp->st;
            else return false;
        }
        else if(temp->info < value)
        {
            if(temp->dr != NULL)
                temp = temp->dr;
            else return false;
        }
    }
    return (temp->info == value);
}

int Tree::height(Node* current)
{
    if(current == NULL)
        return 0;

    int leftHeight = height(current->st);
    int rightHeight = height(current->dr);

    return (max(leftHeight, rightHeight) +1);
}

Node* Tree::findMaxim(Node* root)
{
    Node* temp = root;
    if(temp == NULL)
        return NULL;
    while(temp->dr != NULL)
        temp = temp->dr;
    return temp;
}

Node* Tree::del(Node* current, int value)
{
    if(current == NULL)
        return NULL;
    else if(value < current->info)      //daca valoarea este mai mica decat valoarea nodului curent,
        current->st = del(current->st, value);      //cautam in subarborele stang
    else if(value > current->info)      //daca e mai mare,
        current->dr = del(current->dr, value);      //cautam in subarborele drept
    else                                //daca valorile sunt egale (am ajuns la nodul cautat)
    {
        ///leaf node
        if(current->dr == NULL && current->st == NULL)
        {
            delete current;
            current = NULL ;
        }
        ///one child
        else if(current->dr == NULL)
        {
            Node* temp = current;
            current = current->st;
            delete temp;
        }
        else if(current->st == NULL)
        {
            Node* temp = current;
            current = current->dr;
            delete temp;
        }
        ///two children
        else
        {
            Node* temp = findMaxim(current->st);        //cautam maximul in subarborele stang
            current->info = temp->info;     //interschimbam current cu maximul
            del(current->st, temp->info);       //aplicam stergerea pentru current
        }
    }
    return current;
}

void Tree::SRD(Node* current)
{
    if(current == NULL)
        return;
    SRD(current->st);
    cout<<current->info<<" ";
    SRD(current->dr);
}

void Tree::RSD(Node* current)
{
    if(current == NULL)
        return;
    cout<<current->info<<" ";
    RSD(current->st);
    RSD(current->dr);
}

void Tree::SDR(Node* current)
{
    if(current == NULL)
        return;
    SDR(current->st);
    SDR(current->dr);
    cout<<current->info<<" ";
}


int main()
{
    Tree ob;
    ob.root = NULL;
    ob.add(1);
    ob.add(4);
    ob.add(2);
    ob.add(0);
    ob.add(5);
    ob.SRD(ob.root);
    cout<<endl<<ob.find(4);
    cout<<"\nHeight is "<<ob.height(ob.root)<<'\n';
    ob.del(ob.root, 0);
    ob.SRD(ob.root);
    return 0;
}