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

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

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

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

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

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

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

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

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

相关问题

试写一个判别给定二叉树是否为二叉排序树的算法。用C语言

以下是一个简单的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

bool isValidBST(struct TreeNode* root) {
    return isValidBSTHelper(root, NULL, NULL);
}

bool isValidBSTHelper(struct TreeNode* root, struct TreeNode* minNode, struct TreeNode* maxNode) {
    if (root == NULL) {
        return true;
    }
    if ((minNode != NULL && root->val <= minNode->val) || (maxNode != NULL && root->val >= maxNode->val)) {
        return false;
    }
    return isValidBSTHelper(root->left, minNode, root) && isValidBSTHelper(root->right, root, maxNode);
}

int main() {
    // 构造一个二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 5;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 1;
    root->left->left = NULL;
    root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->right->val = 4;
    root->left->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->right->left->val = 3;
    root->left->right->left->left = NULL;
    root->left->right->left->right = NULL;
    root->left->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->right->right->val = 6;
    root->left->right->right->left = NULL;
    root->left->right->right->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 8;
    root->right->left = NULL;
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->val = 10;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    // 判断是否为二叉排序树
    if (isValidBST(root)) {
        printf("Given binary tree is a binary search tree.\n");
    } else {
        printf("Given binary tree is not a binary search tree.\n");
    }

    return 0;
}

该算法使用递归的方法来判断二叉树是否为二叉排序树。对于当前节点，需要保证其左子树中的所有节点值都小于当前节点的值，右子树中的所有节点值都大于当前节点的值，并且左右子树也分别是二叉排序树。为了实现这一点，算法需要同时维护一个最小值和最大值，这两个值分别表示当前节点的左子树中的最大值和右子树中的最小值。如果当前节点的值不满足上述条件之一，则返回false。否则递归判断左右子树即可。

在实现过程中，为了方便起见，我使用了一个结构体来表示二叉树节点。该结构体包含一个整数值，以及左右子树指针。同时，为了方便测试，我在main函数中构造了一个二叉树，并判断其是否为二叉排序树。

【问题描述】试写一个判别给定二叉树是否为二叉排序树的算法。以前序遍历序列和中序遍历序列给出该二叉树的结点，并创建该二叉树。然后再进行判断。请注意，树中结点关键字可能相同。 先创建二叉树的链式存储，再对其进行判断。 【样例输入】 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;
}