Árvore binária

Segundo Marcos Laureano:

Uma árvore binária é um conjunto finito de elementos que está vazio ou é particionada em três subconjuntos.

Os subconjuntos da árvore são:

• raiz da árvore - elemento inicial (único);
• subárvore da esquerda - se vista isoladamente compõe uma outra árvore;
• subárvore da direita - se vista isoladamente compõe uma outra árvore.

A árvore pode não ter nenhum elemento (árvore vazia). A construção de uma árvore pode ser recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. Lembrando que recursividade é o processo de definir algo em termos de si mesmo e é, algumas vezes, chamado de definição circular. Assim, pode-se dizer que o conceito de algo recursivo está dentro de si, que por sua vez está dentro de si e assim sucessivamente, infinitamente, ou seja, se não tiver um mecanismo de saída ou de parada o algoritmo entrará em loop.

As árvores onde cada nó que não seja folha numa árvore binária tem subárvores esquerda e direita.