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
(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
7
Passo 4
Agora inserimos 8. Como 8>7, vai para a direita de 7. A árvore fica:
7
8
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
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
7
/
3 8
4
Passo 7
Ao inserir 2: 2<7 (vai a 3), 2<3 (vai à esquerda). Fica:
7
/
3 8
/
2 4
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
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
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
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:
Em-ordem:
Pós-ordem:
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.
Á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
8
/
3
/
2 4
/
1 5