-1

Estou com uma dúvida a respeito de como encontrar um determinado item dentro de uma árvore. Inclusive, eu não faço a mínima ideia de como seria um usuário implementar uma "árvore" como uma entrada (no caso, seria uma matriz?).

Coloquei até uma imagem abaixo para tentar contextualizar meu problema.

Sei que obviamente, o caminho mais fácil seria implementar um algorítmo de busca, contudo, além de centenas de exemplos que eu já vi em livros (como inteligencia artificial de ben cooper, Algoritmos de Thomas Cormen), nenhum foi claro na estruturação do algoritmo (a não ser pelos pseudo códigos).

Minha pergunta é:

  • Como seria a entrada do usuário para que fosse buscado um determinado objeto dentro de uma lista? (como mostra a foto inserida);

  • Como seria feito essa busca? Como ficaria esse exemplo em C ou Lua (lua contêm diversas ferramentas para uso de tabelas, e pelo que vi, a maioria utiliza este conceito;

Não precisa necessariamente que ele faça o melhor caminho, muito menos que seja eficiente (inclusive ele pode percorrer todas as casas para achar o item).

Árvore de busca:

inserir a descrição da imagem aqui

A busca começa pelo nó A, passa pelo B, D, e chega ao final no item F. Saída: Caminho A, B, D, F

1 Resposta 1

2

Para trabalhar com árvores, temos que definir uma forma de percorrer os caminhos da mesma. Temos algumas formas:

Caminhamento pré-fixado:

  1. visita a raiz
  2. percorre a sub-árvore da esquerda
  3. percorre a sub-árvore da direita

Caminhamento in-fixado:

  1. percorre a sub-árvore da esquerda
  2. visita a raiz
  3. percorre a sub-árvore da direita

Caminhamento pós-fixado:

  1. percorre a sub-árvore da esquerda
  2. percorre a sub-árvore da direita
  3. visita a raiz

Tenha em mente que a forma em que árvore está também é importante. Na sua foto, a árvore não está balanceada, ou seja, tanto o lado esquerdo da raiz e o direito não estão da mesma altura. Para fazer uma busca menos custosa, pode-se fazer um algoritmo para balancear a árvore primeiro (as vezes vale a pena, computacionalmente ou não, depende o quão desbalanceada a árvore estiver) e depois procurar o elemento em questão.

Você pode definir por um arquivo uma sequência de letras (nós) e pontos(não-nós) que definam como essa árvore vai ser construída.Se eu adotar que meu algoritmo constrói uma árvore da esquerda pra direita e depois volta pro nó pai, podemos ter por exemplo:

Ex: A B D . . . C E . . F . . Teriamos a seguinte árvore

inserir a descrição da imagem aqui

Note que a minha árvore está balanceada.

Eu só conheço linguagem C. Se você souber o conceito de recursão, ponteiros, arquivos, acho que dá pra entender o princípio.

Você pode então criar uma struct para definir cada nó, com dado (letra) e dois ponteiros dentro, pois cada nó sempre tem um lado esquerdo e direito.

/*no de uma arvore*/
typedef struct no{
    char dado;
    struct no *esquerda, *direita;
}arvore;

Para construir uma árvore, eu faço de forma recursiva, pois essa estrutura de dados é boa para isso:

/*funcao que constroi uma arvore, de forma recursiva*/

/*eu passo o endereço do ponteiro que indica o inicio da minha árvore, que fica
na minha funcão principal*/
void constroiArvore(arvore **eainicio){

    char c;
    c=fgetc(arquivo);

    /*se encontrar '.' no arquivo, então o ponteiro aponta para NULL*/
    if(c =='.'){
        *eainicio= NULL;

    /*caso contrario, constroi os nos, sempre a esquerda primeiro*/
    }else{

        *eainicio = malloc(sizeof(arvore));
        (*eainicio)-> dado = c;

        constroiArvore(&((*eainicio)->esquerda));
        constroiArvore(&((*eainicio)->direita));


    }

}

Uma vez construída, posso percorrer a árvore:

/*funcao que imprime a arvore*/
void imprimeArvore(arvore *ainicio){

    /*se o ponteiro estiver apontando para null, entao significa que chegou em uma folha*/
    if (ainicio==NULL){
        printf(".");

    /*caso contrario, imprime o no, sempre a esquerda primeiro*/
    }else{

        printf("%c",ainicio->dado);

        imprimeArvore(ainicio->esquerda);
        imprimeArvore(ainicio->direita);

    }

}

A saída será a mesma que defini no arquivo: A B D . . . C E . . F . .

Bem, para verificar se a cada nó percorrido tem o conteúdo procurado, basta comparar. Espero que com isso eu tenha ajudado.

1
  • 1
    Caro Lucas, estou a anos tentando desvendar a ideia desse tipo de algorítimo. Você conseguiu fazer o que todos os meus professores e livros não conseguiram: Dar bons exemplos e esclarecer de forma definitiva o conceito de busca\árvores. Vou tomar nota e praticar aonde eu parei nos estudos. Meu muitíssimo OBRIGADO! Grande abraço e excelente ano novo!
    – duhspbr
    Commented 3/01/2020 às 4:49

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 .