How to create binary tree with iterative algorithm?

Question:

I'm making a program that allocates a dictionary in memory to check for misspelled words in text files. The function below converts dictionary words to integers and stores them in tree structures.

  • My question is how to correctly and iteratively write the part of the code that stores the numbers in the tree ( from line 24 onwards ).

I saw many examples, but all recursive and I didn't understand very well, feel free to give any kind of example to other users who may have the same question.

typedef struct arvore
{
    unsigned int n;
    struct arvore *esq, *dir;
}arvore;

arvore *raiz;

unsigned int
BPHash(const char* str, unsigned int len)
{
    unsigned int hash;
    for (unsigned int i = 0; i < len; str++, i++)
        hash = hash << 7 ^ (*str);
    return hash;
}

bool
load(const char *dict)
{
    FILE *fp = fopen(dict, "r"); // dict = arquivo que serve como dicionário
    if (fp == NULL)
        return false;

    char str[LENGTH+1]; // LENGTH = tamanho máximo da string (45)
    unsigned int strtam, hash; // Tamanho da string e string convertida em inteiro com função hash
    struct arvore dicio = {0, NULL, NULL};
    raiz = &dicio; // Ponteiro global

    while (fgets(str, LENGTH, fp) != NULL)
    {
        strtam = strlen(str);
        hash = BPHash(str, strtam); // BPHash = função hash

        if (raiz->n == 0) // Minha dúvida se refere as linhas abaixo
            raiz->n = hash;

        else if (raiz->n < hash)
        {
            raiz->esq = (arvore*)malloc(sizeof(arvore));
            raiz->dir = NULL;
            raiz->n = hash;
        }

        else
        {
            raiz->dir = (arvore*)malloc(sizeof(arvore));
            raiz->esq = NULL;
            raiz->n = hash;
        }
    }

    return true;
}

Answer:

Your first problem is that the root of the tree ( dicio ) is declared inside the load function itself, statically allocated on the execution stack (local variables are allocated on the execution stack). This means, that when the function finishes, the corresponding part of the execution stack will be cleared and with it the root of the tree. The root could still be retrieved by the raiz global variable, but this will be a pointer that will point to a part of the stack that no longer exists and that will soon be overwritten, thus becoming garbage.

The best solution for this would be to return the root of the tree or NULL if it cannot be created. Avoid using global variables, as doing so is bad programming practice. But as you are being forced to work in this way, then unfortunately there is no other way out.

Another problem is that your tree has a maximum of three nodes: raiz , raiz->dir and raiz->esq . By the way, you will only have two, because when you create the left node, you delete the right one and vice versa. Also, you delete these nodes without deallocating them, causing a memory leak. You are never creating or accessing us on deeper levels.

Your revised code is this:

// LENGTH = tamanho máximo da string
#define LENGTH 45

// função hash
unsigned int BPHash(const char *str, int len) {
    unsigned int hash = 0;
    for (unsigned int i = 0; i < len; str++, i++) {
        hash = hash << 7 ^ (*str);
    }
    return hash;
}

typedef struct arvore {
    unsigned int n;
    struct arvore *esq, *dir;
} arvore;

arvore *raiz = NULL;

bool load(const char *dict) {

    // Primeiro, destroi qualquer árvore que já houvesse antes, para evitar vazamento de memória.
    destruir_arvore(raiz);
    raiz = NULL;

    FILE *fp = fopen(dict, "r"); // dict = arquivo que serve como dicionário
    if (fp == NULL) return false;

    char str[LENGTH + 1];

    while (fgets(str, LENGTH, fp) != NULL) {
        arvore *novo = (arvore *) malloc(sizeof(arvore));
        novo->n = BPHash(str, strlen(str));
        novo->esq = NULL;
        novo->dir = NULL;

        arvore *no = raiz;

        while (1) {
            if (no == NULL) {
               raiz = novo;
               break;
            } else if (no->n < hash) {
                if (no->esq == NULL) {
                    no->esq = novo;
                    break;
                }
                no = no->esq;
            } else {
                if (no->dir == NULL) {
                    no->dir = novo;
                    break;
                }
                no = no->dir;
            }
        }
    }

    return true;
}

Notice that we have two while s here. The external while traverses the file reading its strings, and at each iteration, a novo node is created. The inner while uses a pointer no , which starts at the raiz and moves down the tree ( no = no->esq; and no = no->dir; ) until it finds an empty place where the novo node can be inserted. When the novo node is inserted into the tree, it break; in the internal while . The if (no == NULL) is for creating the root of the tree. This approach still has the advantage that zero is not special and the function works even if BPHash returns zero. No recursion is used here.

A function to destroy the created tree(s) is also needed in order to avoid memory leaks (this time with recursion, as the non-recursion version is much more complicated):

void destruir_arvore(arvore *no) {
    if (no == NULL) return;
    destruir_arvore(no->esq);
    destruir_arvore(no->dir);
    free(no);
}

Of course, this all depends on whether the BPHash function has been properly implemented (it lacked initialization of the hash with zero in it). I don't know if the implementation is adequate or not. I don't know if this tree will actually be useful for what you want either, but if it is, then it's the way I put it above that you're going to build it.

Scroll to Top