758595

1-Árvores binárias

Introdução
Existem os mais diferentes tipos de árvores, no entanto, as árvores binárias são especiais e muito utilizadas nas mais diversas aplicações porque quando ordenadas permitem que pesquisas, inclusões e exclusões de dados em sua estrutura sejam extremamente rápidas.

Árvores binárias
Uma árvores binárias é uma árvore direcionada com as seguintes propriedades:
Todos os nodos têm no máximo dois filhos.
Cada filho é rotulado como filho da esquerda ou um filho da direita.
O filho da esquerda precede o filho da direita na ordenação dos filhos em um nodo.
A subárvore enraizada no filho da direita ou filho da esquerda de um nodo interno v é chamada de subárvore da direita e subárvore da esquerda de v respectivamente. Uma árvore binária é própria de cada nodo tem zero ou dois filhos. Algumas pessoas se referem a estas árvores como árvores binárias cheias. Logo em uma árvore binária própria de nodo interno tem exatamente dois filhos. Uma árvores binária que não é própria é imprópria.

• Exemplo
– árvores binárias representando expressões aritméticas:
• nós folhas representam operandos
• nós internos operadores
• exemplo: (3+6) *(4-1) +5 Desenvolvimento

1.1-Inserção de nós

A inserção começa com uma busca; procurando pelo valor, mas se não for encontrado, procuraremos as sub-árvores da esquerda ou direita como na busca. Eventualmente, alcançaremos a folha, e então inserimos o valor nesta posição. Ou seja nós examinamos a raiz e introduzimos um nó novo na sub-árvore da esquerda se o valor novo é menor do que a raiz, ou na sub-árvore da direita se o valor novo for maior do que a raiz.
Uma outra maneira de explicar a inserção é que a fim de introduzir um nó novo na árvore, seu valor é primeiro comparado com o valor da raiz. Se seu valor for menos do que a raiz, é comparado então com o valor do filho da esquerda da raiz. Se seu valor for maior, está comparado com o filho da direita da raiz. Este processo continua