检查树是否是二叉搜索树 [英] check if a tree is a binary search tree

问题描述

我编写了以下代码来检查树是否是二进制搜索树。请帮我查一下代码：

I have written the following code to check if a tree is a Binary search tree. Please help me check the code:

好的！代码现在已编辑。这个简单的解决方案是由以下帖子中的人建议的：

Okay! The code is edited now. This simple solution was suggested by someone in the posts below:

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

推荐答案

方法只能做一个一次一件事。你做事的方式也很奇怪。
我会给你一些几乎Java伪代码。对不起，但我已经有一段时间没碰过Java了。我希望它有所帮助。看看我在问题上的评论，我希望你把它整理出来！

A Method should only do one thing at a time. Also the way you do things are generally Weird. I will give you some almost-Java pseudocode. Sorry for that, but I have not touched Java for some Time. I hope it helps. Look at the comments I also did on the Question and I hope you sort it out!

像这样打电话给你的isBST：

Call your isBST like that :

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 您应该使用Container的每个子树的值（我使用 ArrayList ）和存储节点，最小值，最大值的三元组，它代表根节点和值（显然）。

Now : If you want to find the Min and Max Values of each Subtree you should use a Container (I used an ArrayList) and store a triplet of Node, Min, Max which represents the root node and the values (obviously).

例如。

/*
 * 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 给定节点的值：

Now this is a method which finds the Min and Max values of a given 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's 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's 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的值，所以我们要用它来查找对于整棵树：

But this returns Values for one Node only, So we gonna use this to find for the Whole Tree:

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

使用此方法，您的通话应该如下所示

Using this methods, your call should look like

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

这几乎是Java。它应该与一些修改和修复工作。找一本好的OO书，它会对你有帮助。请注意，此解决方案可以分解为更多方法。

This is almost Java. It should work with some modification and fix. Find a good OO book, it will help you. Note, that this solution could be broke down into more methods.

这篇关于检查树是否是二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！