vendredi 29 mai 2015

recursive function that tells if a Tree is a Binary Search Tree ( BST ) (Modified code)

I was working on the exercises here : "http://ift.tt/1LMovHG"
I wrote a function that decides if a Tree is a BST(return 1) or not(return 0) but I'm not sure if my code is totally good, I tested it for a BST and a non-BST Tree and it seems to work correctly. I want to know the opinion of the community : Updated Code :

consider the Tree ( not a BST ) :

     5  
    / \ 
   2   7 
  / \ 
 1   6

my Idea is to compare 2 with 5 if it's good, then 1 with 5, and if it's good then 6 with 5 if it's good then 1 with 2 if it's good then 6 with 2 if it's good then 5 with 7 ; if it's good isBST() returns 1. this code is supposed to do it recursively.

the node structure :

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

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

Aucun commentaire:

Enregistrer un commentaire