Uma Árvore nada mais é do que um grafo conexo sem ciclos, com um vértice (nó) especial, chamado raiz.
É uma Árvore sem uma raiz especificada.
Um Grafo formado por várias Árvores
A Árvore Binária possui até no máximo dois filhos por nó. Geralmente esse tipo de árvore é utilizada para a busca binária, onde permite uma menor quantidade de passos até chegar no nó desejado.
A Árvore Binária é estruturada de uma forma onde o nó X possui um peso Y, seu nó filho na esquerda possui o peso < Y, enquanto o nó filho na direita possui o peso > Y.
É quando todas as folhas (nós que não possuem descendentes) estão em uma mesma profundidade e todos os nós internos têm grau 2 (dois nós filhos).
O número de vértices em uma Árvore Binária Cheia é 2^(h+1) - 1, onde h é a altura da árvore.
Quando a altura é h, cada folha está no nível h ou h-1.
Os algoritmos de busca tem como base o método de procura de qualquer elemento dentro de um conjunto de elementos com determinadas propriedades.
{8, 3, 6, 10, 14, 1, 7, 13, 4}
Uma Árvore Binária é dita de busca, se para todos seus nós (vértices), temos que o elemento deste nó é maior que todos os elementos dos nós da subárvore à sua esquerda, e menor que todos os elementos dos nós da subárvore à sua direita.
- Uma Árvore com n vértices tem n-1 arestas.
- Em uma Árvore com n vértices, o número total de extremidades de arestas é 2n-2.
Percorre a Árvore a partir da seguinte ordem:
- Nó
- Descendente da esquerda
- Descendente da direita
//Pré-Orderm
const func = (node) => {
if(node != null) {
console.log(node)
func(node.children[0])
func(node.children[1])
}else console.log(null)
}
Percorre a Árvore a partir da seguinte ordem:
- Descendente da esquerda
- Nó
- Descendente da direita
//Orderm
const func = (node) => {
if(node != null) {
func(node.children[0])
console.log(node)
func(node.children[1])
}else console.log(null)
}
Percorre a Árvore a partir da seguinte ordem:
- Descendente da esquerda
- Descendente da direita
- Nó
//Pós-Orderm
const func = (node) => {
if(node != null) {
func(node.children[0])
func(node.children[1])
console.log(node)
}else console.log(null)
}
| Notação | Sequência | Equivalência |
|---|---|---|
|
Infixa Convencional |
Exibir a folha esquerda Exibir a raiz Exibir a folha direita |
Ordem |
|
Prefixa Polonesa |
Exibir a raiz Exibir a folha esquerda Exibir a folha direita |
Pré-Ordem |
|
Pósfixa Polonesa Inversa |
Exibir a folha esquerda Exibir a folha direita Exibir a raiz |
Pós-Ordem |
Infixa:
(3 * a) + (b + 5) - (4 / a)
Prefixa:
+ (* 3 a) (- (+ b 5) (/ 4 a))
Pósfixa:
(3 a *) ((b 5 +) (4 a /) -) +