NOIP 普及 2013 第一轮 第 34 题：递归判断二叉查找树：第 3 空

题目

完善程序：
（二叉查找树） 二叉查找树具有如下性质： 每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。
输入的第一行包含一个整数 $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 << is_bst( ⑤, -INFINITE, INFINITE ) << endl;
	return(0);
}

③处应填（ ）

答案

cur

题解

考点定位

本题（BST 判定第③空）考「新下界传入」,对应大纲 3.2.2 BST（难度【3】）。

解题过程

③处右子树递归的下界参数：

``cpp is_bst(a[root].right_child, cur, upper_bound) ``

答案：cur。

易错提醒

① 进入右子树 ⇒ 所有结点必须 > 当前值；② 下界/上界的开闭区间要与「严格大于」对应。