NOIP 普及组初赛 · NOIP 2013 普及组初赛试题 第 28 题

完善程序： （二叉查找树） 二叉查找树具有如下性质： 每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。 输入的第一行包含一个整数 $n$，表示这棵树有 $n$ 个顶点， 编号分别为 $1, 2, \dots , n$，其中编号为 $1$ 的为根结点。之后的第 $i$ 行有三个数 $\mathrm{value},\mathrm{left\_child},\mathrm{right\_child}$ ，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用 $0$ 代替。输出 $1$ 表示这棵树是二叉查找树，输出 $0$ 则表示不是。

#include <iostream> 
using namespace std; 
const int SIZE = 100;
const int INFINITE = 1000000;
struct node
{
	int left_child, right_child, value;
}; node a[SIZE];
int is_bst( int root, int lower_bound, int upper_bound )
{
	int cur;
	if ( root == 0 )
		return(1);
	cur = a[root].value;
	if ( (cur > lower_bound) && ( ① ) && (is_bst( a[root].left_child, lower_bound, cur ) == 1) && (is_bst( ②, ③, ④ ) == 1) )
		return(1);
	return(0);
}


int main()
{
	int i, n; cin >> n;
	for ( i = 1; i <= n; i++ )
		cin >> a[i].value >> a[i].left_child >> a[i].right_child;
	cout << i

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

看到递归 BST 判定 → 先想每层递归必须收紧左右子树的值域边界

只查当前节点不传边界；右子树 lower 写成 -INFINITE 或 upper 写成 cur；根填 0

考点：二叉查找树递归判定｜递归边界传递

程序在做什么

输入二叉树结构，用递归函数 is_bst 检查每个节点值是否落在 (lower_bound, upper_bound) 开区间内，同时左右子树递归时更新边界。