To work with trees, we have to define a way of walking the paths of it. We have some forms:
Walk:
- visit the root
- runs through the left subtree
- runs through the right subtree
Walk in-fixed:
- runs through the left subtree
- visit the root
- runs through the right subtree
Post-fixed walk:
- runs through the left subtree
- runs through the right subtree
- visit the root
Keep in mind that the shape the tree is in is also important. In your photo, the tree is not balanced, That is, both the left side of the root and the right side are not of the same height. To make a search less expensive, you can make an algorithm to balance the tree first (sometimes worthwhile, computationally or not, it depends on how unbalanced the tree is) and then look for the element in question.
You can define by a file a sequence of letters (nodes) and points (non-nodes) that define how this tree will be built. If I adopt that my algorithm builds a tree from left to right and then goes back to the parent node, we can have for example:
Ex: A B D . . . C E . . F . .
We would have the following tree
Note that my tree is balanced.
I only know the C language. If you know the concept of recursion, pointers, files, I think you can understand the principle.
You can then create a struct
to define each node, with dice (letter) and two pointers inside, as each node always has a left and right side.
/*no de uma arvore*/
typedef struct no{
char dado;
struct no *esquerda, *direita;
}arvore;
To build a tree, I do it recursively, because this data structure is good for this:
/*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));
}
}
Once built, I can walk the tree:
/*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);
}
}
The output will be the same as defined in the file: A B D . . . C E . . . F . .
Well, to check if every node you’ve gone through has the content searched, just compare it. I hope I’ve helped with that.
Dear Lucas, I’ve been trying for years to unravel the idea of this kind of algorithm. You managed to do what all my teachers and books failed to: Give good examples and clarify definitively the concept of tree search. I will take note and practice where I ended up in my studies. My very much THANK YOU! Great hug and excellent new year!
– duhspbr