文档章节

6-2 是否二叉搜索树(25 分)

o
 osc_z1hvg4cu
发布于 2018/04/24 20:58
字数 387
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

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

函数接口定义:

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)
return true;
if(!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<T->Data)
return false;
}
return IsBST(T->Left)&&IsBST(T->Right);
}

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

63. Unique Paths II

题目: 63. Unique Paths II A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any p......

JiaMing
18分钟前
26
0
前后端分离了,跨域问题怎么处理?

利用Nginx反向代理解决跨域问题 使用jsonp 来进行解决,不推荐,老项目可以使用此方案,但是发送的http 请求体有大小限制,并且发送方式为get方式,大小限制、不安全。 服务器代理 CORS 请求...

SpringForA
20分钟前
19
0
Hacker News 简讯 2020-07-10

更新时间: 2020-07-10 00:00 How to track and display profile views on GitHub - (rushter.com) 如何在GitHub上跟踪和显示概要视图 得分:80 | 评论:36 XMEMS Announces World's First Mon......

FalconChen
35分钟前
83
0
如何在Java中将文本追加到现有文件 - How to append text to an existing file in Java

问题: I need to append text repeatedly to an existing file in Java. 我需要将文本重复添加到Java中的现有文件中。 How do I do that? 我怎么做? 解决方案: 参考一: https://stackoom...

fyin1314
昨天
12
0
Eclipse HotKey:如何在选项卡之间切换? - Eclipse HotKey: how to switch between tabs?

问题: How can I switch between opened windows in Eclipse? 如何在Eclipse中打开的窗口之间切换? There is Ctrl + F6 , but it's asking me which one I want, but I want switch it lik......

富含淀粉
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部