Find a way inside a tree

Question

I have a question as to how to find a particular item within a tree. Even, I have no idea what it would be like for a user to implement a "tree" as an input (in this case, it would be an array?).

I even put an image below to try to contextualize my problem.

I know that obviously, the easiest way would be to implement a search algorithm, however, in addition to hundreds of examples I’ve seen in books (such as artificial ben Ooper intelligence, Thomas Cormen’s algorithms), none were clear in structuring the algorithm (other than by pseudo codes).

My question is:

• What would be the user input to search for a certain object inside a list? (how shows the picture inserted);

• How would this search be done? How would this example look in C or Lua (moon contain several tools for using tables, and from what I saw, most use this concept;

You don’t necessarily need him to make the best way, let alone be efficient (even he can go through all the houses to find the item).

Search tree:

The search begins at node A, goes through B, D, and ends at item F. Exit: Path A, B, D, F

Answer 1

To work with trees, we have to define a way of walking the paths of it. We have some forms:

Walk:

1. visit the root
2. runs through the left subtree
3. runs through the right subtree

Walk in-fixed:

1. runs through the left subtree
2. visit the root
3. runs through the right subtree

Post-fixed walk:

1. runs through the left subtree
2. runs through the right subtree
3. 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.