Question sur l'arbre de recherche binaire

Question

Je regarde le code suivant: http://netrsc.blogspot.com/2010/04/net-c-binary-tree.html

Suis-je raison de penser que la condition while (!Found) itérera l'arbre?

protected void Insert(T item) 
{ 
    TreeNode<T> TempNode = Root; 
    bool Found=false; 
    while (!Found) 
    { 
     int ComparedValue = TempNode.Value.CompareTo(item); 
     if(ComparedValue<0) 
     { 
      if(TempNode.Left==null) 
      { 
       TempNode.Left=new TreeNode<T>(item,TempNode); 
       ++NumberOfNodes; 
       return; 
      } 
      else 
      { 
       TempNode=TempNode.Left; 
      } 
     } 
     else if(ComparedValue>0) 
     { 
      if(TempNode.Right==null) 
      { 
       TempNode.Right=new TreeNode<T>(item,TempNode); 
       ++NumberOfNodes; 
       return; 
      } 
      else 
      { 
       TempNode=TempNode.Right; 
      } 
     } 
     else 
     { 
      TempNode=TempNode.Right; 
     } 
    } 
} 

De même, pour les méthodes de recherche et de traversée, comment fonctionnent-elles? Si rien n'est renvoyé par la méthode Traversal mais par la branche de gauche, la boucle de Find s'exécutera-t-elle à nouveau? Comment saurait-il exécuter la bonne branche?

protected IEnumerable<TreeNode<T>> Traversal(TreeNode<T> Node) 
{ 
    if (Node.Left != null) 
    { 
     foreach (TreeNode<T> LeftNode in Traversal(Node.Left)) 
      yield return LeftNode; 
    } 
    yield return Node; 
    if (Node.Right != null) 
    { 
     foreach (TreeNode<T> RightNode in Traversal(Node.Right)) 
      yield return RightNode; 
    } 
} 

Merci

Answer 1

Un exemple d'itération de l'arborescence se trouve dans la commande Find, qui appelle la fonction Traversal.

foreach (TreeNode<T> Item in Traversal(Root)) 

La fonction Traversal va itérativement retourner les articles dans l'arbre dans une profondeur d'abord, de manière gauche à droite. Si vous regardez le code Traversal, il s'appelle de manière récursive sur le côté gauche, puis récursivement sur la droite.

Traversal renvoie l'arbre entier dans un objet itérable, où les éléments sont classés en profondeur d'abord, de gauche à droite. La commande Find fait simplement une boucle dans chacun d'entre eux et quand elle frappe une correspondance, elle revient en dehors de la boucle. Fondamentalement, Traversal renvoie un itératif ordonné des éléments, Find passe par cette liste à la recherche d'une correspondance. Find n'a même pas besoin de savoir si c'est la recherche dans une liste ou un arbre ou autre. Il a juste besoin de quelque chose à parcourir pour trouver un match.

Answer 2

Pas nécessairement. Il va seulement parcourir les nœuds sur le chemin d'où le nœud inséré doit être ajouté. Il y a quelques instructions return saupoudrées dans cette boucle de sorte qu'il s'arrêtera essentiellement quand il trouvera l'emplacement correct et ajoutera le nouveau nœud. Il aurait été plus approprié (dans le code) de définir la variable Found à true à la place.

Les méthodes de traversée renvoient les noeuds des sous-arbres gauche et droit. Vous devriez noter qu'il utilise yield return et non le return. L'utiliser crée un énumérateur où chaque élément qui est cédé est ce que le numérateur retournerait pendant que vous le parcourez. Pensez-y comme mettant en pause l'exécution lorsqu'il atteint une instruction yield return. Lors de l'itération à la valeur suivante à partir du code appelant, l'exécution est poursuivie à ce point, ce qui peut potentiellement renvoyer plus de valeurs.

La recherche prendra les résultats de la traversée et renvoie la valeur stockée si elle se trouve dans l'un des nœuds.