vérifier si un arbre binaire est un arbre de recherche

droite, une autre solution simple est de faire une visite ordonnée

code java ici

boolean bst = isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

public boolean isBST(Node root, int min, int max) {
    if(root == null) 
        return true;

    return (root.data > min &&
            root.data < max &&
            isBST(root.left, min, root.data) &&
            isBST(root.right, root.data, max));
    }

mise à jour: je viens de voir que cette solution a déjà été suggérée. Désolé les gars, peut-être quelqu'un trouve encore ma version utile

Voici une solution qui utilise Dans L'Ordre Transversal pour vérifier la propriété DE BST. Avant de fournir la solution, j'utilise une définition D'un TSB qui ne permet pas les doublons. Cela signifie que chaque valeur dans le TSB est unique (c'est juste pour la simplicité).

Code récursif afinde imprimer:

void printInorder(Node root) {
    if(root == null) {                 // base case
        return;
    }
    printInorder(root.left);           // go left
    System.out.print(root.data + " "); // process (print) data
    printInorder(root.right);          // go right
}

après cet ordre de traversée sur un TSB, toutes les données doivent être imprimées dans l'ordre croissant. Par exemple l'arbre:

   5
 3   7
1 2 6 9

aurait aussitôt d'impression:

1 2 3 5 6 7 9

maintenant, au lieu d'imprimer le noeud, nous pouvons garder la trace de la valeur précédente dans la séquence dans l'ordre et la comparer à la valeur du noeud courant. Si la valeur du noeud courant est plus petite que la valeur précédente, cela signifie que la séquence n'est pas dans l'Ascendant ordre trié et que la propriété de la BST est violée.

Par exemple, l'arborescence:

   5
 3   7
1 8 6 9

A une violation. Le droit de l'enfant de 3 8 et ce serait ok si 3 était le noeud racine. Cependant, dans un BST 8 finirait comme un enfant de 9 et non pas comme un enfant de 3. Par conséquent, cet arbre n'est pas un BST. Donc, le code qui suit cette idée:

/* wrapper that keeps track of the previous value */
class PrevWrapper {
    int data = Integer.MIN_VALUE;
}

boolean isBST(Node root, PrevWrapper prev) {
    /* base case: we reached null*/
    if (root == null) {
        return true;
    }

    if(!isBST(root.left, prev)) {
        return false;
    }
    /* If previous in-order node's data is larger than
     * current node's data, BST property is violated */
    if (prev.data > root.data) {
        return false;
    }

    /* set the previous in-order data to the current node's data*/
    prev.data = root.data;

    return isBST(root.right, prev);
}

boolean isBST(Node root) {
    return isBST(root, new PrevWrapper());
}

Les dans l'ordre traversal pour l'arbre échantillon échouerait la vérification pour le noeud 5 depuis le précédent dans l'ordre de 5 8, qui est plus grande donc la propriété DE BST est violée.

    boolean isBST(TreeNode root, int max, int min) {
        if (root == null) {
            return true;
        } else if (root.val >= max || root.val <= min) {
            return false;
        } else {
            return isBST(root.left, root.val, min) && isBST(root.right, max, root.val);
        }

    }

une solution alternative pour 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 noeud gauche doit être <= la clé du noeud racine et la clé du noeud droit doit être plus grande que la racine.

donc le problème que nous avons est que si les clés dans l'arbre ne sont pas uniques et qu'une traversée dans l'ordre a été faite, nous pourrions obtenir une situation de deux traversées dans l'ordre produisant la même séquence, où 1 serait un TSB valide et l'autre pas, cela se produirait si nous avions un arbre où le noeud de gauche = racine (TSB valide) et le noeud droit = root (invalide pas un TSB).

pour contourner cela, nous avons besoin de maintenir une plage min/max valide entre laquelle la clé "visitée" doit se trouver, et nous passons cette plage comme nous le faisons à d'autres noeuds.

#include <limits>

int min = numeric_limits<int>::min();
int max = numeric_limits<int>::max();

The calling function will pass the above min and max values initially to isBst(...)

bool isBst(node* root, int min, int max)
{
    //base case
    if(root == NULL)
        return true;

    if(root->val <= max && root->val >= min)
    {
        bool b1 = isBst(root->left, min, root->val);
        bool b2 = isBst(root->right, root->val, max);
        if(!b1 || !b2)
            return false;
        return true;
    }
    return false;
}

cela n'a pas vraiment de sens de retourner entier.MIN, ENTIER.MAX comme valeurs pour un arbre vide. Peut-être utiliser un entier et retourner null à la place.

public void inorder()
     {
         min=min(root);
         //System.out.println(min);
         inorder(root);

     }

     private int min(BSTNode r)
         {

             while (r.left != null)
             {
                r=r.left;
             }
          return r.data;


     }


     private void inorder(BSTNode r)
     {

         if (r != null)
         {
             inorder(r.getLeft());
             System.out.println(r.getData());
             if(min<=r.getData())
             {
                 System.out.println(min+"<="+r.getData());
                 min=r.getData();
             }
             else
             System.out.println("nananan");
             //System.out.print(r.getData() +" ");
             inorder(r.getRight());
             return;
         }
     }

nous faisons une marche en profondeur à travers l'arbre, testant la validité de chaque noeud au fur et à mesure. Un noeud donné est valide s'il est plus grand que tous les noeuds ancestraux qu'il est dans le sous-arbre droit et moins que tous les noeuds ancestraux qu'il est dans le sous-arbre gauche de. Au lieu de garder la trace de chaque ancêtre pour vérifier ces inégalités, nous vérifions juste le plus grand nombre il doit être plus grand que (son lowerBound) et le plus petit nombre il doit être moins que (son upperBound).

 import java.util.Stack;

final int MIN_INT = Integer.MIN_VALUE;
final int MAX_INT = Integer.MAX_VALUE;

public class NodeBounds {

BinaryTreeNode node;
int lowerBound;
int upperBound;

public NodeBounds(BinaryTreeNode node, int lowerBound, int upperBound) {
    this.node = node;
    this.lowerBound = lowerBound;
    this.upperBound = upperBound;
}
}

public boolean bstChecker(BinaryTreeNode root) {

// start at the root, with an arbitrarily low lower bound
// and an arbitrarily high upper bound
Stack<NodeBounds> stack = new Stack<NodeBounds>();
stack.push(new NodeBounds(root, MIN_INT, MAX_INT));

// depth-first traversal
while (!stack.empty()) {
    NodeBounds nb = stack.pop();
    BinaryTreeNode node = nb.node;
    int lowerBound = nb.lowerBound;
    int upperBound = nb.upperBound;

    // if this node is invalid, we return false right away
    if ((node.value < lowerBound) || (node.value > upperBound)) {
        return false;
    }

    if (node.left != null) {
        // this node must be less than the current node
        stack.push(new NodeBounds(node.left, lowerBound, node.value));
    }
    if (node.right != null) {
        // this node must be greater than the current node
        stack.push(new NodeBounds(node.right, node.value, upperBound));
    }
}

// if none of the nodes were invalid, return true
// (at this point we have checked all nodes)
return true;
}