How to create binary tree with iterative algorithm?

Question

How to create binary tree with iterative algorithm?

Navigation

#1 by (1 votes)

2

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

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

I have seen many examples, but all recursive and I do not quite understand, feel free to give any type of example to other users who may have the same doubt.

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

c struct

asked by anonymous 10.12.2017 / 00:22

1 answer

Problem in drawing chessboard with objects Write file in JSON

score 1 · Accepted Answer

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

The best solution to this would be to return the tree root or NULL if it can not be created. Avoid using global variables, as doing so is a bad programming practice. But as you are being forced to work that 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 . In fact, you only have two, because when you create the left node, you delete the right and vice versa. In addition, you delete these nodes without deallocating them, causing memory leaks. You are never creating or accessing nodes at 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 while external traverses the file by reading its strings, and at each iteration, a novo node is created. The% internal% uses a while pointer, which starts in no and goes down in the tree ( raiz and no = no->esq; ) until it finds an empty place where the no = no->dir; node can be inserted. When the novo node is inserted into the tree, a novo is added to the break; internal. The while is to create the root of the tree. This approach still has the advantage that zero is not special and the function works even if if (no == NULL) returns zero. Recursion is not used here.

A function to destroy the tree (s) created is also necessary in order to avoid memory leaks (this time with recursion, since the version without recursion 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 the BPHash function being properly implemented (it failed to initialize the BPHash with zero in it). I do not know if the implementation is appropriate or not. I also do not know if this tree will actually be useful to what you want, but if it is, it's the way I put it above that you will build it.