O que significa caminhada pré, pós e em ordem para uma árvore n-ária?
8
Os métodos de passagem em árvore explicados neste artigo da Wikipedia são pré-encomenda, pós-encomenda e em ordem. Esses métodos são limitados a árvores binárias? O algoritmo parece ser definido em termos de filho esquerdo e direito. Se pode ser usado para árvores n-árias, como?
Uma árvore n-ária possui 1 pai e n filhos em qualquer nó. Onde n pode ser qualquer número inteiro para cada nó.
Por favor, use a figura abaixo para explicar isso, se você precisar de um.
Não, não se limita a árvores binárias. Sim, pré-encomenda e pós-encomenda podem ser usadas paranárias árvores. Você simplesmente substitui as etapas "Atravessar a subárvore esquerda .... Atravessar a subárvore direita ...." no artigo da Wikipedia por "Para cada filho: percorra a subárvore enraizada nesse filho chamando recursivamente a função de deslocamento". Assumimos que o loop for iterará pelos filhos na ordem em que são encontrados na estrutura de dados: normalmente, na ordem da esquerda para a direita, para um diagrama como o mostrado.
De fato, isso já está descrito no artigo da Wikipedia sobre travessias de árvores: consulte https://en.wikipedia.org/wiki/Tree_traversal#Generic_tree , que descreve exatamente como generalizar isso paranárias árvores. O percurso de pré-encomenda é aquele em que a operação de pré-encomenda é "Exibir o nó atual" e a operação de pré-pedido é "Não faça nada". O percurso pós-pedido é aquele em que a operação de pré-pedido é "Não fazer nada" e a operação de pós-pedido é "Exibir o nó atual".
A travessia em ordem é um caso especial. Provavelmente só faz sentido para árvores binárias. Embora existam várias maneiras possíveis de definir um percurso em ordem paranarvores, cada uma delas parece um pouco estranha e antinatural e provavelmente não é muito útil na prática. Portanto, provavelmente é melhor pensar na travessia em ordem como sendo específica para árvores binárias; se você quiser fazer algo semelhante em ordem de travessia por umnNa árvore principal, você precisará decidir exatamente o que você quer dizer com isso, pois não há um significado padrão para isso.
Também vale a pena notar que o único tipo de travessia que não funciona para n-Árvores não estão em ordem; não existe um equivalente significativo de passagem na ordem para um nó com um número ímpar de filhos.
Adam R. Nelson
@DW E quanto a in-oder? Você poderia incluir isso na sua resposta também?
Renae Lider
@ AdamR.Nelson Como funciona para um número par que não seja dois? Para binário, é Esquerda-Raiz-Direita. Não sei como isso funcionará para, digamos, um quadtree.
precisa
@RenaeLider Dados os filhos A, B, C e D (da esquerda para a direita), você pode fazer algo parecido com a travessia de um quadtree ao atravessar o AB-Root-CD. Mas não acho que exista alguma aplicação útil disso.
Adam R. Nelson
2
@ AdamR.Nelson Você pode definir em ordem para o caso geral, dizendo que visita os pais após o primeiro filho e depois os outros filhos. Talvez não seja muito significativo, mas possível.
Raphael
0
Existem muitas estruturas de dados exóticas usadas em todo o CS com muitas variantes. Houve uma pergunta recente semelhante (agora excluída) sobre atravessar árvores n-árias de maneira ordenada overexchange. Parece que a maioria ou muitas árvores n-árias na literatura estudada tendem a não ser encomendadas. No entanto, como um caso alternativo de pov / excepcional / "borda" na outra resposta detalhada, existem casos de árvores n-árias ordenadas que não são "estranhas e não naturais e provavelmente não são muito úteis na prática". Aqui está uma referência; provavelmente existem muitos outros casos, embora seja possível que eles não sejam amplamente utilizados.
ps outra maneira de pensar em árvores n-árias ordenadas é simplesmente que as arestas são rotuladas e têm ordenamentos acessíveis ao algoritmo no percurso.
vzn
Não estou claro sobre o procedimento de inserção / atualização da árvore ordenada. Você pode compartilhar o código?
Existem muitas estruturas de dados exóticas usadas em todo o CS com muitas variantes. Houve uma pergunta recente semelhante (agora excluída) sobre atravessar árvores n-árias de maneira ordenada
overexchange. Parece que a maioria ou muitas árvores n-árias na literatura estudada tendem a não ser encomendadas. No entanto, como um caso alternativo de pov / excepcional / "borda" na outra resposta detalhada, existem casos de árvores n-árias ordenadas que não são "estranhas e não naturais e provavelmente não são muito úteis na prática". Aqui está uma referência; provavelmente existem muitos outros casos, embora seja possível que eles não sejam amplamente utilizados.[1] árvores encomendadas por n / árias / notas do curso P Mateti 7140
fonte