Comment effectuer un parcours dans l'ordre d'un arbre binaire en langage C ?

La méthode de parcours dans l'ordre d'un arbre binaire en langage C : parcourir d'abord le sous-arbre de gauche, et continuer à visiter à l'aide de la récursion jusqu'au nœud le plus à gauche puis visiter enfin le nœud racine ; sous-arbre droit et continuez à visiter avec l'aide de la récursion. Allez simplement au nœud le plus à droite.

La méthode de parcours dans l'ordre d'un arbre binaire en langage C :

La règle d'in- le parcours de l'ordre est : sous-arbre gauche ---> Nœud racine ---> L’ordre dans lequel nous visitons les nœuds doit donc changer.

• On attend que la récursion soit un processus de va-et-vient, pour un nœud qui a exactement deux nœuds enfants (pas de nœuds enfants). Il vous suffit de visiter le nœud de gauche une fois, de visiter la racine et de visiter le nœud de droite. C'est ça.

• Et s'il y a des nœuds des deux côtés. Chaque nœud doit satisfaire aux règles de parcours dans l'ordre. Nous visitons d'abord le nœud gauche depuis la racine. Lorsqu'il atteint le nœud gauche, le nœud gauche redevient un sous-arbre, qui doit également répondre aux exigences du parcours dans l'ordre. Nous devons donc d'abord accéder au nœud gauche du nœud gauche (s'il existe). Donc si vous le pensez, vous comprenez les règles. Mais c'est trop compliqué. Ensuite, nous utilisons la récursion. Parce que ses sous-problèmes sont les mêmes que les problèmes du nœud racine, mais la portée est réduite. Nous utilisons donc la pensée récursive pour le résoudre.

• Alors la logique récursive est la suivante : compte tenu des circonstances particulières (accès direct si spécial), ne pas récursivement, sinon accéder de manière récursive au sous-arbre de gauche (laisser le sous-arbre de gauche exécuter la même fonction, arrêter la récursion si spécial) Sortie, continuez à chercher jusqu'à ce que le nœud le plus à gauche ne soit pas spécial)——>Sortie du nœud——>Accédez de manière récursive au sous-arbre de droite.

public void zhongxu(node t)// 中序遍历 中序遍历：左子树---> 根结点 ---> 右子树
{
if (t != null) {
zhongxu(t.left);
System.out.print(t.value + " ");// 访问完左节点访问当前节点
zhongxu(t.right);
}
}

Apprentissage connexe recommandé : Tutoriel vidéo C

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!