Para trabalhar com árvores, temos que definir uma forma de percorrer os caminhos da mesma. Temos algumas formas:
Caminhamento pré-fixado:
- visita a raiz
- percorre a sub-árvore da esquerda
- percorre a sub-árvore da direita
Caminhamento in-fixado:
- percorre a sub-árvore da esquerda
- visita a raiz
- percorre a sub-árvore da direita
Caminhamento pós-fixado:
- percorre a sub-árvore da esquerda
- percorre a sub-árvore da direita
- 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
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.