funzione ricorsiva che dice se un albero è un Binary Search Albero (BST) (codice modificato)

Question

stavo lavorando su esercizi qui: "http://cslibrary.stanford.edu/110/BinaryTrees.html#s2"
ho scritto una funzione che decide se un albero è un BST (ritorno 1) o no (return 0) ma non sono sicuro che il mio codice sia totalmente valido, l'ho testato per un BST e un albero non BST e sembra funzionare correttamente. Voglio conoscere il parere della comunità: codice aggiornato:

considerano l'albero (non un BST):

 5 
    /\ 
    2 7 
/\ 
1 6 

la mia idea è quella di confrontare 2 con 5 se è buono, poi 1 con 5, e se va bene allora 6 con 5 se è buono allora 1 con 2 se è buono allora 6 con 2 se è buono allora 5 con 7; se è buono, BST() restituisce 1. questo codice dovrebbe farlo in modo ricorsivo.

la struttura del nodo:

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

il codice:

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

Il codice non funziona davvero - nemmeno per l'esempio che avete mostrato. Non confronti mai da 5 a 6. Fondamentalmente stai confrontando la radice di un sottoalbero con root->left, root->left->left, root->left->left->left, ecc. Quindi stai confrontando root con root->right, root->right->right, ecc., Ma non confronti mai radice con gli altri nodi in il sottoalbero Il problema è che non si confronta la radice di un albero con ogni elemento sui suoi sottoalberi destro e sinistro, e dovresti.

Questa è una domanda di intervista conosciuta. Il modo più semplice per risolverlo è passare i valori minimi e massimi consentiti per un sottoalbero come parametri.

Ecco come funziona con l'albero di esempio che hai mostrato: vedi 5, quindi il valore massimo per qualsiasi nodo sulla sottostruttura di sinistra di 5 è 5. Analogamente, il valore minimo per qualsiasi nodo sulla sottostruttura di destra di 5 è 5. Questo la proprietà viene applicata in modo ricorsivo per verificare che il valore di ogni nodo sia coerente con i requisiti. Ecco un'implementazione di lavoro (presuppone un albero senza duplicazioni):

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