二叉查找树

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

CPP

#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) && (___(1)___) &&
(is bst(a[root].left child, lower bound, cur) == 1) &&(is_bst(___(2)___,___(3)___,___(4)___) == 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(___(5)___, -INFINITE, INFINITE)<<endl;
 }

讨论操作

回复

相关推荐

二叉查找树