二叉查找树

二叉查找树具有如下性质： 每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。

输入的第一行包含一个整数 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);
}

1. ①处应填（ ）{{ select(1) }}

• cur<upper_bound
• cur<=upper_bound
• cur>upper_bound
• cur>=upper_bound

2. ②处应填（ ）{{ select(2) }}

• left_child
• right_child
• a[root].left_child
• a[root].right_child

3. ③处应填（ ）{{ select(3) }}

• left_child
• right_child
• cur+1
• cur

4. ④处应填（ ）{{ select(4) }}

• left_child
• upper_bound-1
• right_child
• upper_bound

5. ⑤处应填（ ）{{ select(5) }}

• -1
• 0
• 1
• 2