Проверьте, является ли дерево двоичным деревом поиска

Ответ 1

Метод должен делать только одно за раз. Также, как вы делаете вещи, как правило, странно. Я дам вам несколько почти-Java псевдокодов. Извините за это, но я не коснулся Java некоторое время. Я надеюсь, что это помогает. Посмотрите на комментарии, которые я также сделал по Вопросу, и я надеюсь, что вы разобрались!

Вызовите свой isBST следующим образом:

public boolean isBst(BNode node)
{
    return isBinarySearchTree(node , Integer.MIN_VALUE , Integer.MIN_VALUE);
}

Внутренне:

public boolean isBinarySearchTree(BNode node , int min , int max)
{
    if(node.data < min || node.data > max)
        return false;
    //Check this node!
    //This algorithm doesn't recurse with null Arguments.
    //When a null is found the method returns true;
    //Look and you will find out.
    /*
     * Checking for Left SubTree
     */
    boolean leftIsBst = false;
    //If the Left Node Exists
    if(node.left != null)
    {
        //and the Left Data are Smaller than the Node Data
        if(node.left.data < node.data)
        {
            //Check if the subtree is Valid as well
            leftIsBst = isBinarySearchTree(node.left , min , node.data);
        }else
        {
            //Else if the Left data are Bigger return false;
            leftIsBst = false;
        }
    }else //if the Left Node Doesn't Exist return true;
    {
        leftIsBst = true;
    }

    /*
     * Checking for Right SubTree - Similar Logic
     */
    boolean rightIsBst = false;
    //If the Right Node Exists
    if(node.right != null)
    {
        //and the Right Data are Bigger (or Equal) than the Node Data
        if(node.right.data >= node.data)
        {
            //Check if the subtree is Valid as well
            rightIsBst = isBinarySearchTree(node.right , node.data+1 , max);
        }else
        {
            //Else if the Right data are Smaller return false;
            rightIsBst = false;
        }
    }else //if the Right Node Doesn't Exist return true;
    {
        rightIsBst = true;
    }

    //if both are true then this means that subtrees are BST too
    return (leftIsBst && rightIsBst);
}

Теперь: Если вы хотите найти значения Min и Max для каждого подтипа, вы должны использовать Контейнер (я использовал ArrayList) и сохранил триплет Node, Min, Max, который представляет корень node и значения (очевидно).

например.

/*
 * A Class which is used when getting subTrees Values
 */
class TreeValues
{
    BNode root; //Which node those values apply for
    int Min;
    int Max;
    TreeValues(BNode _node , _min , _max)
    {
        root = _node;
        Min = _min;
        Max = _max;
    }
}

И a:

/*
 * Use this as your container to store Min and Max of the whole
 */
ArrayList<TreeValues> myValues = new ArrayList<TreeValues>;

Теперь это метод, который находит значения Min и Max данного node:

/*
 * Method Used to get Values for one Subtree
 * Returns a TreeValues Object containing that (sub-)trees values
 */ 
public TreeValues GetSubTreeValues(BNode node)
{
    //Keep information on the data of the Subtree Startnode
    //We gonna need it later
    BNode SubtreeRoot = node;

    //The Min value of a BST Tree exists in the leftmost child
    //and the Max in the RightMost child

    int MinValue = 0;

    //If there is not a Left Child
    if(node.left == null)
    {
        //The Min Value is this node data
        MinValue = node.data;
    }else
    {
        //Get me the Leftmost Child
        while(node.left != null)
        {
            node = node.left;
        }
        MinValue = node.data;
    }
    //Reset the node to original value
    node = SubtreeRoot; //Edit - fix
    //Similarly for the Right Child.
    if(node.right == null)
    {
        MaxValue = node.data;
    }else
    {
        int MaxValue = 0;
        //Similarly
        while(node.right != null)
        {
            node = node.right;
        }
        MaxValue = node.data;
    }
    //Return the info.
    return new TreeValues(SubtreeRoot , MinValue , MaxValue);   
}

Но это возвращает значения только для одного node, поэтому мы будем использовать это, чтобы найти для всего дерева:

public void GetTreeValues(BNode node)
{
    //Add this node to the Container with Tree Data 
    myValues.add(GetSubTreeValues(node));

    //Get Left Child Values, if it exists ...
    if(node.left != null)
        GetTreeValues(node.left);
    //Similarly.
    if(node.right != null)
        GetTreeValues(node.right);
    //Nothing is returned, we put everything to the myValues container
    return; 
}

Используя эти методы, ваш вызов должен выглядеть как

if(isBinarySearchTree(root))
    GetTreeValues(root);
//else ... Do Something

Это почти Java. Он должен работать с некоторыми изменениями и исправлениями. Найдите хорошую книгу OO, это поможет вам. Обратите внимание, что это решение может быть разбито на несколько методов.

Ответ 2

вправо, другое простое решение - это сделать inorder visit

java-код здесь

Ответ 3

ОБНОВЛЕНИЕ: Я только видел, что это решение было предложено раньше. Извините, ребята, может быть, кто-то по-прежнему находит мою версию полезной.

Вот решение, в котором используется Отслеживание заказов, чтобы проверить свойство BST. Прежде чем предоставить решение, я использую определение BST, которое не позволяет дублировать. Это означает, что каждое значение в BST уникально (это просто для простоты).

Код для рекурсивной печати по порядку:

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
}

После этого обхода обхода по BST все данные должны быть напечатаны в отсортированном порядке по возрастанию. Например дерево:

   5
 3   7
1 2 6 9

будет иметь встроенную печать:

1 2 3 5 6 7 9

Теперь, вместо печати node, мы можем отслеживать предыдущее значение в последовательности In-Order и сравнивать его с текущим значением node. Если текущее значение node меньше предыдущего значения, это означает, что последовательность не находится в порядке сортировки по возрастанию и что свойство BST нарушено.

Например, дерево:

   5
 3   7
1 8 6 9

Имеет нарушение. Правильный ребенок 3 8, и это было бы нормально, если 3 был корнем node. Однако в BST 8 закончится как левый дочерний элемент 9, а не как правый ребенок 3. Поэтому это дерево не является BST. Итак, код, который следует этой идее:

/* 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 data is larger than
     * current node data, BST property is violated */
    if (prev.data > root.data) {
        return false;
    }

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

    return isBST(root.right, prev);
}

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

В обходном порядке для дерева образцов произойдет проверка на node 5, поскольку предыдущий порядок 5 8 > , что больше, чем нарушено свойство BST.

Ответ 4

    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);
        }

    }

альтернативный способ решения этой проблемы.. аналогично вашему коду

Ответ 5

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));
    }

Ответ 6

Двоичное дерево поиска имеет следующие свойства, где ключ для левого node должен быть <= root node, а правильный node ключ должен быть больше, чем корень.

Таким образом, проблема заключается в том, что ключи в дереве не уникальны, и в порядке обхода мы можем получить ситуацию, когда две обходные последовательности производят одну и ту же последовательность, где 1 будет действительным bst, а другой не было бы, это произошло бы, если бы у нас было дерево, где левый node= root (действительный bst) и правый node= root (недействительный не bst).

Чтобы обойти это, нам нужно поддерживать допустимый диапазон min/max, который должен "посещаться" ключом, и мы передаем этот диапазон, когда мы рекурсируем к другим узлам.

#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;
}

Ответ 7

На самом деле не имеет смысла возвращать INTEGER.MIN, INTEGER.MAX в качестве значений для пустого дерева. Возможно, используйте Integer и вместо этого верните нуль.

Ответ 8

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;
         }
     }

Ответ 9

Мы делаем глубокую прогулку по дереву, проверяя каждую node на достоверность, когда мы идем. Данный node действителен, если он больше, чем все его предковые узлы, в правом поддереве и меньше, чем все его предковые узлы в левом поддереве. Вместо того чтобы следить за каждым предком, чтобы проверить эти неравенства, мы просто проверяем наибольшее число, которое оно должно быть больше (его нижнее значение), а наименьшее число должно быть меньше (его верхняя граница).

 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;
}