Arvore Binaria

Árvore binária

Uma árvore binária é uma estrutura de dados caracterizada por:
Ou não tem elemento algum (árvore vazia).
Ou tem um elemento distinto, denominado raiz, com dois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.
Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária.
Os nós de uma árvore binária possuem graus zero, um ou dois. Um nó de grau zero é denominado folha.
Em uma árvore binária, por definição, cada nó poderá ter até duas folhas, sendo que ela se compara com a abb (árvore binária de busca), apesar de não ter a propriedade da mesma ("na abb, existe uma regra na inserção")

Árvore binária de busca

Uma árvore binária de busca é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (esta é a forma padrão, podendo as subárvores serem invertidas, dependendo da aplicação). O objetivo desta árvore é estruturar os dados de forma flexível, permitindo busca binária.1
Nós - são todos os itens guardados na árvore
Raiz - é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8)
Filhos - são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3)
Pais - são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14)
Folhas - são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13)

Operações
Operações em uma árvore binária requerem comparações entre nós. Essas comparações são feitas com chamadas a um comparador, que é uma subrotina que calcula a ordem total (ordem linear) em dois valores quaisquer.
Busca

A