arvore-binaria.cpp

/* Estrutura de Dados II - Árvore Binária */

#include <iostream>
#include <windows.h>

typedef int tipochave;

using namespace std;

typedef struct aux {
    tipochave chave;
    aux *esq, *dir;
} no;

typedef no* pont;

pont inicializa()
{
    return nullptr;
}

pont criaNo(tipochave c)
{
    pont novoNo = new no;
    
    novoNo->chave = c;
    novoNo->dir = nullptr;
    novoNo->esq = nullptr;

    return novoNo;
}

pont adiciona(pont raiz, pont no)
{
    if (!raiz) return no;
    if (no->chave < raiz->chave)
        raiz->esq = adiciona(raiz->esq, no);
    else
        raiz->dir = adiciona(raiz->dir, no);
}

pont adiciona(pont raiz, tipochave c)
{
    return adiciona(raiz, criaNo(c));
}

void exibirArvore(pont raiz)
{
    if (!raiz) return;
    cout << raiz->chave;
    cout << '(';
        exibirArvore(raiz->esq);
        exibirArvore(raiz->dir);
    cout << ')';
}

pont contem(pont raiz, tipochave c) 
{
    if (!raiz)
        return nullptr;
    if (raiz->chave == c)
        return raiz;
    if (c < raiz->chave)
        contem(raiz->esq, c);
    else
        contem(raiz->dir, c);
}

int contarNos(pont raiz)
{
    if (!raiz)
        return 0;
    return (contarNos(raiz->esq) + 1 + contarNos(raiz->dir));
}

/*
    Busca binária não recursiva. Retorna o ponteiro do nó buscado.
    Abastesce pai com o ponteiro do nó pai deste.
*/
pont buscarNo(pont raiz, tipochave c, pont *pai)
{
    pont atual = raiz;
    *pai = nullptr;
    
    while (atual) {
        if (atual->chave == c)
            return atual;

        *pai = atual;

        if (atual->chave > c)
            atual = atual->esq;
        else
            atual = atual->dir;
    }
    return nullptr;
}

pont remvoverNo(pont raiz, tipochave c)
{
    pont pai, no, p, q;
    no = buscarNo(raiz, c, &pai);
    
    
    if (!no) // Se o nó não for encontrado na árvore
        return raiz;
    
    if (!no->esq || !no->dir) { // Caso o nó encontrado possua apenas um filho
        if (!no->esq)
            q = no->dir;
        else
            q = no->esq;
    } else { // Tem os dois filhos
        p = no;
        q = no->esq;
        while (q->dir) {
            p = q;
            q = q->dir;
        }
        if (p != no) {
            p->dir = q->esq;
            q->esq = no->esq;
        }
        q->dir = no->dir;
    }

    if (!pai) {
        delete no;
        return q;
    }

    if (c < pai->chave)
        pai->esq = q;
    else
        pai->dir = q;

    delete no;
    return raiz;
}

int main() {
    pont arv = inicializa();

    arv = adiciona(arv, 2);
    arv = adiciona(arv, 1);
    arv = adiciona(arv, 4);
    arv = adiciona(arv, 3);

    exibirArvore(arv);

    cout << endl;
    system("pause");
    return 0;
}