c++试写一个判别给定二叉树是否为二叉排序树的算法。以前序遍历序列和中序遍历序列给出该二叉树的结点,并创建该二叉树。然后再进行判断。请注意,树中结点关键字可能相同。 【样例输入1】 6 4 5 8 6 9 0 4 5 6 6 8 9 0 【样例输出1】 true 【样例输入2】 6 4 7 8 0 4 7 6 8 0 【样例输出2】 false
时间: 2023-12-30 14:04:12 浏览: 27
这是一个 C++ 代码示例,实现二叉排序树的判断:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v): val(v), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty()) {
return nullptr;
}
int rootVal = preorder[0];
auto root = new TreeNode(rootVal);
auto iter = find(inorder.begin(), inorder.end(), rootVal);
int idx = iter - inorder.begin();
vector<int> leftInorder(inorder.begin(), iter);
vector<int> rightInorder(iter+1, inorder.end());
vector<int> leftPreorder(preorder.begin()+1, preorder.begin()+1+idx);
vector<int> rightPreorder(preorder.begin()+1+idx, preorder.end());
root->left = buildTree(leftPreorder, leftInorder);
root->right = buildTree(rightPreorder, rightInorder);
return root;
}
bool isBST(TreeNode* root, int minVal, int maxVal) {
if (root == nullptr) {
return true;
}
if (root->val < minVal || root->val > maxVal) {
return false;
}
return isBST(root->left, minVal, root->val-1) && isBST(root->right, root->val+1, maxVal);
}
int main() {
vector<int> preorder, inorder;
int val;
while (cin >> val) {
preorder.push_back(val);
}
while (cin >> val) {
inorder.push_back(val);
}
auto root = buildTree(preorder, inorder);
cout << boolalpha << isBST(root, INT_MIN, INT_MAX) << endl;
return 0;
}
```
输入数据格式:第一行为前序遍历序列,第二行为中序遍历序列。输出数据格式:true 或 false,表示该二叉树是否为二叉排序树。
注意:本代码没有对输入数据进行特判,如序列长度不一致等情况。在实际应用中需要进行相应的处理。