Mostre passo a passo a árvore binária resultante das seguintes operações:
(a) Inserção de 7, 8, 3, 4, 2, 1, 6, 5
(b) Mostre o percurso em pré-ordem, em-ordem e pós-ordem
© Remoção de 7 e 6

Passo 1

O enunciado pede para construirmos uma árvore binária de busca (BST) inserindo os valores 7, 8, 3, 4, 2, 1, 6, 5; depois mostrarmos os percursos pré-ordem, em-ordem e pós-ordem; e por fim removermos os nós 7 e 6. Vamos usar as regras de inserção e remoção em BST e as definições de cada tipo de percurso.

Passo 2

Para inserir em uma BST, comparamos o valor a inserir com o nó atual: se for menor, vamos para a subárvore esquerda; se for maior, para a direita; e repetimos até encontrar um lugar vazio. Começamos com 7, que vira a raiz.

Passo 3

Após inserir 7, a árvore é:
7

Passo 4

Agora inserimos 8. Como 8>7, vai para a direita de 7. A árvore fica:
7

8

Passo 5

Em seguida inserimos 3. Como 3<7, vai para a esquerda de 7. A árvore passa a ser:
7
/
3 8

Passo 6

Para inserir 4, começamos em 7 (4<7 → esquerda em 3), depois em 3 (4>3 → direita). Colocamos 4 à direita de 3:
7
/
3 8

4

Passo 7

Ao inserir 2: 2<7 (vai a 3), 2<3 (vai à esquerda). Fica:
7
/
3 8
/
2 4

Passo 8

Inserindo 1: 1<7→3; 1<3→2; 1<2→esquerda de 2. Resultado:
7
/
3 8
/
2 4
/
1

Passo 9

Inserindo 6: 6<7→3; 6>3→4; 6>4→direita de 4. Fica:
7
/
3 8
/
2 4
/
1 6

Passo 10

Por fim inserimos 5: 5<7→3; 5>3→4; 5>4→6; 5<6→esquerda de 6. A árvore final após inserções é:
7
/
3 8
/
2 4
/
1 6
/
5

Passo 11

Para os percursos, usamos as definições:
  • Pré-ordem: nó, subárvore esquerda, subárvore direita
  • Em-ordem: subárvore esquerda, nó, subárvore direita
  • Pós-ordem: subárvore esquerda, subárvore direita, nó
    Aplicando isso à árvore final, temos:
    Pré-ordem: (7,3,2,1,4,6,5,8)
    Em-ordem: (1,2,3,4,5,6,7,8)
    Pós-ordem: (1,2,5,6,4,3,8,7)

Passo 12

Para remover em BST, se o nó tem dois filhos, substituímos pelo sucessor in-order (mínimo da subárvore à direita) e apagamos esse sucessor; se tem um filho só, substituímos pelo filho; se for folha, removemos direto. Removendo 7 (raiz com dois filhos), o sucessor é 8, que vira nova raiz, e apagamos o antigo nó 8.
Árvore após remover 7:
8
/
3
/
2 4
/
1 6
/
5
Em seguida removemos 6 (nó com um filho à esquerda), então substituímos 6 por 5.

Resposta

Árvore final após remoções:
8
/
3
/
2 4
/
1 5

Exercícios relacionados