10

Venho tentando criar uma função recursiva a partir a função que lista uma arvore binaria em ordem.

Essa função retornaria o N-ésimo termo, em ordem, de uma arvore binaria de busca.

Cada nodo se encontra no seguinte formato:

typedef struct nodo
{
    int Elemento;

    struct Nodo *Esquerda;

    struct Nodo *Direita;

}Nodo;

Função que lista os elementos de uma árvore em ordem, e a qual estou me baseando.

void ListarEmOrdem(Nodo* T)
    {
        if (T != NULL)
        {
            ListarEmOrdem(T->Esquerda);

            printf("%d\n",T->Elemento);

            ListarEmOrdem(T->Direita);
        }
    }

Exemplo da função:

Entrada: ponteiro para a raíz duma árvore e N
Saída: N-elemento

Elementos de uma árvore em ordem: 2,5,8,44 e 78

se F(T,4)

então, F(T,4) retorna = `44`

Como é o procedimento?

3 Respostas 3

6

Eu vi a resposta do @pcccj e concordo com o que ele diz, sobre retornar o item, e não apenas escrever seu valor. Existem várias formas se de fazer isso, desde um algoritmo genial que manipule o retorno da função de busca com maestria até um algorítmo simples mas que faça uso das ferramentas do C.

Como eu não sou tão inteligente assim, aqui vai um algoritmo simples ;)

#include<stdio.h>
#include<stdlib.h>

// Declara o formato dos nodos da árvore, e cria o tipo
struct nodo {
    int Elemento;
    struct nodo *Esquerda;
    struct nodo *Direita;
};

typedef struct nodo Nodo;

// Insere elementos na árvore
void InsereNodo(Nodo **raiz, Nodo *item) {
    if (!*raiz) {
        *raiz = item;
        return;
    }

    if (item->Elemento < (*raiz)->Elemento)
        InsereNodo(&(*raiz)->Esquerda, item);
    else
        InsereNodo(&(*raiz)->Direita, item);
}

// Escreve o valor de cada elemento da árvore, in-order
void ListarEmOrdem(Nodo *raiz){
    if (raiz->Esquerda)
        ListarEmOrdem(raiz->Esquerda);

    printf("%d\n", raiz->Elemento);

    if (raiz->Direita)
        ListarEmOrdem(raiz->Direita);
}

// Percorre a árvore, por profundidade, parando ao encontrar o n-ésimo elemento
void ProcuraProfundidade(Nodo *raiz, int **posicao, int limite, Nodo **NodoEncontrado){
    if (raiz->Esquerda)
        ProcuraProfundidade(raiz->Esquerda, posicao, limite, NodoEncontrado);

    if (!*NodoEncontrado){
        if((**posicao)++ == limite){
            *NodoEncontrado = raiz;
            return;
        }

        if (raiz->Direita)
            ProcuraProfundidade(raiz->Direita, posicao, limite, NodoEncontrado);
    }
}

// Função intermediária de busca; mantém uma assinatura decente e lida com exceções
Nodo* Procura(Nodo *raiz, int posicao){
    if (posicao < 1)
        return NULL;
    else if (!raiz)
        return raiz;
    else {
        Nodo *NodoEncontrado = NULL;
        int *inicial = malloc(sizeof(int));
        *inicial = 1;
        ProcuraProfundidade(raiz, &inicial, posicao, &NodoEncontrado);
        return NodoEncontrado;
    }
}


int main(int argc, char **argv){
    Nodo *raiz, *atual;
    int i;

    raiz = NULL;

    // Cria uma árvore de 7 elementos aleatórios
    for (i = 0; i < 7; i++) {
        atual = (Nodo*)malloc(sizeof(Nodo));
        atual->Esquerda = atual->Direita = NULL;
        atual->Elemento = rand();
        InsereNodo(&raiz, atual);
    }

    // Escreve todos os elementos da árvore
    printf("Lista de elementos\n----------\n");
    ListarEmOrdem(raiz);

    // Procura por todas as posições, de 0 a n+1, para cobrir pelo menos 2 casos de erro
    printf("\n\nResultado das buscas\n----------\n");
    for (i = 0; i <= 8; i++){
        atual = Procura(raiz, i);
        if (atual)
            printf("%d: %d\n", i, atual->Elemento);
        else
            printf("%d: %p\n", i, atual);
    }

    return EXIT_SUCCESS;
}

Basicamente, a busca funciona exatamente igual à função de escrita, mas adiciona condições de parada para evitar buscar toda a árvore quando você atinge a posição que gostaria.

Para controle, usa 2 ponteiros-para-ponteiros, para que cada sub-chamada da função controle os mesmos valores. Essa é a parte em que eu troco um algoritmo genial por usar as ferramentas da linguagem de forma efetiva. Funciona que é uma maravilha!

No final das contas, o resultado final é mais próximo do que você imaginaria naturalmente:

  1. percorra a árvore

  2. para cada elemento adicione um ao contador

  3. se o contador for igual à posição que quiser

    1. retorne o elemento

Se quiser saber mais sobre ponteiros: http://www.mtm.ufsc.br/~azeredo/cursoC/aulas/c600.html

1
  • Acho que seria melhor alocar inicial na pilha ao invés de usar malloc (você esqueceu de darfree, btw).
    – hugomg
    Commented 17/11/2014 às 17:17
6

Uma maneira super simples de contornar as dificuldades desse problema é usar umas variáveis globais para os parâmetros da busca e pro valor de retorno, o que permite manter a função recursiva focada exclusivamente na iteração:

static int n_arvore;
static int k_alvo;
static int k_esimo_elemento;

void percorrerArvore(Nodo* T){
    if (T != NULL){
        percorrerArvore(T->Esquerda);

        if(n_arvore == k_alvo){ k_esimo_elemento = T->Elemento; }    
        +n_arvore;

        percorrerArvore(T->Direita);
    }
}

void kEsimoElemento(int k, Nodo * T){
    n_arvore = 0;
    k_alvo = k;
    percorrerArvore(T);
    if(k < n_arvore){
        return k_esimo_elemento;
    }else{
        /* Árvore não tem elementos o suficiente */
    }
}

Se você não quiser usar globais, você pode empacotar o estado numa struct:

struct kElemState {
    int n_arvore;
    int k_alvo;
    int k_esimo_elemento;
}

void percorrerArvore(struct kElemState *state, Nodo* T){ ... }

void kEsimoElemento(int k, Nodo * T){
    struct kElemState s;
    s.n_arvore = 0;
    s.k_alvo = k;
    percorrerArvore(&s, T);
    if(k < s.n_arvore){
        return s.k_esimo_elemento;
    }else{
        /* Árvore não tem elementos o suficiente */
    }
}

O legal mesmo seria se pudéssemos declarar a função percorreArvore dentro da função nEsimoElemento, com n_arvore sendo variáveis locais de nEsimoElemento. Isso combinaria a simplicidade da versão com variáveis globais com a localidade da versão com struct. Infelizmente, C não conta com essa funcionalidade.

Fora isso, você também pode adicionar uma otimização para parar a recursão depois que você achar o elemento que você estiver procurando. Tem muitas maneiras de fazer isso, essa aqui é só um exemplo:

int percorrerArvore(Nodo* T){
    if (T != NULL){
        percorrerArvore(T->Esquerda);

        if(k_alvo < n_arvore){ return; }

        if(k_alvo == n_arvore){ k_esimo_elemento = T->Elemento; }    
        +n_arvore;

        if(k_alvo < n_arvore){ return; }

        percorrerArvore(T->Direita);
    }
}
3

O ideal seria que a funcao retornasse o valor final(T->Elemento) através de um return, e não de um printf(). Mas fiquei sem ideia.

Talvez alguém possa completar.

int Kth(Nodo* T, int cont, int pos)
{
    if (T != NULL)
    {
        cont = Kth(T->Esquerda, cont, pos);

        if(cont != 0)
        {
            if(cont == pos)
            {
                printf("%d\n",T->Elemento);

                return T->Elemento;///o ideal seria que ele retornasse o valor de T->Elemento por aqui, e não pelo PRINTF, só que n sei como fazer
            }

            cont = cont +1;
        }

        cont = Kth(T->Direita, cont, pos);

        return cont;

    }
    else
    {
        if(cont == 0)
            return (cont +1);

        return cont;
    }
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .