Recursos em Árvore Binária

Recursos em ABB

Dada uma ABB, um problema pertinente pode ser construir rotinas para a realização de percursos na mesma. Isto pode ser feito por meio de funções recursivas, empregando abordagens especifícas.

Percurso em pré-ordem

1. Visita um nó, raiz da árvore ou da árvore;
2. Percorre o ramo esquerdo do nó, recursivamente;
3. Percorre o ramo direito do nó, recursivamente.

Void preOrdem(ABB *aux){

        Printf(“%d \t “, aux-> dado);

If(aux->esq!=NULL)

        PreOrdem(aux->esq);

If(aux->dir!=NULL)

        PreOrdem(aux->dir);

}

Percurso em pós-Ordem

1. Percorre o ramo esquerdo do nó, recursivamente;
2. Percorre o ramo direito do nó, recursivamente;
3. Visita um nó, raiz da árvore ou da subárvore

Void posOrdem(ABB *aux){

        If(aux->esq!=NULL)

                posOrdem(aux->esq);

        If(aux->dir!=NULL)

                PosOrdem(aux->dir);

Printf(“%d \t “\ aux->dado);

}

Percurso em ordem simétrica (em ordem)

1. Percorre o ramo esquerdo do nó, recursivamente;
2. Visita um nó, raiz da árvore ou da subárvore;
3. Percorre o ramo direito do nó, recursivamente.

Void emOrdem(ABB * aux){

        If(aux->esq!=NULL)

                EmOrdem(aux->esq);

        

        Printf(“%d \t “, aux->dado);

If(aux->dir!=NULL)

        EmOrdem(aux->dir);

}

Para os exemplos de funções escritas aqui, foi considerado o tipo construído ABB;

Typedef struct temp {

        Int dado;

Struct temp *esq;

Struct temp *dir;

}ABB;

A chamada externa pode enviar qualquer nó da árvore binária de busca:

preOrdem(raiz); //percorre a ABB em pré-ordem

posOrdem(raiz->esq); //percorre a subárvore esquerda da raiz

//em pós-ordem

Atividade:

Indique como ficaria o percurso da ABB a1 nos 3 modos indicados:

...