欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

是否二叉搜索树

程序员文章站 2022-06-27 22:14:10
6 1 是否二叉搜索树 (25 分) 本题要求实现函数,判断给定二叉树是否二叉搜索树。 函数接口定义: bool IsBST ( BinTree T ); 其中BinTree结构定义如下: typedef struct TNode Position; typedef Position BinTree ......

6-1 是否二叉搜索树 (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:

yes
输入样例2:如下图

输出样例2:

no

bool isbst ( bintree t )
{
bintree p;
if((!t)||(!t->left)&&(!t->right))
return true;
p=t->left;
if(p){
while(p->right)
p=p->right;
if(p->data>t->data)
return false;
}
p=t->right;
if(p){
while(p->left)
p=p->left;
if(p->datadata)
return false;
}
return true;
}