Zhejiang University Edition "Data Structure" Exercise 4.3 Whether the binary search tree (25 points)

This question requires the realization of the function to determine whether the given binary tree is a binary search tree. Function interface definition:

bool IsBST ( BinTree T );

where the BinTree structure is defined as follows:

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

The function IsBST shall determine whether the given T is a binary search tree, that is, a binary tree that satisfies the following definition: Definition: A binary search tree is a binary tree that can be empty. If it is not empty, it will satisfy the following properties:

  1. All non-empty left subtrees have less key values ​​than their root nodes. The
  2. non-empty right subtree has all the key values ​​greater than the key value of its root node.
  3. Left and right subtrees are binary search trees. The function returns true if T is a binary search tree, otherwise returns false.

Referee test program example:

#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree BuildTree(); /* by the referee, the details are not listed */bool IsBST( BinTree T );

int main()
{
    BinTree T;

    T = BuildTree();
    if ( IsBST(T) ) printf("Yes\n");
    else printf("No\n");

    return 0;
}
/* Your code will be embedded here */

** Input example 1: ** as shown below 样例1 出样样1:

Yes

** Input example 2: ** as shown below sample 2 出样样2:

No

码: Recursive method

Algorithm: There are four cases of a non-empty node in the binary search tree: 1. Left space & & right space; 2. Left space & & right non-empty; 3. Left non-empty & & right space; 4. Left non-empty & & right non-empty. recursive exit: left empty && right empty. Recursive function: The rest of the situation. The necessary condition of the binary tree node : is greater than the maximum value of the left subtree, less than the minimum value of the right subtree.

bool IsBST ( BinTree T ){
    BinTree p=NULL;
    if(!T){ /*Recursive export*/
        return true;
    }
    else{ /* non-empty tree*/
        if(!T->Left){
            if(!T->Right)   /* left empty && right empty: recursive export */
                return true;
            else{           /* left empty && right non-empty: Need to judge the right subtree * / | | | p
                p = T->Right;
                while(p->Left){
                    p = p->Left;
                }
                if(T->Data >= p->Data)
                    return false;
                else
                    return IsBST(T->Right);
            }
        }
        else{    / * left non-empty: need to judge the left subtree * / | | | p
            p = T->Left;
            while(p->Right){
                p = p->Right;
            }
            if(T->Data <= p->Data)
                return false;
            else{
                if(!T->Right)    / * left non-empty & & right empty: no need to judge the right subtree */
                    return IsBST(T->Left);
                else{           /* Left non-empty & & right non-empty: need to judge the right subtree */p= T->Right;
                    while(p->Left){
                        p = p->Left;
                    }
                    if(T->Data >= p->Data)
                        return false;
                    else
                        return ( IsBST(T->Left) && IsBST(T->Right) );
                    }
            }
        }
    }
}