Qu'est-ce qui rend une traversée d'arbre en pré-commande ou en ordre?

Nous avons toujours la restriction que l'enfant de gauche est visité avant l'enfant de droite.

La principale différence est où se trouve la racine.

• Si la racine est avant les deux enfants, nous l'appelons précommande. (Racine, Gauche, Droite)

• Si la racine est après les deux enfants, nous l'appelons postorder. (Gauche, Droite, Racine)

• Si la racine est entre les deux enfants, nous l'appelons inorder. (Gauche, Racine, Droite)

Le préfixe fait référence à quand le contenu du nœud racine doit être placé.

Compte tenu de cet arbre , vous pouvez le représenter de différentes manières:

• Pré-commande : la racine est placée en premier (puis les enfants à gauche et à droite ), la liste ressemblera à ceci:

[41, 20, 65, 11, 29, 50, 91, 32, 72, 99]
 |   ------  --------------  ----------
 |      |          |                |-----Level 3
 |      |          |
 |      |          |----- Level 2
 |      |
 |      |------ Level 1
 |
 |----- Level 0 (aka, the root of the tree)

Dans les sous-listes de sous-arborescence gauche et droite, la précommande est conservée.

• Dans l'ordre : l'enfant gauche est placé (analysé si vous le souhaitez) en premier, puis racine et droite strong > enfant. Cela ressemblera à ceci:

[11, 32, 29, 20, 50, 72, 99, 91, 65, 41]
 --------------  ------------------  |
       |                 |           |---- Root of the tree
       |                 |        
       |                 |----- Right sub-tree
       | 
       |------ Left sub-tree

Maintenant, la première partie de la liste représente le sous-arbre de gauche, la racine est placée après, et enfin, le sous-arbre de droite. Ici, dans l'ordre est également conservé à l'intérieur des sous-listes de sous-arborescences de gauche et de droite.

^{Le parcours dans l'ordre peut être vu comme un gauche-à-droite analyse.}

• Post-ordre : enfant gauche analysé en premier, puis enfant droit et enfin racine :

[11, 20, 29, 32, 41, 50, 65, 72, 91, 99]
 --------------  |   ------------------
      |          |            |
      |          |            |------- Right sub-tree
      |          |
      |          |---- Root of the tree
      |
      |----- Left sub-tree

Identique aux autres, la racine est à la fin, mais les sous-listes gauche et droite conservent la même propriété postorder .

De plus, d'autres parcours possibles peuvent être

• Par niveaux : les éléments sont placés triés par niveau dans l'arborescence, de gauche à droite

[41, 20, 11, 29, 32, 65, 50, 91, 72, 99]
 ^   --------------  ------------------
 |        |                     |
 |        |                     |-----Right sub-tree
 |        | 
 |        |----Left sub-tree
 |
 |------ Root of the tree

Considérez cet arbre simple:

  A
 /  \
B    C

Parcours de précommande : ABC.

Le terme contient le mot pre . pre signifie avant. Ainsi, la racine est avant l'un de ses enfants. Notez que A est avant à la fois B et C

Traversée après commande : BCA

Le terme contient le mot post . post signifie après. Ainsi, la racine est après l'un de ses enfants. Notez que A est après à la fois B et C

Traversée dans l'ordre : BAC

Le terme contient le mot In . In signifie à l'intérieur (au milieu). La racine est donc au milieu de ses enfants. Notez que A est entre B et C