组合题5 个小题
已作答 0 / 5
完善程序: (二叉查找树) 二叉查找树具有如下性质: 每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。 输入的第一行包含一个整数 n,表示这棵树有 n 个顶点, 编号分别为 1,2,…,n,其中编号为 1 的为根结点。之后的第 i 行有三个数 value,left_child,right_child ,分别表示该节点关键字的值、左子节点的编号、右子节点的编号;如果不存在左子节点或右子节点,则用 0 代替。输出 1 表示这棵树是二叉查找树,输出 0 则表示不是。
1#include <iostream>2using namespace std;3const int SIZE = 100;4const int INFINITE = 1000000;5struct node6{7 int left_child, right_child, value;8}; node a[SIZE];9int is_bst( int root, int lower_bound, int upper_bound )10{11 int cur;12 if ( root == 0 )13 return(1);14 cur = a[root].value;15 if ( (cur > lower_bound) && ( ① ) && (is_bst( a[root].left_child, lower_bound, cur ) == 1) && (is_bst( ②, ③, ④ ) == 1) )16 return(1);17 return(0);18}19 20int main()21{22 int i, n; cin >> n;23 for ( i = 1; i <= n; i++ )24 cin >> a[i].value >> a[i].left_child >> a[i].right_child;25 cout << is_bst( ⑤, -INFINITE, INFINITE ) << endl;26 return(0);27}①处应填( )