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
{
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;
}
``````

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.

``````// 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;

// 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