判断一棵树是否为二叉排序树_判断一棵树是否为二叉排序树的算法

概要

由于二叉排序树的中序遍历时得到的一定是个一个升序序列，我们可以根据这一性质，利用中序遍历进行判定。

算法

1）设置全局变量max为无穷小。
2）若树为空，则返回true。
3）否则递归判断左子树是否为二叉排序树，并用flag1保存结果。
3）若flag1为假或者根节点关键字小于等于左子树的关键字，则返回false。
4）否则递归判断右子树是否为二叉排序树，并用flag2保存结果。
5）返回flag2。

//判断是否为二叉排序树 
bool Judge(BinaryTree* root,int& MAX){
    if(root == NULL){//树为空则为二叉排序树 
        return true;
    }
    bool bst_l,bst_r;
    bst_l = Judge(root->lchild,MAX);//判断左子树是否为二叉排序树
    if(!bst_l || MAX >= root->data){
        return false;
    }
    MAX = root->data;
    bst_r = Judge(root->rchild,MAX);//判断右子树是否为二叉排序树
    return bst_r;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

后记

关于二叉树的基本遍历操作相关请详见博客：二叉树的构建及其遍历算法
关于二叉排序树的基本操作相关请详见博客：二叉搜索树