BlitzMax/Lições/Árvore

Ao contrário das listas, as árvores são estruturas de dados não lineares, ou seja, podem ter múltiplos sucessores, servem principalmente para aplicações de hierarquia ou de busca de elementos. Cada árvore é formada por nós, sempre iniciada por um nó raiz podendo ter nós galhos (que possuem filhos), ou nós folhas (que não possuem filhos). Existem vários tipos de arvores com conceitos e aplicações diferentes.

Árvore binária

A árvore binária é o tipo de árvore mais simples de todas. Cada nó é formado por apenas um elemento (variável) e aponta para dois filhos, o da esquerda (sempre menor) e o da direita (sempre maior).

Protótipo do nó da árvore binária

Para criar o nó da arvore binária vamos usar o comando Type, colocar o campo para entrar o valor do nó da árvore e os dois ponteiros do tipo nó que apontarão para a esquerda e para direita.

Type No
    Field noEsquerdo:No Ptr
    Field variavel
    Field noDireito:No Ptr
EndType

Iniciando uma árvore binária

Com o protótipo criado, vamos iniciar a arvore em si, criando um ponteiro que aponta para a raiz.

Type No
    Field noEsquerdo:No Ptr
    Field variavel
    Field noDireito:No Ptr
EndType

raiz:No Ptr

Inserindo um elemento em uma árvore binária vazia

Vimos anteriormente que cada nó da árvore irá receber um elemento, a princípio vemos que a nossa árvore está vazia, por isso o elemento inserido no nó será diretamente colocado na raiz. Vamos criar uma função que irá receber como parâmetro a raiz e o número a ser inserido.

Type No
    Field noEsquerdo:No Ptr
    Field variavel
    Field noDireito:No Ptr
EndType

raiz:No Ptr

Function inserir(pegarRaiz:No Ptr, pegarElemento)
    pegarRaiz:No = New No
    pegarRaiz.noEsquerdo = Null
    pegarRaiz.variavel
    pegarRaiz.noDireito = Null
EndFunction

Inserindo mais elementos na árvore binária

O exemplo anterior mostrou como inserir um elemento apenas em uma árvore vazia, agora vamos ver como fazer para inserir mais elementos e construir a nossa árvore propriamente dita. Para isso iremos criar uma condição If, para se o nó estiver vazio utilizar o procedimento anterior. Se não então fazemos as comparações:

• Se o número a ser inserido for MENOR que o do nó, ir para o filho esquerdo.
• Se o número a ser inserido for MAIOR que o do nó, ir para o filho direito.

Type No
    Field noEsquerdo:No Ptr
    Field variavel
    Field noDireito:No Ptr
EndType

raiz:No Ptr

Function inserir(pegarRaiz:No Ptr, pegarElemento)
    If(pegarRaiz = Null)
        pegarRaiz:No = New No
        pegarRaiz.noEsquerdo = Null
        pegarRaiz.variavel
        pegarRaiz.noDireito = Null
    ElseIf(pegarElemento < pegarRaiz.variavel)
        inserir(pegarRaiz\noEsquerdo, pegarElemento)
    ElseIf(pegarElemento > pegarRaiz.variavel)
        inserir(pegarRaiz\noDireito, pegarElemento)
    EndIf
EndFunction

Caso a árvore não esteja vazia e se coloque algum elemento que seja IGUAL ao de algum nó não haverá inserção.