是否二叉搜索树
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->data
return false;
}
return true;
}