ASD-ARBORE

#include <iostream>

using namespace std;

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

class Arbore
{
public:
    Arbore(){root = NULL;}

    Node *root;
    void add(int x);
    Node *deletee(Node* current, int x);
    Node *findMaxim(Node* current);


    void RSD(Node* current);
    void SRD(Node* current);
    void SDR(Node* current);
};

void Arbore::add(int x)
{
    Node *p = new Node;
    p->st = NULL;
    p->dr = NULL;
    p->info = x;


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

    Node *temp = root;

    while(true)
    {
        if (x > temp->info && temp->dr == NULL)
        {
            temp->dr = p;
            break;
        }

        if (x < temp->info && temp->st == NULL)
        {
            temp->st = p;
            break;
        }

        if (x > temp->info)
            temp = temp->dr;
        else if (x < temp->info)
            temp = temp->st;
    }


}

Node* Arbore::findMaxim(Node* root)
{
    Node *temp = root;
    if (temp == NULL)
        return NULL;

    while (temp->dr != NULL)
        temp = temp->dr;

    return temp;
}

Node* Arbore::deletee(Node* current, int x)
{
    if (current == NULL)
        return NULL;
    else if (x < current->info)
        current->st = deletee(current->st, x); // cautam in suboarborele stang
    else if (x > current->info)
        current->dr = deletee(current->dr, x); // cautam in suboarborele drept
    else // daca valorile sunt egale, am ajuns la elementul cautat
    {
        //nod frunza
        if (current->dr == NULL && current->st == NULL)
        {
            delete current;
            current = NULL;
        }
        else if (current->dr == NULL) //cu un singur copil
        {
            Node* temp = current;
            current = current->st;
            delete temp;
        }
        else if (current->st == NULL)
        {
            Node* temp = current;
            current = current->dr;
            delete temp;
        }
        else // cu doi copii
        {
            Node* temp = findMaxim(current->st);
            current->info = temp->info;
            deletee(current->st, temp->info);
        }

    }
    return current;
}

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

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

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

int main()
{
    Arbore a;
    a.add(5);
    a.add(3);
    a.add(7);
    a.deletee(a.root,3);
    a.SDR(a.root);
    return 0;
}