La structure d'un "arbre binaire complet" peut-elle être identifiée de manière unique si seuls ses travers de pré-commande ou de post-commande ou en ordre sont donnés?

Question

Je suis incapable de raisonner si nous pouvons construire un arborescence binaire complet si seulement l'un des 3 travers suivants est donné: Pré-commande, post-commande, en ordre.

Ce qui suit est la définition d'un arborescence binaire complet:

Un arbre binaire complet est un arbre binaire dans lequel chaque niveau, à l'exception peut-être le dernier, est complètement rempli, et tous les nœuds sont aussi loin que possible.

La définition ci-dessus a été prise à partir de ce lien: https://web.cecs.pdx.edu/~COUARD / COURS / CS163 / DOC / FULLVSCOMPLETE.HTML

Il serait utile que quelqu'un puisse prouver ou expliquer intuitivement pourquoi nous pouvons ou ne pouvons pas construire de manière unique un arbre binaire complet si seulement l'un de ses 3 traversers est donné?

Answer 1

donné $ N $ , il n'y a qu'une seule forme pour un arbre binaire complet (CBT) avec $ n $ nœuds.

Pour tout travertial déterministe, la correspondance entre la position d'un nœud dans une CBT et sa position pendant la traversée de cette TCC est complètement fixée. Donc, si une traversée déterministe est donnée, nous pouvons reconstruire le CBT uniquement. Ceci s'applique non seulement à l'une des tranchères de pré-commande, d'après l'ordre ou de commande, il s'applique également à la main-d'œuvre à couper le souffle (avec l'enfant gauche visité devant le bon enfant), ou tout autre traversé déterministe mentionné. par Hendrik Jan à son commentaire .

Voici un exemple. La forme ci-dessus est la seule forme pour un CBT avec 12 nœuds, qui sont 1 racine (à la profondeur 0), 2 nœuds à la profondeur 1, 4 nœuds à la profondeur 2 et 5 nœuds à la profondeur 3. une traversée de pré-commande de cette CBT visit les nœuds dans l'ordre suivant.

1. le nœud racine.
2. le premier noeud de la profondeur 1.
3. le premier noeud de la profondeur 2.
4. le premier nœud de la profondeur 3.
5. le deuxième noeud de profondeur 3.
6. le deuxième noeud de la profondeur 2.
7. Le troisième noeud de profondeur 3.
8. le quatrième noeud de profondeur 3.
9. le deuxième noeud de profondeur 1.
10. le troisième noeud de profondeur 2.
11. le cinquième noeud de la profondeur 3.
12. le quatrième noeud de profondeur 2.

Donnez la liste ci-dessus, nous savons que le nœud racine est le 1 ^{st -Node visité, le premier nœud de la profondeur 1 est le 2 nd -Node visité ,. .., le quatrième noeud de la profondeur 3 est le 8 TH -Node visité et le cinquième noeud de la profondeur 3 est le 11 TH -Node visité.}