Traversée d'arbre en ordre: quelle définition est correcte?
https://stackoverflow.com/questions/486039
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai le texte suivant d'un cours académique que j'ai suivi il y a quelque temps et qui concerne la traversée en ordre (ils l'appellent aussi le «pancaking») d'un arbre binaire (pas la BST):
Traversée de l'arborescence de l'ordre
Tracez une ligne autour de l'extérieur du arbre. Commencez à gauche de la racine, et contourner l'extérieur de l'arbre, pour finir à droite de la racine. Restez le plus près possible de l'arbre, mais ne traversez pas l'arbre. (Penser à l'arbre & # 8212; ses branches et ses nœuds & # 8212; comme une barrière solide.) L'ordre du les nœuds est l'ordre dans lequel cette ligne passe sous eux. Si vous êtes Vous ne savez pas quand vous allez & # 8220; dessous & # 8221; un noeud, rappelez-vous qu’un noeud & # 8220; au à gauche & # 8221; vient toujours en premier.
Voici l'exemple utilisé (arborescence légèrement différente de celle ci-dessous)
Cependant, lorsque je fais une recherche sur google, je reçois une définition contradictoire. Par exemple, exemple wikipedia :
Séquence de traversée de l’ordre: A, B, C, D, E, F, G, H, I (leftchild, rootnode, right node)
Mais selon (à ma connaissance) la définition n ° 1, cela devrait être
A, B, D, C, E, F, G, I, H
Quelqu'un peut-il préciser quelle définition est correcte? Ils peuvent être tous deux décrivant différentes méthodes de parcours, mais utilisent le même nom. J'ai du mal à croire que le texte universitaire revu par les pairs est faux, mais je ne peux pas en être sûr.
La solution
Dans ma mauvaise tentative de dessin, voici l'ordre dans lequel ils doivent être choisis.
Choisissez le nœud situé directement au-dessus de la ligne dessinée.
Autres conseils
Oubliez les définitions, il est tellement plus simple 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);
}
Ce ne sont que trois lignes. Réorganisez la commande avant et après la commande.
Si vous lisez attentivement, vous voyez que la première " définition " indique de démarrer à gauche de la racine et que l’ordre des nœuds est déterminé par le passage de sous . Donc, B n’est pas le premier noeud, car vous le passez de la gauche à A, puis passez d'abord sous <=> après quoi vous montez et passez sous <=>. Il semble donc que les deux définitions donnent le même résultat.
J'ai personnellement trouvé la conférence utile.
Les deux définitions donnent le même résultat. Ne vous fiez pas aux lettres du premier exemple - regardez les chiffres le long du chemin. Le deuxième exemple utilise des lettres pour indiquer le chemin - c’est peut-être ce qui vous dégoûte.
Par exemple, dans votre exemple, dans lequel vous indiquez comment vous pensiez que le deuxième arbre serait traversé à l'aide de l'algorithme du premier, placez & «D &»; après " B " mais vous ne devriez pas, car il reste encore un noeud enfant de gauche de D (c'est pourquoi le premier élément indique & "; l'ordre dans lequel cette ligne passe en dessous ). "
c'est peut-être tard, mais cela pourrait être utile à tout le monde plus tard .. Il suffit de ne pas ignorer les nœuds factices ou nuls, par exemple, le nœud G a un nœud nul de gauche .. Considérer ce nœud nul va tout régler correctement ..
La traversée appropriée serait: aussi loin que possible avec les noeuds feuille (pas les noeuds racine)
Racine gauche droite
A B NULL
C D E
Null F G
H I NULL
F est root ou à gauche, je ne suis pas sûr
Je pense que le premier arbre binaire contenant la racine de a est un arbre binaire mal construit.
Essayez de le mettre en œuvre de sorte que tout le côté gauche de l’arbre soit inférieur à la racine et que tout le côté droit de l’arbre soit supérieur ou égal à la racine.
Mais selon (ma compréhension de) définition n ° 1, cela devrait être
A, B, D, C, E, F, G, I, H
Malheureusement, votre compréhension est fausse.
Chaque fois que vous arrivez sur un nœud, vous devez descendre jusqu'à un nœud gauche disponible avant de regarder le nœud actuel, puis un nœud droit disponible. Lorsque vous avez choisi D avant C, vous n'êtes pas d'abord descendu vers le noeud de gauche.
Hé, selon moi, comme mentionné dans wiki est correct, la séquence pour un parcours en ordre est gauche-racine-droite.
Jusqu'à A, B, C, D, E, F je pense que vous avez déjà compris. Maintenant, après la racine F, le nœud suivant est G qui n’a pas de nœud gauche, mais un nœud droit, conformément à la règle (left-root-right) et null-g-right. Maintenant, je suis le nœud droit de G mais j’ai un nœud gauche, donc la traversée serait GHI. C’est correct.
J'espère que cela vous aidera.
Pour une traversée d'arbres en ligne, vous devez garder à l'esprit que l'ordre de traversée est left-node-right. Pour le diagramme ci-dessus sur lequel vous avez un conflit, votre erreur se produit lorsque vous lisez un nœud parent avant de lire les nœuds feuille (enfants) à gauche.
La traversée appropriée serait: aussi loin que possible avec les nœuds terminaux (A), revenir au nœud parent (B), déplacez-vous vers la droite, mais puisque D a un enfant à sa gauche, vous redescendez (C) , remontez jusqu'au parent de C (D), à l'enfant droit de D (E), retournez à la racine (F), déplacez-vous vers la feuille de droite (G), déplacez-vous vers la feuille de G mais, comme il possède un nœud de feuille gauche, déplacez-vous là (H), retournez au parent (I).
la traversée ci-dessus lit le nœud quand je le fais entre parenthèses.
données de package;
public class BinaryTreeTraversal {
public static Node<Integer> node;
public static Node<Integer> sortedArrayToBST(int arr[], int start, int end) {
if (start > end)
return null;
int mid = start + (end - start) / 2;
Node<Integer> node = new Node<Integer>();
node.setValue(arr[mid]);
node.left = sortedArrayToBST(arr, start, mid - 1);
node.right = sortedArrayToBST(arr, mid + 1, end);
return node;
}
public static void main(String[] args) {
int[] test = new int[] { 1, 2, 3, 4, 5, 6, 7 };
Node<Integer> node = sortedArrayToBST(test, 0, test.length - 1);
System.out.println("preOrderTraversal >> ");
preOrderTraversal(node);
System.out.println("");
System.out.println("inOrderTraversal >> ");
inOrderTraversal(node);
System.out.println("");
System.out.println("postOrderTraversal >> ");
postOrderTraversal(node);
}
public static void preOrderTraversal(Node<Integer> node) {
if (node != null) {
System.out.print(" " + node.toString());
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
public static void inOrderTraversal(Node<Integer> node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(" " + node.toString());
inOrderTraversal(node.right);
}
}
public static void postOrderTraversal(Node<Integer> node) {
if (node != null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(" " + node.toString());
}
}
}
données de package;
Node de classe publique {
E value = null;
Node<E> left;
Node<E> right;
public E getValue() {
return value;
}
public void setValue(E value) {
this.value = value;
}
public Node<E> getLeft() {
return left;
}
public void setLeft(Node<E> left) {
this.left = left;
}
public Node<E> getRight() {
return right;
}
public void setRight(Node<E> right) {
this.right = right;
}
@Override
public String toString() {
return " " +value;
}
}
preOrderTraversal > > 4 2 1 3 6 5 7 inOrderTraversal > > 1 2 3 4 5 6 7 postOrderTraversal > > 1 3 2 5 7 6 4
void
inorder (NODE root)
{
if (root != NULL)
{
inorder (root->llink);
printf ("%d\t", root->info);
inorder (root->rlink);
}
}
C'est l'approche la plus simple pour la définition récursive du parcours dans l'ordre, appelez simplement cette fonction dans la fonction principale pour obtenir le parcours dans l'ordre d'un arbre binaire donné.
Il est correct en pré-commande, nt pour en-tête
