reconstruindo uma tree a partir de suas listas de pré-encomenda e pós-encomenda

Considere a situação em que você tem duas listas de nós, das quais tudo o que você sabe é que uma é uma representação de uma passagem de pré-ordem de uma tree e a outra é uma representação de uma passagem de pós-ordem da mesma tree.

Eu acredito que é possível reconstruir a tree exatamente a partir dessas duas listas, e eu acho que tenho um algoritmo para fazer isso, mas não provei isso. Como isso será parte de um projeto de mestrado, eu preciso estar absolutamente certo de que é possível e correto (matematicamente comprovado). No entanto, não será o foco do projeto, então eu queria saber se há uma fonte lá fora (ou seja, papel ou livro) que eu poderia citar para a prova. (Talvez no TAOCP? Alguém conhece a seção possivelmente?)

Em suma, preciso de um algoritmo comprovado em um recurso citável que reconstrua uma tree a partir de suas travessias pré e pós-ordem.


Nota: A tree em questão provavelmente não será binária ou balanceada, ou qualquer coisa que torne isso muito fácil.

Nota 2: Utilizar apenas a encomenda ou a lista de encomendas seria ainda melhor, mas não creio que seja possível.

Nota3: Um nó pode ter qualquer quantidade de filhos.

Nota 4: Eu só me importo com a ordem dos irmãos. Esquerda ou direita não importa quando há apenas um filho.

Você não pode usar apenas uma lista, porque não terá noção da profundidade da tree. Assim, você definitivamente precisa de duas ou mais listas.

Aqui está minha tentativa de solução:

Use sua passagem de pré-encomenda como um meio de saber a ordem dos dados. Isto faz sentido porque você sabe que o primeiro nó é o topo, e você sabe que os dados mais à esquerda do percurso pertencem à esquerda da tree, etc.

Sua travessia de ordem de postagem pode determinar a profundidade da tree. Por exemplo, digamos que eu tenha uma estrutura como esta:

  1 2 5 6 3 4 7 Where 2 is the parent of 3 and 4, and 5 is the parent of 7. Preorder: 1 2 3 4 5 7 6 Postorder: 3 4 2 7 5 6 1 

Sabemos que começamos com 1, porque é o primeiro nó na travessia da pré-ordem. Então olhamos para o próximo número, 2. Na ordem de post, porque o número 2 vem ANTES do nó 1, sabemos que 2 tem que ser filho de 1. Em seguida, olhamos para 3. 3 vem antes de 2 e, portanto, 3 é uma criança de 2. 4 é antes de 2, mas depois de 3, por isso sabemos que 4 é uma criança de 2, mas não uma criança de 3. Etc.

Agora, isso pode não funcionar se os nós não forem exclusivos, mas, no mínimo, será um começo para uma solução.

Edit: A ordem dos filhos é preservada com esta solução, simplesmente devido ao conhecimento da ordenação dos nós através da travessia da pré-encomenda e, em seguida, conhecer a estrutura através do percurso da encomenda.

Edit2: A prova pode estar aqui: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel2%2F215%2F626%2F00017225.pdf%3Farnumber% 3D17225 & authDecision = -203

Eu acho que você precisa comprar o documento, no entanto …

Aqui está uma prova escrita apresentada para ser uma solução:

http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa-cse/tutorials/tutorial09-solutions.pdf

Preorder e postorder não definem exclusivamente uma tree.

Em geral, uma única tree percorrida não define exclusivamente a estrutura da tree. Por exemplo, como já vimos, para ambas as trees a seguir, uma passagem in-loco produz [1,2,3,4,5,6].

  4 3 / \ / \ 2 5 2 5 / \ \ / / \ 1 3 6 1 4 6 

A mesma ambigüidade está presente para travessias de pré-encomenda e pós-encomenda. A travessia da pré-ordem para a primeira tree acima é [4,2,1,3,5,6]. Aqui está uma tree diferente com o mesmo percurso de pré-ordem.

  4 / \ 2 1 / \ 3 6 \ 5 

Da mesma forma, podemos facilmente construir outra tree cuja trajetória de pós-ordem [1,3,2,6,5,4] coincida com a da primeira tree acima.

Considere uma tree arbitrária T como quadruplicar (A, B, C , D ), onde A é o nó raiz, B é o nó raiz do primeiro filho, C é um vetor de qualquer filho não vazio de B e D é um vetor de quaisquer irmãos não-vazios de B. Os elementos de C e D são eles próprios trees.

Qualquer um de A, B, C e D pode estar vazio. Se B estiver vazio, deve ser C e D ; se A, então tudo.

Como os nós são exclusivos, os conjuntos de nós contidos em qualquer lugar dentro de C e D são separados e nenhum contém A ou B.

As funções pre () e post () geram sequências ordenadas do formulário:

pre (T) = [A, B, pré ( C ) , pré ( D ) ]

post (T) = [ post ( C ) , B, postagem ( D ) , A]

onde a function aplicada a um vetor é definida como a concatenação das seqüências resultantes da aplicação da function a cada elemento, por sua vez.

Agora considere os casos:

  • se A estiver vazio, a saída de ambas as funções é a sequência vazia []
  • se B estiver vazio, a saída de ambas as funções é apenas [A]
  • se C e D estiverem vazios, pre (T) = [A, B] e pós (T) = [B, A]
  • se apenas C estiver vazio, pre (T) = [A, B, D ‘ ] e pós (T) = [B, D’ ‘ , A] (onde os primos indicam alguma permutação dos nós contidos em D )
  • se apenas D estiver vazio, pre (T) = [A, B, C ‘ ] e pós (T) = [ C’ ‘ , B, A]
  • se nenhum estiver vazio, pre (T) = [A, B, C ‘ , D’ ] e pós (T) = [ C ” , B, D ” , A]

Em todos os casos, podemos particionar de forma não ambígua os membros das duas seqüências de saída nas subseqüências apropriadas, usando A e B (se presentes) como delimitadores.

A questão então é: podemos também particionar as sequências do vetor? Se pudermos, cada um pode ser processado recursivamente e pronto.

Como o resultado de pre () sempre será uma cadeia de seqüências começando com A, e o resultado de post () sempre será uma cadeia de seqüências terminando com A, nós podemos de fato dividi-los, desde que os nós A nunca estão vazios.

É aqui que o processo cai no caso de trees binárias (ou de fato qualquer) com filhos fixos que podem estar vazios independentemente. No nosso caso, no entanto, definimos C e D para conter apenas nós não vazios, e assim a reconstrução é garantida para funcionar.

Acho que sim. Obviamente, isso é apenas um argumento, não uma prova formal!

Crie uma tree binária com esta restrição que tenha pelo menos um nó que este nó tenha apenas um filho (direita ou esquerda, não há diferença).

Agora, escreva suas listas de pré-encomenda e pós-encomenda. tente reconstruir a tree dessas listas. e você percebe que nesse nó você não pode decidir que seu filho está certo ou esquerdo.

Como já foi apontado por outros, uma tree binária não pode ser reconstruída usando apenas o percurso pré e pós-ordem. Um único nó filho tem percursos ambíguos que não podem identificar se é filho da esquerda ou da direita, por exemplo, considerar os seguintes percursos de pré-encomenda e pós-encomenda: preorder: a, b postorder b, a

Pode produzir ambas as seguintes trees

aa \ / bb Simplesmente não é possível saber se b é um filho da esquerda ou da direita sem qualquer informação adicional, como inorder traversal.

As travessias de pré-ordem e pós-ordem são suficientes para reconstruir a tree, assumindo que os nós são nomeados exclusivamente. A chave para criar os algoritmos é entender que

X é um ancestral de Y se X precede Y na pré-encomenda e está atrás de Y no pós-ordenado.

Perante isto, podemos sempre encontrar todos os descendentes de qualquer nó. Os descendentes de X sempre seguem imediatamente X na pré-ordem e precedem X no pós-pedido. Então, uma vez que sabemos que estamos interessados ​​em produzir a subtree enraizada em X, podemos extrair o percurso pré-ordem e pós-ordem para a subtree enraizada em X. Isso leva naturalmente a um algoritmo recursivo, uma vez que percebemos que o nó imediatamente após X deve ser seu filho mais à esquerda, se é um descendente de todo.

Há também uma implementação baseada em pilha, que percorre os nós de pré-encomenda e mantém na pilha quaisquer nós que sejam candidatos a pai direto do próximo nó de pré-encomenda. Para cada nó de pedido antecipado, retire repetidamente todos os nós da pilha que não são pais do próximo nó de encomenda antecipada. Torne esse nó um filho do nó superior na pilha e empurre o filho para a pilha.

Não é possível construir uma Árvore Binária geral a partir de travessias de pré-ordem e pós-encomenda (Veja isto). Mas se soubermos que a Árvore Binária está Cheia, podemos construir a tree sem ambigüidade. Vamos entender isso com a ajuda do seguinte exemplo.

Vamos considerar as duas matrizes dadas como pré [] = {1, 2, 4, 8, 9, 5, 3, 6, 7} e postar [] = {8, 9, 4, 5, 2, 6, 7 3, 1}; Em pre [], o elemento mais à esquerda é raiz da tree. Como a tree está cheia e o tamanho da matriz é maior que 1. O valor próximo a 1 em pre [] deve ser deixado como filho da raiz. Então sabemos que 1 é raiz e 2 é filho de esquerda. Como encontrar todos os nós na subtree esquerda? Sabemos que 2 é a raiz de todos os nós na subtree esquerda. Todos os nós anteriores a 2 em post [] devem estar na subtree esquerda. Agora sabemos que 1 é raiz, elementos {8, 9, 4, 5, 2} estão na subtree esquerda e os elementos {6, 7, 3} estão na subtree direita.

  1 / \ / \ {8, 9, 4, 5, 2} {6, 7, 3} 

Nós seguimos recursivamente a abordagem acima e obtemos a seguinte tree.

  1 / \ 2 3 / \ / \ 

4 5 6 7 / \
8 9