Introdução a árvores binárias

Árvores
Uma árvore é uma estrutura de interligação de "nós" bastante útil para construir estruturas hierárquicas, como determinados esquemas de expressões aritméticas, árvores genealógicas, esquemas de indexação etc.

A árvore parte de um nó especial, chamado raiz, e vai se "ramificando" em nós internos, terminando nos nós-folha. O grau de um nó é seu número de filhos. O grau de uma árvore é o grau máximo de seus nós. Altura de um nó é 1 + o número de ramos para alcançar a raiz. A estrutura em árvore facilita algumas operações. Por exemplo, considere que numa árvore genealógica, cada nó aponta para a mãe à esquerda e para o pai à direita :

Na figura, o nó contém somente um nome, mas poderia conter várias informações. A árvore contém 15 nós, mas encontrar um nó nela custaria somente 4 comparações – no pior caso. Uma árvore especialmente interessante em computação é a árvore binária de busca, em que cada nó tem no máximo dois nós filhos, organizados segundo uma determinada ordem.

Uma árvore não-binária pode ser simplificada para uma árvore binária. Imagine que queiramos representar um tipo de genealogia em que cada homem gera outros, representando os filhos mais velhos à esquerda e os mais novos à direita. Por exemplo, João gerou Carlos, Davi e Paulo, onde Carlos é o mais velho e Paulo é o mais novo. Da mesma forma, Carlos gerou Pedro e Marcos, Davi gerou Lucas e Paulo gerou Mateus :

As mesmas relações de parentesco pode ser representadas numa árvore binária, em que cada nó pode ter seu filho mais velho à direita e um irmão à esquerda.

A sequência dos dados de entrada é importante. Compare, no quadro abaixo, o formato da árvore produzida quando se altera a sequência dos dados de entrada. No caso mais à direita, vemos que uma sequência em ordem gera uma árvore que pode ser considerada como uma lista. No caso, uma lista descendente à direita. Analogamente, uma sequência em ordem invertida gera uma lista descendente à esquerda.