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.