Trouver une boucle dans un arbre binaire

Comment trouver une boucle dans un arbre binaire? Je suis à la recherche d'une solution autre que le marquage des nœuds visités visité ou faire une adresse de hachage. Des idées?

S'il pouvait y avoir des boucles, alors c'est juste l'habitude graphique. Il existe un certain nombre de façons de trouver la boucle: stackoverflow.com/questions/546655/finding-all-cycles-in-graph

OriginalL'auteur novice | 2012-07-05

  1. 1

    Comme déjà mentionné: Un arbre n'a pas (par définition) contiennent des cycles (boucles).

    Pour tester si votre graphe orienté contient des cycles (références à des nœuds déjà ajouté à l'arbre), vous pouvez effectuer une itération creux de l'arbre et de l'ajout de chaque nœud visité de liste (ou de la valeur de hachage d'elle, si vous préférez) et vérifier chaque nouveau nœud si il est dans la liste.
    Beaucoup d'algorithmes pour le cycle de détection dans les graphiques sont juste un google-recherche à l'écart.

    OriginalL'auteur mariusnn

  2. 1

    Supposons que vous avez un arbre binaire, mais vous n'avez pas confiance en elle et vous pensez que cela peut être un graphique, le cas général va dicter à rappeler les nœuds visités. Il est, en quelque sorte, le même algorithme pour construire un minimum spanning tree à partir d'un graphique et cela signifie que l'espace et le temps, la complexité sera un problème.

    Une autre approche serait de considérer les données que vous enregistrez dans l'arbre. Considérez que vous avez des numéros de hachages de sorte que vous pouvez comparer.

    Un pseudocode serait un test pour cette conditions:

    1. Chaque nœud d'avoir un maximum de 2 enfants et 1 parent (max 3 connexions). Plus de 3 connexions => pas un arbre binaire.
    2. Le parent ne doit pas être un enfant.

    3. Si un noeud a deux enfants, puis la gauche de l'enfant a une valeur plus petite que le parent et l'enfant a une plus grande valeur. Donc, compte tenu de ce que, si une feuille, ou intérieure nœud a comme un enfant un nœud de niveau supérieur (comme le parent du parent), vous pouvez déterminer une boucle basée sur les valeurs. Si un enfant est un droit nœud puis c'est la valeur doit être supérieure à celle du parent, mais si l'enfant forme une boucle, cela signifie qu'il est de la partie gauche ou la partie droite de la mère.

      3.un. Donc, si c'est à partir de la partie gauche, puis sa valeur est plus petite que son frère. Donc => pas un arbre binaire. L'idée est un peu la même chose pour l'autre partie.

    Tests de côté, sous quelle forme est l'arbre que vous voulez tester? Rappelez-vous que chaque nœud possède un pointeur vers celle du parent. Ce pointeur pointe vers un seul parent. Donc, en fonction du format de votre arbre, vous pouvez profiter de cette.

    OriginalL'auteur amb