lista_arvore_Revisão

Prévia do material em texto

Lista de Exercícios de Estruturas de Dados II
Revisão de Árvores Binárias e Árvores Binárias de Busca
1ª Questão: Considere uma árvore binária de busca cujos nós armazenam números inteiros. Construa os procedimentos e funções abaixo:
Um procedimento não recursivo para inserir um novo nó e que utilize apenas um ponteiro auxiliar.
Um procedimento não recursivo para remover um nó.
Uma função recursiva para contar o número de nós.
Uma função não recursiva para contar o número de nós.
Uma função recursiva para contar o número de folhas.
Uma função não recursiva para contar o número de folhas.
Uma função recursiva para contar o número de nós não-terminais.
Uma função não recursiva para contar o número de nós não-terminais.
Um procedimento recursivo para remover todos os nós.
Um procedimento não recursivo para remover todos os nós.
Uma função recursiva para retornar o endereço do nó que contém o menor valor.
Uma função não recursiva para retornar o endereço do nó que contém o menor valor.
Uma função recursiva para retornar o endereço do nó que contém o maior valor.
Uma função não recursiva para retornar o endereço do nó que contém o maior valor.
Um procedimento não recursivo para percorrer a árvore utilizando o passeio em-ordem.
Um procedimento não recursivo para percorrer a árvore utilizando o passeio em pré-ordem.
Um procedimento não recursivo para percorrer a árvore utilizando o passeio em pós-ordem.
2ª Questão: Dadas duas árvores binárias A e B, diz-se que A eq B (lê-se A é equivalente a B), se:
ambas são vazias, ou
info (raiz(A)) = info (raiz(B)) e esq(A) eq esq(b) e dir(A) eq dir(B)
Construa o sub-programa equivalente (A,B) para determinar se as árvores apontadas por A e B são ou não equivalentes.
3ª Questão: Dada uma árvore binária qualquer, faça um procedimento para criar uma cópia idêntica da mesma, ou seja, criar uma árvore equivalente à árvore dada.
4ª Questão: Dada uma árvore binária qualquer, faça um sub-programa para determinar se a mesma é ou não uma árvore binária completa.