Sprawdź, czy drzewo jest drzewem binarnym wyszukiwania

Question

Napisałem poniższy kod, aby sprawdzić, czy drzewo jest drzewem binarnym wyszukiwania. Proszę pomóż mi sprawdzić kod:

Okay! Kod jest teraz edytowany. To proste rozwiązanie zostało zaproponowane przez kogoś w poniższych wypowiedzi:

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

Answer 1

Metoda powinna wykonywać tylko jedną rzecz naraz. Również sposób, w jaki robisz rzeczy, jest ogólnie dziwny. Dam ci trochę pseudokodowania prawie-Java. Przepraszam za to, ale przez jakiś czas nie dotykałem Javy. Mam nadzieję, że to pomoże. Zobacz komentarze, które również zrobiłem w sprawie pytania i mam nadzieję, że to załatwisz!

Zadzwoń do isBST tak:

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

Wewnętrznie:

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

Teraz: Jeśli chcesz znaleźć Min i Max wartości każdego poddrzewo należy użyć pojemnika (użyłem ArrayList) i przechowaj triplet z Node, Min, Max, który reprezentuje węzeł główny i wartości (oczywiście).

np.

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

I:

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

Teraz jest to metoda, która wyszukuje wartości Min i Max danego węzła:

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

Ale ta zwraca wartości tylko dla jednego węzła, Więc użyjemy tego, aby znaleźć dla całego drzewa:

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

Używając tej metody, połączenie powinno wyglądać

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

To prawie Java. Powinien działać z pewnymi modyfikacjami i poprawkami. Znajdź dobrą książkę OO, to ci pomoże. Zauważ, że to rozwiązanie może być zepsute na więcej metod.

Answer 2

To naprawdę nie ma sensu, aby powrócić INTEGER.MIN, INTEGER.MAX jako wartości dla pustym drzewie. Być może użyj liczby całkowitej i zwróć wartość null.

Answer 3

prawo, inny Prostym rozwiązaniem jest zrobić wizytę Inorder

java code here

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

    } 

alternatywny sposób rozwiązania tego problemu .. podobnie z kodem

Answer 5

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

Answer 6

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

Answer 7

UPDATE : Właśnie zobaczyłem, że to rozwiązanie zasugerowano wcześniej.Przepraszam za te osoby, może ktoś nadal uważa moją wersję za przydatną

Oto rozwiązanie, które używa In-Order Traversal do sprawdzania właściwości BST. Zanim dostarczę rozwiązanie, używam definicji BST, która nie pozwala na duplikaty. Oznacza to, że każda wartość w BST jest unikalna (jest to tylko dla uproszczenia).

Kod rekurencyjne Inorder druku:

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 
} 

Po tym Inorder przechodzenie na BST, wszystkie dane powinny być wydrukowane w posortowanych rosnąco. Na przykład drzewo:

5 
3 7 
1 2 6 9 

musiałby Inorder druku:

1 2 3 5 6 7 9 

Teraz, zamiast drukować węzeł, możemy śledzić od poprzedniej wartości w kolejności rzędu i porównać ją do wartości bieżącego węzła. Jeśli wartość bieżącego węzła jest mniejsza od poprzedniej wartości, oznacza to, że sekwencja nie znajduje się w porządku posortowanym rosnąco i że właściwość BST jest naruszona.

Na przykład drzewo:

5 
3 7 
1 8 6 9 

Has naruszenie. Właściwym dzieckiem jest i byłoby ok, jeśli był węzłem głównym. Jednak w BST skończyłoby się jako lewe dziecko z , a nie jako właściwe dziecko z . Dlatego to drzewo nie jest BST. Więc kod, który po tej idei:

/* 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()); 
} 

The przechodzenie na zamówienie dla drzewa próbki nie powiedzie się czek na węźle ponieważ poprzedni w-zlecenie jest , który jest większy, więc własność BST jest naruszona.

Answer 8

Drzewo wyszukiwania binarnego ma następujące właściwości, w których kluczem dla lewego węzła musi być < = klucz węzła głównego i klucz prawego węzła musi być większy niż klucz główny.

Mamy więc problem, jeśli klucze w drzewie nie są unikatowe, a w kolejności, w której wykonano przemieszczenie, możemy uzyskać sytuację dwóch wykonanych w kolejności przesuwów wytwarzających tę samą sekwencję, gdzie 1 byłby prawidłowym bstem i inne nie, to by się stało, gdybyśmy mieli drzewo, w którym lewy węzeł = root (poprawny bst), a prawy węzeł = root (invalid a nie bst).

Aby obejść ten problem, musimy utrzymywać prawidłowy zakres min/maks., W którym klucz "odwiedzany" musi znajdować się pomiędzy, a my przechodzimy ten zakres, gdy przechodzimy do innych węzłów.

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

Answer 9

Najpierw przechodzimy przez drzewo, sprawdzając każdy węzeł pod względem trafności. Dany węzeł jest ważny, jeśli jest większy niż wszystkie węzły przodków, znajduje się w prawym podsieci i jest mniejszy niż wszystkie węzły przodków, które znajdują się w lewym podtekście.Zamiast śledzić każdego z przodków, aby sprawdzić te nierówności, po prostu sprawdzamy największą liczbę, która musi być większa niż (jej lowerBound) i najmniejszą liczbę musi być mniejsza niż (jego 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; 
}