是否二叉搜索树

左手的ㄟ右手 2021-11-29 08:58 286阅读 0赞

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

转载于:https://www.cnblogs.com/1112zx/p/10865471.html

发表评论取消回复

表情：

评论列表（有 0 条评论，286人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉搜索树、平衡二叉树

一、二叉搜索树这里我们不用太多书面化的语言来定义，笔者认为在讨论数据结构、算法相关的内容时用太多书面化、学术化的语言是一种让人很烦的事情。咬文嚼字，不便于读者理解。

阳光穿透心脏的1/2处/ 2023年10月18日 22:26/ 0 赞/ 30 阅读

相关二叉搜索树

在计算机术语中，二叉搜索树又叫二叉查找树、二叉排序树。二叉搜索树（Binary Search Tree）的定义：它或者是一棵空树，或者是具有下列性质的二叉树：若它的

Myth丶恋晨/ 2022年09月30日 06:45/ 0 赞/ 190 阅读

相关二叉搜索树

二叉搜索树的特征定义就是：一个节点的左子节点的关键字值小于这个节点，右子节点的关键字大于或等于这个父节点 package Trees; import java.ut

客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 268 阅读

相关验证一棵树是否为二叉搜索树

由一道小库科技笔试题而生出来的一篇博文，题目如下： > 给予一个二叉树的根节点，验证该树是否是二叉搜索树，在O(n)时间内，用熟悉的语言写出算法。不了解二叉搜索树的盆友可

系统管理员/ 2022年05月08日 09:14/ 0 赞/ 180 阅读

相关二叉搜索树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy

た入场券/ 2022年03月17日 02:18/ 0 赞/ 265 阅读

相关是否二叉搜索树PTA

本题要求实现函数，判断给定二叉树是否二叉搜索树。函数接口定义： bool IsBST ( BinTree T ); 其中BinTree结构定义如下：

雨点打透心脏的1/2处/ 2022年02月03日 07:06/ 0 赞/ 228 阅读

相关判断二叉树是否是二叉搜索树

问题给定一棵二叉树，判定该二叉树是否是二叉搜索树（Binary Search Tree）？解法1:暴力搜索首先说明一下二叉树和二叉搜索树的区别。二叉树指这

ゝ一世哀愁。/ 2021年12月21日 07:39/ 0 赞/ 243 阅读

相关是否二叉搜索树

6-1 是否二叉搜索树 (25 分) 本题要求实现函数，判断给定二叉树是否二叉搜索树。函数接口定义： bool IsBST ( BinTree T ); 其中B

左手的ㄟ右手/ 2021年11月29日 08:58/ 0 赞/ 287 阅读

相关二叉搜索树

二叉搜索树基本概念二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 337 阅读

相关判断是否为同一颗二叉搜索树（二叉排序树）

判断方法 1、分别建立两颗搜索树，通过递归，比较根，左子树，右子树是否相同； 2、不建树的判别方法； 3、只建一棵树，在判别其他序列是否与该树一致； [点击显

ゝ一世哀愁。/ 2021年11月10日 07:44/ 0 赞/ 335 阅读