rekursive Funktion, wenn ein Baum erzählt, ist ein binärer Suchbaum (BST) (Modified-Code)

Question

ich auf den Übungen hier arbeitet: „http://cslibrary.stanford.edu/110/BinaryTrees.html#s2“
ich eine Funktion geschrieben, die ein Baum entscheidet, ob ein BST (Rückkehr 1) oder nicht (0 zurückgeben), aber ich bin mir nicht sicher, ob mein Code total gut ist, ich habe ihn für einen BST und einen Nicht-BST-Baum getestet und es scheint korrekt zu funktionieren. Ich möchte die Meinung der Gemeinschaft wissen: Aktualisiert-Code:

betrachten den Baum (kein BST):

 5 
    /\ 
    2 7 
/\ 
1 6 

Meine Idee ist 2 mit 5 zu vergleichen, wenn es gut ist, dann 1 mit 5, und wenn es gut ist, dann 6 mit 5, wenn es gut ist, dann 1 mit 2, wenn es gut ist, dann 6 mit 2, wenn es gut ist, dann 5 mit 7; Wenn es gut ist, gibt isBST() 1 zurück. Dieser Code soll es rekursiv tun.

der Knotenstruktur:

struct node { 
    int data; 
    struct node* left; 
    struct node* right; 
}; 

der Code:

int lisgood(struct node* n1,struct node* n2) 
{ 
    if(n2 == NULL) 
     return 1; 
    else{ 
    int r = lisgood(n1,n2->left)*lisgood(n1,n2->right); 
     if(r){ 
      if(n1->data >= n2->data) 
      { 
       return r; 
      } 
      else return 0; 
     } 
     else return r; 
    } 
} 
int risgood(struct node* n1,struct node* n2) 
{ 
    if(n2 == NULL) 
     return 1; 
    else{ 
     int r = risgood(n1,n2->right)*risgood(n1,n2->left); 
     if(r){ 
      if(n1->data < n2->data) 
      { 
       return r; 
      } 
      else return 0; 
     } 
     else return r; 
    } 
} 

int isBST(struct node* node) 
{ 
    if(node == NULL) 
     return 1; 
    else{ 
     if(lisgood(node,node->left)&&risgood(node,node->right)){ 
      return (isBST(node->left)&&isBST(node->right)); 
     } 
     else return 0; 
    } 
} 

Answer 1

Ihr Code wirklich funktioniert nicht - nicht einmal für das Beispiel, das Sie zeigte. Sie vergleichen nie 5 bis 6. Grundsätzlich vergleichen Sie die Wurzel eines Unterbaums mit root->left, root->left->left, root->left->left->left usw. Dann vergleichen Sie root mit root->right, root->right->right, etc., aber Sie vergleichen nie Wurzel mit den anderen Knoten in der Teilbaum. Das Problem ist, dass Sie die Wurzel eines Baumes nicht mit jedem Element auf seiner rechten und linken Unterstruktur vergleichen, und Sie sollten.

Dies ist eine bekannte Interviewfrage. Der einfachere Weg, es zu lösen, besteht darin, die für einen Unterbaum zulässigen minimalen und maximalen Werte als Parameter zu übergeben.

So funktioniert es mit dem von Ihnen gezeigten Beispielbaum: Sie sehen 5, daher ist der Maximalwert für jeden Knoten in 5 im linken Teilbaum 5. Ebenso ist der Mindestwert für jeden Knoten im rechten Teilbaum 5 Eigenschaft wird rekursiv angewendet, um zu überprüfen, ob der Wert jedes Knotens den Anforderungen entspricht. Hier ist eine Arbeits Implementierung (nimmt einen Baum ohne Duplikate):

#include <stdio.h> 
#include <limits.h> 

struct tree_node { 
    int key; 
    struct tree_node *left; 
    struct tree_node *right; 
}; 

static int is_bst_aux(struct tree_node *root, int min, int max) { 
    if (root == NULL) { 
     return 1; 
    } 

    if (!(min < root->key && root->key < max)) { 
     return 0; 
    } 

    if (!is_bst_aux(root->left, min, root->key)) { 
     return 0; 
    } 

    return is_bst_aux(root->right, root->key, max); 
} 

int is_bst(struct tree_node *root) { 
    return is_bst_aux(root, INT_MIN, INT_MAX); 
}