C Estrutura de Dados - Arvore binaria

[David Banky]

Bom dia, estou fazendo um exercicio de estrutura de dados, mas tudo parece bem confuso, será que alguem conseguiria me auxiliar, resolvendo e explicando por favor.

 

Problema:

Considere uma árvore binária cujos nós têm um campo chave de um tipo linearmente ordenado, um tipo (como int, char, string, etc.) que admite comparação.

Uma árvore binária deste tipo é de busca se cada nó p tem a seguinte propriedade:  a chave de p é (1) maior ou igual à chave de qualquer nó na subárvore esquerda de p  e (2) menor ou igual à chave de qualquer nó na subárvore direita de p.  

Em outras palavras, se p é um nó qualquer então:

e->chave   ≤   p->chave   ≤   d->chave

O que deve ser realizado na questão:

Considerando-se uma árvore ordenada, ou árvore binária de busca, sem balanceamento, faça:

a) A partir de uma árvore vazia, insira os seguintes nós na árvore, na ordem apresentada:

8, 5, 15, 12, 3, 18, 4, 7

Mostre a árvore resultante a cada passo.

b) Qual é o caminho do nó 4?

c) Remova o nó de valor 15. Como ficará a árvore resultante? Explique sua resposta.

Mostre a árvore resultante.

d) Insira mais 5 números (a escolha é sua) na árvore resultante do item C.

Mostre a árvore resultante.

e) Faça outra árvore, inserindo apenas os seguintes nós:

            15, 12, 9, 6, 3

Que tipo de árvore é essa?

Com qual outro tipo de estrutura de dados ela pode ser comparada?

Mostre a árvore resultante.