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

题目

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

④处应填（ ）

答案

upper_bound

题解

考点定位

本题（BST 判定第④空）考「递归终止上界」,对应大纲 3.2.2 BST（难度【3】）。

解题过程

④处左子树递归传入的上界：

``cpp is_bst(a[root].left_child, lower_bound, cur) ``

官方答案 upper_bound（④空位置在右子树分支，继承原上界）。

答案：upper_bound。

易错提醒

① 左子树：下界继承、上界改 cur；右子树：上界继承、下界改 cur；② 两分支别写反。