检查树是否是二叉搜索树
我编写了以下代码来检查树是否是二进制搜索树。 请帮我查一下代码：
好的！ 代码现在已编辑。 以下post中有人建议使用这个简单的解决方案：
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了。 我希望它有所帮助。 看看我在问题上所做的评论，我希望你能解决它！
像这样打电话给你的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 ，则应使用Container（我使用ArrayList ）并存储Node, Min, Max的三元组Node, Min, Max它表示根节点和值（显然）。
例如。
/* * 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; } }
并且：
/* * Use this as your container to store Min and Max of the whole */ ArrayList myValues = new ArrayList ;
现在，这是一个查找给定节点的Min和Max值的方法：
/* * 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的值，所以我们将使用它来查找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; }
使用此方法，您的通话应该是这样的
if(isBinarySearchTree(root)) GetTreeValues(root); //else ... Do Something
这几乎是Java。 它应该与一些修改和修复工作。 找一本好的OO书，它会对你有帮助。 请注意，此解决方案可以分解为更多方法。
对，另一个简单的解决方案就是进行一次访问
java代码在这里
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)); }
更新：我刚刚看到此解决方案之前已被建议。 对不起这个家伙，也许有人仍觉得我的版本很有用
这是一个使用In-Order Traversal检查BST属性的解决方案。 在我提供解决方案之前，我使用的BST定义不允许重复。 这意味着BST中的每个值都是唯一的（这只是为了简单起见）。
递归inorder打印代码：
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
现在，我们可以跟踪顺序序列中的先前值，并将其与当前节点的值进行比较，而不是打印节点。 如果当前节点的值小于先前值，则意味着序列不是按升序排序并且违反了BST属性。
例如，树：
5 3 7 1 8 6 9
有违规行为。 3的右子是8 ，如果3是根节点，这将是正常的。 然而，在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'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()); }
样本树的有序遍历将无法检查节点5，因为先前的5的顺序是8 ，这更大，因此违反了BST属性。
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); } }
解决此问题的另一种方法..与您的代码类似
二叉搜索树具有以下属性，其中左节点的密钥必须<=根节点密钥，右节点密钥必须大于根节点。
所以我们遇到的问题是如果树中的键不是唯一的并且在顺序遍历中我们可以得到两个顺序遍历生成相同序列的情况，其中1将是有效的bst而另一个不会，如果我们有一个树，其中左节点= root（有效bst），右节点= root（无效而不是bst），则会发生这种情况。
为了解决这个问题，我们需要保持一个有效的最小/最大范围，即“被访问”的密钥必须介于两者之间，并且当我们递归到其他节点时，我们会通过这个范围。
#include int min = numeric_limits::min(); int max = numeric_limits ::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; }
将INTEGER.MIN，INTEGER.MAX作为空树的值返回并没有多大意义。 也许使用Integer并返回null。
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; } }
我们在树中进行深度优先遍历，测试每个节点的有效性。 如果给定节点大于它在右子树中的所有祖先节点并且少于它在左子树中的所有祖先节点，则该节点是有效的。 我们只是检查它必须大于（它的lowerBound）的最大数字，并且必须小于它的最小数字（它的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 stack = new Stack (); 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; }