PTA 是否二叉搜索树 (25分)

╰半夏微凉° 2023-07-26 05:26 14阅读 0赞

# PTA 是否二叉搜索树 (25分) #

本题要求实现函数，判断给定二叉树是否二叉搜索树。

## 函数接口定义： ##

bool IsBST ( BinTree T );

其中BinTree结构定义如下：

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

函数IsBST须判断给定的T是否二叉搜索树，即满足如下定义的二叉树：  
定义：一个二叉搜索树是一棵二叉树，它可以为空。如果不为空，它将满足以下性质：

*  非空左子树的所有键值小于其根结点的键值。
 *  非空右子树的所有键值大于其根结点的键值。
 *  左、右子树都是二叉搜索树。  
    如果T是二叉搜索树，则函数返回true，否则返回false。

## 裁判测试程序样例： ##

#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(); /* 由裁判实现，细节不表 */
    bool IsBST ( BinTree T );
    
    int main()
    {
        
        BinTree T;
    
        T = BuildTree();
        if ( IsBST(T) ) printf("Yes\n");
        else printf("No\n");
    
        return 0;
    }
    /* 你的代码将被嵌在这里 */

## 输入样例1：如下图 ##

![1][]

## 输出样例1： ##

Yes

## 输入样例2：如下图 ##

![3][]

## 输出样例2： ##

## 第一次刷： ##

bool IsBST ( BinTree T ){
        
    	if(!T)
    		return true;
    	if (!T->Left && !T->Right)
    		return true;
    	else if(T->Left && !T->Right)
    		return (T->Left->Data < T->Data && IsBST ( T->Left ));
    	else if(!T->Left && T->Right)
    		return (T->Right->Data > T->Data && IsBST ( T->Right ));
    	else
    		return (T->Right->Data > T->Data && T->Left->Data < T->Data && IsBST ( T->Right ) && IsBST ( T->Left ));
    }

![1][1 1]  
![1][1 2]

## ***要注意二叉搜索树的定义中的一点，简单来说就是根结点的值一定大于左子树的最大值，小于右子树的最小值。千万不要仅仅判断根结点与左右孩子大小的关系。*** ##

## 这里提供一个很好的想法：二叉搜索树的中序遍历的序列是非递减的，利用这个性质我们跑一遍中序遍历即可，设置一个全局变量pre，判断序列是否单调 ##

## 这里通过定义两个全局变量来实现 ##

int pre = -9999999, flag = 1;
    void InorderTraversal( BinTree BT ){
        
    	if(BT != NULL) {
        
    		InorderTraversal( BT->Left );
    		if (pre < BT->Data) 
    			pre = BT->Data;
    		else
    			flag = 0;
    		InorderTraversal( BT->Right );
    	}
    }
    bool IsBST ( BinTree T ) {
        
    	InorderTraversal( T );
    	if(flag)
    		return true;
    	return false;
    }

[1]: /images/20230528/05abe7d3451d4b8b838e1f9ac2671c98.png
[3]: /images/20230528/6a31b8c534184369821bdce463ed5725.png
[1 1]: /images/20230528/fdf38533dee5498387b35527148e500c.png
[1 2]: /images/20230528/5b3c9d4d633d4e5aa325bb2a84000409.png