Quais combinações de sequencialização pré, pós e ordem são únicas?

Sabemos pós-encomenda,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

e pré-encomenda

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

e passagem em ordem resp. sequencialização.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

Pode-se ver facilmente que nenhuma delas descreve uma dada árvore de maneira única, mesmo que assumamos chaves / rótulos distintos aos pares.

Quais combinações dos três podem ser usadas para esse fim e quais não podem?

As respostas positivas devem incluir um algoritmo (eficiente) para reconstruir a árvore e uma prova (idéia) de por que ela está correta. Respostas negativas devem fornecer exemplos contrários, ou seja, árvores diferentes que tenham a mesma representação.

Primeiro, vou assumir que todos os elementos são distintos. Nenhuma quantidade de sequencializações lhe dirá a forma de uma árvore com elementos [3,3,3,3,3]. É possível reconstruir algumas árvores com elementos duplicados, é claro; Não sei que condições suficientes existem.

Continuando com os resultados negativos, você não pode reconstruir completamente uma árvore binária apenas a partir de suas seqüências de pré e pós-ordem. [1,2]pré [2,1]- encomenda, a pós-encomenda deve ter 1na raiz, mas 2pode ser a criança esquerda ou a criança certa. Se você não se importa com essa ambiguidade, pode reconstruir a árvore com o seguinte algoritmo:

• Seja o percurso de pré-ordem e [ y n , … , y 1 ] seja o percurso de pós-ordem. Devemos ter x 1 = y 1 , e esta é a raiz da árvore.$[x_1,\dots,x_n]$$[y_n,\ldots,y_1]$$x_1=y_1$
• é o filho mais à esquerda da raiz e y 2 é o filho mais à direita. Se x 2 = y 2 , o nó raiz é unário; recursione sobre [ x 2 , … , x n ] e [ y n , … , y 2 ] para criar a única subárvore.$x_2$$y_2$$x_2 = y_2$$[x_2,\ldots,x_n]$$[y_n,\ldots,y_2]$
• Caso contrário, deixa e j são os índices de tal modo que x 2 = y i e y 2 = x j . [ x 2 , … , x j - 1 ] é a travessia de pré-ordem da subárvore esquerda, [ x j , … , x n ] a da subárvore direita e da mesma forma para as travessias de pós-ordem. A subárvore esquerda tem j - 2 = n - i $i$$j$$x_2 = y_i$$y_2 = x_j$$[x_2,\ldots,x_{j-1}]$$[x_j,\ldots,x_n]$ elementos e a subárvore direita possui i - 2 = n - j + 1 elementos. Recursar uma vez para cada subárvore. A propósito, esse método generaliza para árvores com ramificações arbitrárias. Com ramificações arbitrárias, descubra a extensão da subárvore esquerda e recorte seuselementos j - 2 de ambas as listas, depois repita para cortar a segunda subárvore da esquerda e assim por diante.$j-2=n-i+1$$i-2=n-j+1$
  $j-2$

Como afirmado, o tempo de execução é com Θ ( n 2 ) no pior caso (no caso de dois filhos, pesquisamos cada lista linearmente). Você pode transformar isso em O ( $O(n^2)$$\Theta(n^2)$ se você pré-processar as listas para criar um$O(n\,\mathrm{lg}(n))$ estrutura finita do mapa, dos valores dos elementos às posições nas listas de entrada. Também use uma matriz ou mapa finito para ir de índices a valores; atenha-se aos índices globais, para que as chamadas recursivas recebam todos os mapas e tomem um intervalo como argumento para saber em que agir.$n\,\mathrm{lg}(n)$

Com o percurso de pré-ordem e o percurso em ordem [ z 1 , … , z n ] , você pode reconstruir a árvore da seguinte maneira:$[x_1,\ldots,x_n]$$[z_1,\ldots,z_n]$

• A raiz é a cabeça da passagem de pré-ordem .$x_1$
• Seja o índice tal que z k = x 1 . Então [ z 1 , … , z k - 1 ] é a travessia em ordem do filho esquerdo e [ z k + 1 , … , z n ] é a travessia em ordem do filho certo. Indo pelo número de elementos, [ x 2 , … , x k ] é a travessia de pré-ordem do filho esquerdo e [ x $k$$z_k = x_1$$[z_1,\ldots,z_{k-1}]$$[z_{k+1},\ldots,z_n]$$[x_2,\ldots,x_k]$o da criança certa. Recomenda-se criar as subárvores esquerda e direita.$[x_{k+1},\ldots,x_n]$

Novamente, esse algoritmo é conforme declarado, e pode ser executado em O ( $O(n^2)$ se a lista for pré-processada em um mapa finito de valores a posições.$O(n\,\mathrm{lg}(n))$

A pós-ordem e a ordem são obviamente simétricas.