Tipos e Estruturas de Dados

Exercícios sobre Árvores

1) Escreva uma função nao recursiva para imprimir uma árvore binaria
em Inordem. Dica: utilize uma pilha. Assuma que nao há mais do 
que 100 elementos em sua arvore

2)Escreva uma função que calcule o número de células de uma árvore binária.

3) Escreva uma função que calcule a aultura de uma árvore binária. 

4) Escreva uma função que conte o nro de nós folhas em uma
árvore (nós com sub-arvores esquerda e direta, vazias)

5) Escreva uma função que troque as subarvores esquerdas pelas direitas,
de uma árvore binária, ou seja, os nós que estão à direita passa para
a esquerda, gerando uma árvore "espelho" da árvore original.

6)Escreva a função void LimpaArvore(No *no) que percorre uma árvore
binária e elimina (dispose) todos os nós.

7)Seja uma árvore binária de busca. Mostre como seria a implementação do método de 
ordenação TreeSort, usando os mecanismos de percorrer árvore e inserção em árvore
binária de busca.

8) IMplemente uma versão nao recursiva da função para busca em uma 
árvode binária de busca.

9) Suponha que as chaves 50, 30, 70, 20, 40, 60, 80, 15, 25, 35, 45, 36 são inseridas, 
nesta ordem, numa árvore de busca que está inicialmente vazia. Desenhe a árvore que resulta. 
Em seguida remova a célula que contém 30.


10)Árvore de expressão aritmética 
Suponha uma expressão aritmética cujos operadores são todos binários. 
Mais concretamente, suponha que os operadores são soma (+) e multiplicação (*). 
Suponha também, para simplificar, que os operandos são nomes de variáveis, cada 
um consistindo de uma única letra. Uma expressão aritmética pode ser muito bem 
representada por uma árvore binária: as folhas da árvore são operandos e os 
nós internos são operadores.

                      *
                    /   \
                   +     f
                 /   \
                a     *
                    /   \
                   *     +
                  / \   / \
                 b   c d   e


Se a árvore for lida em inordem, teremos a expressão em notação 
infixa. Se for lida em ordem posordem, teremos a expressão em notação 
posfixa. Se for lida em ordem preordem, teremos a expressão em 
notação prefixa.

    infixa   	(a+(b*c)*(d+e))*f
    posfixa   	abc*de+*+f*
    prefixa   	*+a**bc+def

Suponha que a expressão prefixa está armazenada em um vetor global de 
caracteres  a[i..] ,  sendo i uma variável global. A função abaixo,
supostamente lê o vetor [a] e cria uma árvore de expressão aritmética.
Essa função funciona?  Sim/Nao e explique

link parse() {
    char t;
    link x;

    t = a[i++];
    x = malloc(sizeof *x); 
    x->token = t;
    if (t == '+' || t == '*') {
        x->l = parse();
        x->r = parse();
    }
    else x->l = x->r = NULL;
    return x;
}