原理
搜索二叉树有2个基本性质可以用于判断:
- 左子树中的所有值都小于等于根节点的值,而右子树中的数据都大于根节点的值。
- 二叉搜索树的中序输出后数据按照非递减顺序排列
对于第一个性质,假设根节点数据为7,那么左子树最大不能超过7,而右子树都大于7。
所以我们可以在函数中增加参数minValue
和maxValue
,用来记录此子树中数据的范围。
代码I
1 2 3 4 5 6 7 8 9 10 11
| bool IsBST(BstNode* root, int minValue, int maxValue) { if (root == NULL)return true; if (root->data >= minValue && root->data < maxValue && IsBST(root->left, minValue, root->data) && IsBST(root->right, root->data, maxValue)) return true; else return false; } bool IsBinarySearchTree(BstNode* root) { return IsBST(root, INT_MIN, INT_MAX); }
|
代码II
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| void LDR(BstNode* root, vector<int>& A) { if (root == NULL)return; LDR(root->left,A); A.push_back(root->data); LDR(root->right,A); } bool ISBST(BstNode* root) { vector<int> A; LDR(root,A); for (int i = 0; i < A.size() - 1; i++) { if (A[i] >A[i + 1])return false; } return true; }
|