判别给定二叉树是否为二叉排序树的算法

判断给定二叉树是否为二叉排序树的算法如下：

1. 如果二叉树为空，则返回 true。

2. 如果二叉树不为空，则判断其左子树是否为二叉排序树，如果不是，则返回 false。

3. 判断当前节点是否大于其左子树的最大值，如果不是，则返回 false。

4. 判断当前节点是否小于其右子树的最小值，如果不是，则返回 false。

5. 判断其右子树是否为二叉排序树，如果不是，则返回 false。

6. 如果以上条件都满足，则返回 true。

其中，判断一个二叉树是否为二叉排序树，需要用到中序遍历，即先遍历左子树，再遍历根节点，最后遍历右子树。如果遍历的结果是一个递增的序列，则该二叉树为二叉排序树。

相关问题

【问题描述】试写一个判别给定二叉树是否为二叉排序树的算法。以前序遍历序列和中序遍历序列给出该二叉树的结点，并创建该二叉树。然后再进行判断。请注意，树中结点关键字可能相同。 先创建二叉树的链式存储，再对其进行判断。 【样例输入】 6 4 5 8 6 9 0 4 5 6 6 8 9 0 【样例输出】 true C/C++源代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10010;
int pre[maxn],in[maxn],n;
bool flag=false;//判断是否为二叉排序树的标志
struct node{
    int data;
    node* lchild,*rchild;
};
node* build(int preL,int preR,int inL,int inR){
    if(preL>preR) return NULL;
    node* root=new node;
    root->data=pre[preL];
    int k;
    for(k=inL;k<=inR;k++){
        if(in[k]==pre[preL]) break;
    }
    int numleft=k-inL;
    root->lchild=build(preL+1,preL+numleft,inL,k-1);
    root->rchild=build(preL+numleft+1,preR,k+1,inR);
    return root;
}
void traversal(node* root){
    if(root==NULL) return;
    traversal(root->lchild);
    if(flag==true) return;//已经不是二叉排序树了，就可以直接返回了
    if(root->lchild!=NULL&&root->rchild!=NULL){
        if(root->lchild->data>root->data||root->rchild->data<root->data){
            flag=true;
            return;
        }
    }
    traversal(root->rchild);
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>pre[i];
    for(int i=0;i<n;i++)
        cin>>in[i];
    node* root=build(0,n-1,0,n-1);
    traversal(root);
    if(flag==true) cout<<"false"<<endl;
    else cout<<"true"<<endl;
    return 0;
}

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

这是一个 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，表示该二叉树是否为二叉排序树。

注意：本代码没有对输入数据进行特判，如序列长度不一致等情况。在实际应用中需要进行相应的处理。