Skip to main content
2 de 2
correções de texto

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.