判断一棵树是否为二叉排序树---AI那点小事

概要

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

算法

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; }后记

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

---来自腾讯云社区的---AI那点小事