11

Cette question explique à peu près qu'ils peuvent, mais ne montre aucun exemple de l'existence de deux arbres différents avec le même parcours de pré-ordre.

Il est également mentionné que la traversée dans l'ordre de deux arbres différents peut être la même bien qu'ils soient structurellement différents. Y en a-t-il un exemple?

trees binary-trees graph-traversal search-trees Sharan Duggirala
la source

2

Il s'agit d'un exercice très débutant. Qu'avez-vous essayé et où êtes-vous resté coincé?

Raphael

1

Même si vous avez la post-commande, en plus de la pré-commande, la traversée, vous pouvez toujours obtenir différents arbres. Pourquoi l'arborescence n'est-elle pas uniquement possible avec une traversée pré-commande et post-commande donnée? Vous pouvez trouver un exemple dans l'ordre dans De la représentation dans l'ordre à l'arborescence binaire . Également lié / dupliqué: quelles combinaisons de séquentialisation pré, post et dans l'ordre sont uniques?

Dukeling

28

Exemples d'arbres (image) :

     A:                 B:
     ‾‾                 ‾‾
     1                  1
    /                  / \
   2                  2   3
  /  
 3

Ceci est un exemple qui correspond à votre scénario, la valeur de la racine de l'arbre A est 1, ayant un enfant gauche avec la valeur 2, et son enfant gauche a également un enfant gauche avec la valeur 3.

La valeur de la racine de l'arbre B est 1, ayant un enfant gauche avec la valeur 2 et un enfant droit avec la valeur 3.

Dans les deux cas, la traversée de précommande est 1-> 2-> 3.

royashcenazi
la source

11

Il s'agit en fait d'un cas spécifique d'une règle générale selon laquelle pour tout arbre d'un certain ordre, il existe un arbre linéaire composé uniquement d'enfants gauche (ou uniquement droit) qui a le même ordre.

Dancrumb

5

@Dancrumb Ce qui à son tour est un cas spécifique d'une règle générale selon laquelle pour tout arbre avec N nœuds, et pour toute forme d'arbre (= arbre sans étiquette) avec N nœuds, il existe un moyen d'étiqueter ce dernier afin qu'il partage le parcours avec l'ancien. Cela vaut pour toute traversée (visite pré- / post- / dans l'ordre).

chi

8

$n$ $n$ $1,2,\dots,n$

Cela signifie que nous pouvons nommer les nœuds de n'importe quelle structure d'arbre binaire afin qu'il génère la même séquence de précommande que celle d'un autre arbre donné.

Cela ne fonctionnera pas si nous devons assumer d'autres propriétés de l'arbre. Par exemple, si l'arbre est supposé être un arbre de recherche binaire, avec toutes les clés différentes, sa séquence de précommande déterminera uniquement l'arbre.

Hendrik Jan
la source

8

Argument de comptage

$n$ $n^\text{th}$ $C_n=(2n)!/(n!(n+1)!).$

    o         o         o         o         o
   /         /         / \         \         \
  o         o         o   o         o         o      .
 /           \                     /           \
o             o                   o             o

$n!$

\frac{(2 n)!}{(n + 1)!} = 2 n \cdot (2 n - 1) \cdot \dots (n + 2) .

$\frac{(2n)!}{(n+1)!} = 2n\cdot(2n-1)\cdot \dots (n+2).$

$n!$ $n$ $n!$ $C_n>1$ $n>1.$ $n$

CR Drost
la source

1

En ce qui concerne votre deuxième question, oui, deux arbres structurellement différents peuvent avoir la même traversée dans l'ordre. Un tel exemple est:

     A:                 B:

     1                  2
    / \                  \
   2   3                  1
                           \
                            3

La traversée inverse des deux arbres est identique. 2 -> 1 -> 3

Navjot Singh
la source

La traversée en précommande de deux arbres différents peut-elle être la même, même si elles sont différentes?

Réponses:

Argument de comptage