vérifier si un arbre binaire est un arbre de recherche
J'ai écrit le code suivant pour vérifier si un arbre Binaire est un arbre de recherche. Merci de m'aider à vérifier le code:
D'accord! Le code est publié maintenant. Cette solution simple a été proposé par quelqu'un dans les posts ci-dessous:
IsValidBST(root,-infinity,infinity);
bool IsValidBST(BinaryNode node, int MIN, int MAX)
{
if(node == null)
return true;
if(node.element > MIN
&& node.element < MAX
&& IsValidBST(node.left,MIN,node.element)
&& IsValidBST(node.right,node.element,MAX))
return true;
else
return false;
}
- quelle langue est-ce écrit dans? Il serait extrêmement utile si vous modifiez votre question à la balise à votre question de manière appropriée. Aussi, vous devez utiliser le code de la balise boutons (
{}
) pour formater votre code pour la lisibilité. Enfin, quel est le problème avec votre code? Quels sont exactement nous "vérification" pour, êtes-vous une erreur? - c'est le code java, et je suis de vérifier si un BinaryNode v satisfait les propriétés d'un arbre de recherche binaire
- pourquoi avez-vous retourner un
Pair()
?? - j'ai besoin de garder une trace des valeurs max et min
- pour l'ensemble de l'arbre ? Vous êtes à la recherche du plus petit et le plus grand nombre dans l'ensemble de l'arbre?
- pour chaque sous-arbre @Petars: NE PAS UTILISER CE POST POUR discuter AVEC des BOBS
- Je viens de faire une blague:) Vous le savez sans doute qui est Bobby Tables - xkcd.com/327 🙂
- Je pense que la façon dont vous le faites, vous obtenez seulement la
Min
etMax
pour l'Ensemble de l'Arbre, et non pas de chaque sous-arbre. - lol..merci pour le lien
- J'ai modifié le code..s'il vous plaît laissez-moi savoir si vous pensez que cela fonctionne
- avez-vous vraiment l'retourner une Paire ? En général, il devrait être évité pour une méthode à faire plus d'une chose. Je pense que vous devriez avoir une méthode qui vérifie si c'est bien un BST, et un autre qui trouve le Min et Max de chaque sous-arbre.
- par exemple, vous pourriez avoir une méthode
isBinarySearchTree()
qui vérifie si un arbre est en effet un BST, et puis après vous en assurer, utilisez une autre méthode appeléeGetSubTreeValues()
qui va mettre toutes les valeurs dans unArrayList
pour chaque sous-arbre. - il serait beaucoup plus facile, et il serait aussi plus et regarder de plus correct. Ce code est très compliqué et je ne pense pas que c'est ce que vous voulez.
- J'ai besoin d'aller maintenant, je vais donc laisser ce que je pense que vous devriez faire. Espérons que cela aide. N'oubliez pas! Chaque méthode == Une Action 🙂 Bonne chance et amusez-vous.
- fixe un petit quelque chose sur le code! Il y avait un bug sur
GetSubTreeValues()
- Que faire si il y a des entrées en double dans l'arbre? Ne devrait-elle pas être <= Max et >= Min.
Vous devez vous connecter pour publier un commentaire.
Une Méthode ne doit faire qu'une chose à la fois. Aussi la façon dont vous faites les choses sont généralement Bizarre.
Je vais vous donner quelques presque-pseudo-code Java. Désolé pour ça, mais je n'ai pas touché à Java depuis un certain Temps. J'espère que cela aide. Regardez les commentaires je l'ai également fait sur la Question et j'espère que vous faites le tri!
Appelez votre isBST comme ça :
En interne :
Maintenant : Si vous voulez trouver le
Min
etMax
Valeurs de chaque sous-arbre, vous devez utiliser un Conteneur (j'ai utilisé unArrayList
) et de stocker un triplet deNode, Min, Max
qui représente le nœud racine et les valeurs (évidemment).par exemple.
Et un :
Maintenant, c'est une méthode qui trouve la
Min
etMax
valeurs d'un nœud donné:Mais cela renvoie des Valeurs pour un seul Nœud, Donc, on va l'utiliser pour trouver des pour l'Ensemble de l'Arbre:
En utilisant cette méthode, votre escale devrait ressembler à
C'est presque Java. Il devrait fonctionner avec certains de modification et de correction. Trouver un bon OO livre, il va vous aider. Notez que cette solution pourrait être décomposée en plus de méthodes.
isBst(node)
!!droit, une solution simple est de faire un afinde visite
code java ici
Mise à JOUR: je viens de voir que cette solution a été proposé avant. Désolé les gars, peut-être quelqu'un trouve encore ma version utile
Ici est une solution qui utilise Dans L'Ordre De La Traversée pour vérifier la BST de la propriété.
Avant que j'ai la solution, je suis l'aide d'une définition de la STB qui ne permet pas de doublons. Cela signifie que chaque valeur de la BST est unique (c'est juste pour des raisons de simplicité).
Code récursif afinde d'impression:
Après cette afinde traversée sur un BST, toutes les données doivent être imprimées dans triés par ordre croissant.
Par exemple l'arbre:
aurait aussitôt d'impression:
Maintenant, au lieu de l'impression, le nœud, nous pouvons garder une trace de la valeur précédente dans l'Ordre de la séquence et de la comparer à la valeur du nœud. Si le nœud actuel de la valeur est inférieure à la valeur précédente, cela signifie que la séquence n'est pas dans l'ordre croissant de l'ordre de tri et que le BST de la propriété est violée.
Par exemple, l'arbre:
A une violation. Le droit de l'enfant de 3 est 8 et ce serait ok si 3 était le nœud racine. Cependant, dans un BST 8 finirait gauche de l'enfant de 9 et non pas comme un droit de l'enfant de 3. Par conséquent, cet arbre n'est pas un BST.
Donc, le code qui suivent cette idée:
Les dans l'ordre de la traversée de l'échantillon arbre échec de la vérification pour le nœud 5 depuis la précédente dans l'ordre de 5 est 8, qui est plus grand que la STB propriété est violée.
une autre façon de résoudre ce problème.. similaire avec votre code
Un arbre de recherche binaire a les propriétés suivantes, où la clé pour le nœud de gauche doit être <= le nœud racine de la clé et le droit nœud de clé doit être plus grand que la racine.
De sorte que le problème que nous avons est si les clés de l'arbre ne sont pas uniques et un dans l'ordre de la traversée a été fait, nous pourrions obtenir une situation de deux afin traversals la production de la même séquence, où 1 serait valable bst et l'autre ne le serait pas, ce qui se passerait si nous avions un arbre dont le nœud de gauche = racine(valable bst) et le droit nœud = racine(invalide pas un bst).
Pour contourner cela, nous avons besoin de maintenir un valide min/max de la gamme que la touche "visité" doit se situer entre les deux, et on passe cette gamme, comme nous le répéter à d'autres nœuds.
Il n'a pas vraiment beaucoup de sens pour revenir ENTIER.MIN,ENTIER.MAX que les valeurs pour un arbre vide. Peut-être utiliser un Entier et renvoie la valeur null à la place.
Nous faisons une profondeur d'abord par le biais de l'arbre, l'analyse de chaque nœud pour la validité que nous allons. Un nœud donné est valide si elle est plus grande que toutes les ancestrales noeuds, il est dans le droit de la sous-arborescence de et à moins de tous les ancestrales noeuds, il est dans le sous-arbre de. Au lieu de garder une trace de chaque ancêtre de vérifier ces inégalités, nous venons de vérifier le plus grand nombre, il doit être supérieur à (sa limite inférieure) et le plus petit nombre, il doit être inférieur à (son upperBound).