A estrutura de uma "árvore binária completa", ser identificada exclusivamente se apenas suas travessias pré-encomendas ou pós-ordem ou encomendas forem dadas?

Question

Eu não consigo reaproçar se pudermos construir uma árvore binária completa se apenas um dos seguintes 3 travessuras for dado: pré-encomenda, pós-ordem, em ordem.

A seguir, a definição de uma árvore binária completa:

.

Uma árvore binária completa é uma árvore binária em que todo nível, exceto possivelmente o último, é completamente preenchido, e todos os nós são tão longe quanto possível.

A definição acima foi tirada desse link: https.pdx.edu/~Sheard / Curso / CS163 / DOC / FullVsComplete.html

seria útil se alguém puder provar ou explicar intuitivamente por que podemos ou não podemos construir exclusivamente uma árvore binária completa se apenas um dos seus 3 travessuras for dada?

Answer 1

dado $ n $ , Há apenas uma forma para uma árvore binária completa (CBT) com $ n $ nós.

Para qualquer travessia determinista, a correspondência entre a posição de um nó em um CBT e sua posição durante a travessia dessa CBT é completamente fixa. Então, se uma travessia determinista é dada, podemos reconstruir o CBT exclusivamente. Isso se aplica não apenas a qualquer uma das travessias pré-encomenda, pós-ordem ou encomenda, também se aplica à respiração-primeira travessia (com a criança esquerda visitada antes da criança certa), ou qualquer outra travessia determinística como mencionado por hendrik jan em seu comentário .

Aqui está um exemplo. A forma acima é a única forma para um CBT com 12 nós, que são, 1 raiz (em profundidade 0), 2 nós a profundidade 1, 4 nós em profundidade 2 e 5 nós em profundidade 3. Uma travessia pré-encomenda daquele CBT visita os nós na seguinte ordem.

.
1. o nó raiz.
2. o primeiro nó da profundidade 1.
3. o primeiro nó da profundidade 2.
4. o primeiro nó da profundidade 3.
5. o segundo nó da profundidade 3.
6. o segundo nó da profundidade 2.
7. o terceiro nó da profundidade 3.
8. o quarto nó da profundidade 3.
9. o segundo nó da profundidade 1.
10. o terceiro nó da profundidade 2.
11. o quinto nó da profundidade 3.
12. o quarto nó da profundidade 2.

Dê a lista acima, sabemos que o nó raiz é o 1 ^{st -node visitado, o primeiro nó da profundidade 1 é o 2 nd -node visitado. .., o quarto nó da profundidade 3 é o 8 -no -node visitado e o quinto nó da profundidade 3 é o 11 th -node visitado.}