Parcours d'arbre en ordre : Quelle définition est correcte ?

Question

J'ai le texte suivant d'un cours académique que j'ai suivi il y a quelque temps sur traversal in-order (ils l'appellent aussi pancakine) d'un arbre binaire (pas un BST) :

Parcours d'arbre inordre

Dessinez une ligne autour de l'extérieur de l'arbre. Commencez à gauche de la racine, et suivez le contour de l'arbre, pour vous retrouver à droite de la racine. Restez aussi proche de l'arbre que possible, mais ne le traversez pas. (Pensez à l'arbre - ses branches et nœuds - comme une barrière solide). L'ordre des nœuds est l'ordre dans lequel cette ligne passe en dessous d'eux. Si vous n'êtes pas sûr de quand vous passez "en dessous" d'un nœud, souvenez-vous qu'un nœud "à gauche" vient toujours en premier.

Voici l'exemple utilisé (un arbre légèrement différent de ci-dessous)

Cependant, lorsque je recherche sur google, je trouve une définition en conflit. Par exemple, l'exemple de wikipedia :

Séquence de parcours inordre : A, B, C, D, E, F, G, H, I (nœud gauche, nœud racine, nœud droit)

Mais selon (ma compréhension de) la définition #1, cela devrait être

A, B, D, C, E, F, G, I, H

Quelqu'un peut-il clarifier quelle définition est correcte? Ils pourraient décrire des méthodes de parcours différentes, mais utiliser le même nom par hasard. J'ai du mal à croire que le texte académique examiné par des pairs soit incorrect, mais je ne peux pas en être certain.

Answer 1

Dans ma mauvaise tentative de dessin, voici l'ordre qui montre comment ils devraient être sélectionnés.

choisissez essentiellement le nœud qui est directement au-dessus de la ligne en cours de dessin.

Answer 2

Oubliez les définitions, il est tellement plus facile d'appliquer simplement l'algorithme:

void inOrderPrint(Node root)
{
  if (root.left != null) inOrderPrint(root.left);
  print(root.name);
  if (root.right != null) inOrderPrint(root.right);
}

C'est juste trois lignes. Réarrangez l'ordre pour le pré- et le post-ordre.

Answer 3

Si vous lisez attentivement, vous verrez que la première "définition" indique de commencer à gauche de la racine et que l'ordre des nœuds est déterminé par le passage en dessous d'eux. Donc, B n'est pas le premier nœud, car vous le passez sur la gauche en allant vers A, puis vous passez d'abord en dessous de A après quoi vous remontez et passez en dessous de B. Il semble donc que les deux définitions donnent le même résultat.

Answer 4

J'ai personnellement trouvé cette conférence assez utile.

Answer 5

Les deux définitions donnent le même résultat. Ne vous laissez pas berner par les lettres dans le premier exemple - regardez les chiffres le long du chemin. Le deuxième exemple utilise en effet des lettres pour indiquer le chemin - c'est peut-être ce qui vous embrouille.

Par exemple, dans votre ordre d'exemple montrant comment vous pensiez que le deuxième arbre serait traversé en utilisant l'algorithme du premier, vous placez "D" après "B" mais vous ne devriez pas car il y a toujours un nœud enfant à gauche de D disponible (c'est pourquoi le premier élément dit "l'ordre dans lequel cette ligne passe en dessous d'eux."