我已经编写了以下代码来检查树是否是二叉搜索树。请帮助我检查代码:
好的!代码已被编辑。下面的帖子中有人建议这种简单的解决方案:
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值,则应使用容器(我使用ArrayList),并存储一个Node, Min, Max表示根节点和值的三元组(显然)。
Min
Max
ArrayList
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<TreeValues> myValues = new ArrayList<TreeValues>;
现在,这是一种查找给定节点的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); }
但这仅返回一个节点的值,因此我们将使用它来查找整棵树:
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。它应该可以进行一些修改和修复。找到一本很好的面向对象的书,它将对您有所帮助。注意,该解决方案可以分解为更多方法。