Questoes Binario

1 Arvores binarias

Nas quest~oes abaixo, considere a seguinte estrutura de dados usada para representar

arvores binarias (n~ao balanceadas):

struct btree{

int info;

struct btree *sad;

struct btree *sae;

};

typedef struct btree BTree;

1. Implemente uma func~ao que determine a altura de uma arvore binaria.

Essa func~ao deve obedecer o prototipo:

int btree_height(BTree *t);

2. Implemente uma func~ao que conte o numero de nos do tipo folha. Essa

func~ao deve obedecer o prototipo:

int btree_numleaves(BTree *t);

3. Implemente uma func~ao que determine se uma arvore binaria e de busca.

Essa func~ao deve obedecer o prototipo:

int btree_issearchtree(BTree *t);

4. Implemente uma func~ao que determine se uma arvore binaria segue as

restric~oes de uma arvore AVL. Essa func~ao deve obedecer o prototipo:

int btree_isavltree(BTree *t);

Na quest~ao abaixo, considere a seguinte estrutura de dados usada para representar

arvores AVL:

struct avltree{

int info;

struct btree *sad;

struct btree *sae;

int height;

};

typedef struct avltree AVLTree;

5. Implemente uma func~ao que insira um novo elemento em uma arvore AVL.

Essa func~ao deve obedecer o prototipo:

int avltree_insert(AVLTree *t, int elem);

Dica: reuse o codigo apresentado em aula para inserc~ao em arvores binarias

de busca n~ao balanceadas, e considere a implementac~ao de func~oes auxiliares

que tratam separadamente os 4 casos de rotac~ao para ns de rebalanceamento

da arvore AVL.

2 Arvores Trie e Patricia

Considere o seguinte trecho do poema \Quadrilha" de Carlos Drummond de

Andrade:

\Jo~ao amava Teresa que amava Raimundo que amava Maria que

amava Joaquim que amava Lili que n~ao amava ninguem"

1. Construa no papel uma arvore Patricia para indexar o texto acima. Considere

a seguinte codicac~ao para as palavras de texto:

Jo~ao 01001011 Maria 01100101

amava 00011101 Joaquim 00101110

Teresa 11101011 Lili 01010011

que 10100101 n~ao 10011100

Raimundo 11011010 ninguem 10110010

Com base na arvore Patricia construda acima, faca uma pesquisa pelas

chaves \amava" e \Lili". Mostre a caminho percorrido para cada pesquisa

e as ocorr^encias do termo pesquisado.

2

3 Tabelas hash

Nas quest~oes abaixo, considere um cadastro de alunos armazenado em