아르보레 비나리아

26287 단어
struct arvbin {
    int info;
    struct arvbin *esq, *dir;
};
typedef struct arvbin TAB;


크리안도 데 움 노




TAB *TAB_cria(int info, TAB *esq, TAB *dir) {
    TAB *no = (TAB *) malloc(sizeof(TAB));
    no->info = info;
    no->esq = esq;
    no->dir = dir;
    return no;
}


Copiando 우마 아르보레


  • 정보 복사
  • Copiar as sub-arvores da esquerda e direita

  • TAB *copia(TAB *a) {
        if(!a)
            return NULL;
        return TAB_cria(a->info, copia(a->esq), copia(a->dir));
    }
    



    // identico
    TAB *copia(TAB *a) {
        if(!a)
            return NULL;
    
        // aloca uma nova arvore
        TAB *novo = (TAB *) malloc(sizeof(TAB));
    
        // copia a informação
        novo->info = a->info;
    
        // copia as subarvores
        novo->esq = copia(a->esq);
        novo->dir = copia(a->dir);
    
        return novo;
    }
    


    에스펠한도 우마 아르보레




    TAB *espelho(TAB *a) {
        if(!a)
            return NULL;
        return TAB_cria(a->info, espelho(a->dir), espelho(a->esq));
    }
    


    Encontrando menor/maior elemento de uma árvore




    TAB *maior(TAB *a) {
        if(!a)
            return a;
    
        TAB *result = a;
    
        // maior elem da sub-arv da esquerda
        TAB *e = maior(a->esq);
    
        // maior elem da sub-arv da direita
        TAB *d = maior(a->dir);
    
        // comparar o elemento da raiz com os maiores das sub-arvores
        if(e && e->info > result->info)
            result = e;    
        if(d && d->info > result->info)
            result = d;
        return result;
    }
    


    Comparando duas árvores




    int igual(TAB *a, TAB *b) {
        // duas arvores vazias
        if(!a && !b)
            return 1;
    
        // uma das arvores vazia, a outra nao
        if(!a || !b)
            return 0;
    
        // se as raizes forem iguais, as sub arvores tambem preciam ser iguas
        if(a->info == b->info)
            return igual(a->esq, b->esq) && igual(a->dir, b->dir);
        return 0;
    }
    


    Retirando os nos pares de uma árvore




    TAB *retira_pares(TAB *a){
        if(!a)
            return NULL;
    
        // retiro os pares das minhas duas sub-arvores
        a->esq = retira_pares(a->esq);
        a->dir = retira_pares(a->dir);
    
        // se a raiz for par...
        if(a->info % 2 == 0) {
    
            // se for uma folha
            if(!a->esq && !a->dir) {
                free(a);
                return NULL;
            }
    
            // trocar a raiz com um elem de uma sub-arvore
            // como ja foram tirado os pares das sub-arvores, garanto que esse elemento nao vai ser par
            TAB *aux = a->esq;
            if(!aux)
                aux = a->dir;
    
            // trocando
            int tmp = aux->info;
            aux->info = a->info;
            a->info = tmp;
    
            // depois da troca, tentar retirar de novo
            a = retira_pares(a);
        }
        return a;
    }
    


    Contando os nos




    int nn(TAB *a) {
        if(!a)
            return 0;
        return 1 + nn(a->esq) + nn(a->dir);
    }
    


    Contando os nos internos




    int ni(TAB *a) {
        if(!a)
            return 0;
    
        // se o no for folha
        if(!a->esq && !a->dir)
            return 0;
    
        // a raiz + os nos internos das sub-arvores
        return 1 + ni(a->esq) + ni(a->dir);
    


    콘탄도 오스 노스 폴하스




    int ni(TAB *a) {
        if(!a)
            return 0;
    
        // se o no for folha
        if(!a->esq && !a->dir)
            return 1;
    
        // os nos folhas das sub-arvores
        return nf(a->esq) + nf(a->dir);
    


    Transformando em um vetor




    int *ab2vet(TAB *a) {
        if(!a)
            return NULL;
        int n = nn(a);
        int *v = (int *) malloc(sizoef(int) * n);
        tovet(a, v);
        return v;
    }
    
    void tovet(TAB *a, int *vet) {
        if(!a)
            return;
        int pos = nn(a->esq);
        v[pos] = a->info;
        tovet(a->esq, v);
        tovet(a->dir, v + pos + 1);
    }
    


    Transformando em uma Lista Simplismente Encadeada




    TLSE *ab2lse(TAB *a) {
        if(!a)
            return NULL;
        return tolse(a, NULL);
    }
    
    TLSE *tolse(TAB *a, TLSE *l) {
        if(!a)
            return l;
        l = tolse(a->esq);
        l = TLSE_insere(l, a->info);
        l = tolse(a->dir);
        return l;
    }
    


    Transformando em uma Árvore Binária de Busca




    TABB *ab2abb(TAB *a) {
        if(!a)
            return NULL;
        int *v = ab2vet(a);
    
        // alguma funcao qualquer para ordenar v
        sort(v);
    
        return vet2abb(v, nn(a));
    }
    
    TABB *vet2abb(int *v, int n) {
        if(n == 0)
            return NULL;
        return TAB_cria(v[n/2], vet2abb(v, n/2), vet2abb(v + n/2 + 1, n - n/2 - 1));
    }
    

    좋은 웹페이지 즐겨찾기