Percurso em árvore e problemas do URI (1191/1194)

Dado uma árvore binária (cada nó tem 0, 1 ou 2 filhos), existem duas formas prioritárias de percorrer os nós, que são em largura (BFS) ou em profundidade (DFS). (Não vamos falar disto aqui, mas são assuntos necessários para entender).

Na busca em profundidade, é possível estabelecer uma ordem de prioridade para as visitas:

• Pré-ordem: Primeiro visita o próprio nó, depois a sub-árvore esquerda e em seguida a direita.
• In-ordem: Primeiro visita a sub-árvore esquerda, depois o próprio nó e por último a direita.
• Pós-ordem: Primeiro visita a sub-árvore esquerda, depois a direita e por último o próprio nó.

Por visitar, entenda uma operação qualquer (pode ser printar, inserir em uma pilha etc). Como exemplo, veja a imagem abaixo.

É claro que só com a ordem de visita pré, in ou pós-ordem não é possível distinguir uma árvore única com mais de um nó. Por exemplo, as duas árvores abaixo possuem a mesma saída após visitar em in-ordem (1, 2, 3).

Visita em In-ordem: 1, 2, 3

Porém, dado a lista com a ordem das visitas, é interessante ver como se estruturam:

Para cada sub-árvore, a raiz é o primeiro elemento do subvetor em pré-ordem, um elemento do meio (que divide o vetor em filhos direitos e esquerdos) em in-ordem, e o último elemento do subvetor em pós-ordem.

Reciusivamente, podemos definir a mesma lógica para o sub-vetor da sub-árvore direita ou esquerda:

Então com o vetor da sub-árvore de visitas in-ordem e em pós (ou pré-ordem), podemos definir raiz, sub-árvore direita (que está à direita da raiz em in-ordem) e sub-árvore esquerda (que está à esquerda da raiz em in-ordem) (basta buscar onde está a raiz).

Definimos então o problema de reconstruir a árvore recursivamente dadas as ordens de visitas in-ordem e pós-ordem (ou pré-ordem, mas o modelo aqui é para pós). Assumimos aqui que todos os elementos da árvore são únicos.

A solução abaixo utiliza ponteiros porque acredito ficar mais fácil de entender, mas é possível fazer sem ponteiros (do it!).

#include <stdio.h>
#define MAXN 1000

int in_ordem[5] = {4, 2, 5, 1, 3};
int pre_ordem[5] = {1, 2, 4, 5, 3};
int pos_ordem[5] = {4, 5, 2, 3, 1};

struct node {
   int val;
   node *esq, *dir;
};

node data[MAXN];
int data_cnt;

node *new_node() {
   data[data_cnt].esq = data[data_cnt].dir = NULL;
   return &data[data_cnt++];
}

node *mount(int in_ini, int in_fim, int pos_fim) {
   //Se o sub-vetor nao eh valido (ou seja, ini > fim)
   //Ou a posicao em pos_ordem nao for valida retorna NULO
   if (in_ini > in_fim || pos_fim < 0) return NULL;

   //Queremos achar no vetor in_ordem o ultimo valor
   //do vetor pos_ordem
   //Assumimos que o vetor in_ordem se refere a uma sub-arvore
   //Que comeca em in_ini e termina em in_fim

   int position = 0;
   for(position = in_ini; position <= in_fim; position++) {
      //Se achamos o elemento que eh a raiz da sub-arvore
      //no vetor in-ordem
      if(in_ordem[position] == pos_ordem[pos_fim]) {
         node *raiz = new_node(); //Criamos um no

         raiz->val = in_ordem[position];
         //Printando em pre-ordem
         printf("%d\n", raiz->val);
         //Resolvemos pras sub-arvores esq e dir
         raiz->esq =
            mount(in_ini, position-1, pos_fim-(in_fim-position)-1);
         raiz->dir = mount(position+1, in_fim, pos_fim-1);
         
         return raiz;
      }
   }
   return NULL; //Se os vetores estiverem OK, sem elementos repetidos
                //Esse return soh serve pra completar a funcao

int main() {
   mount(0, 4, 4);
}

Se você já conhece o QuickSort, vai ver que este algoritmo é muito parecido com o de ordenação, e tem tempo de execução similar (O(nlogn) no caso médio e O(n²) no pior caso).

Dois problemas no URI são muito parecidos com este que enunciado aqui:
https://www.urionlinejudge.com.br/judge/pt/problems/view/1191
https://www.urionlinejudge.com.br/judge/pt/problems/view/1194

OBS: Não é necessário reconstruir a árvore nestes problemas, mas a lógica é parecida!

Até mais!