E21.1 Escreva uma função recursiva que receba uma árvore binária r e imprima o conteúdo dos seus nós em ordem r-e-d. (A ordem r-e-d também é conhecida como pré-ordem e como busca em profundidade.)
E21.2 Dada uma árvore binária, encontrar um nó da árvore cujo conteúdo tenha um certo valor val.
E21.3 Escreva uma função que imprima o conteúdo de cada nó de uma árvore binária com recuo de margem proporcional à profundidade do nó na árvore. Por exemplo, a árvore
555
/ \
333 888
/ \ \
111 444 999
deve se representada assim:
555
333
111
-
-
444
-
-
888
-
999
-
-
onde os caracteres '-' representam NULL.
E21.4
A varredura por níveis
ou busca em largura,
de uma árvore binária visita
todos os nós à profundidade 0,
depois todos os nós à profundidade 1,
depois todos os nós à profundidade 2,
e assim por diante.
(Lembrete: a profundidade
de um nó s em uma árvore binária com raiz r
é a distância entre s e r.)
Para cada profundidade,
os nós são visitados da esquerda para a direita
.
(Dica: Use uma fila de nós.)
E21.5 Em que condições uma árvore binária é um heap? Escreva uma função que transforme uma árvore binária quase completa em heap. Escreva uma função que transforme um heap em uma árvore binária (quase completa).
E21.6 A profundidade de um nó s em uma árvore binária com raiz r é a distância entre s e r. Mais precisamente, a profundidade de s é o comprimento do (único) caminho que vai de r até s. Por exemplo, a profundidade de r é 0 e a profundidade de r->esq é 1. Escreva uma função que determine a profundidade de um nó dado.
E21.7 Escreva uma função iterativa que receba uma árvore binária r e imprima o conteúdo dos seus nós em ordem r-e-d (ou seja, em pré-ordem). Dica: use uma pilha de nós.