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
editarA á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
editarPara 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
editarCom 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
editarVimos 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
editarO 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.