判断二叉树是否为二叉搜索树
概要
这题利用二叉搜索树的特性：左子树的所有的关键字小于根节点的关键字，右子树的所有关键字都大于根结点 的关键字。二叉搜索树的中序遍历一定是个有序序列。根据这一特性可以利用二叉树的非递归中序遍历来解答这个问题。
二叉树数据结构
typedef struct node{
ElemType data; //数据域
struct node* lchild;
struct node* rchild;
}BinaryTree; 递归算法思路
1）设置全局比较变量last为二叉树数据域对应数据类型的最小值，标志变量flag为真。 2）若树有左子树且标志位flag为真，递归判断左子树是否为二叉排序树。 3）若根节点的数据域小于last，那么flag置为false。 4）把last赋值为当前根节点的数据域。 5）若存在右子树且flag为真，递归判断右子树是否为二叉排序树。 6）返回flag。
代码
int last = -32768;
bool flag = true;
bool JudgeBST(BinaryTree* root)
{
if(!root->lchild && flag){
JudgeBST(root->lchild);
}
if(root->data < last){
flag = false;
}
last = root->data;
if(root->rchild && flag){
JudgeBST(root->rchild);
}
return flag;
}非递归算法思路
1）初始化堆栈为空，设置data为当前根节点的键值，设置cur指向根节点，标志位flag为true。 2）若cur->lchild非空，那么如果cur->lchild的键值小于data那么cur入栈，cur = cur->lchild，data = cur->data。否则flag = false并结束循环。 3）若cur->lchild为空，那么cur = cur->rchild，此时cur非空，那么若cur->data大于data那么data = cur->data。否则flag = false并结束循环。若cur为空且堆栈非空，那么堆栈一直出栈，并把每出栈的指针的右孩子赋值给cur，并且之后data = cur->datal。 4）当cur为空或者堆栈不空时一直循环上述操作2）与3）。
代码
bool isBST(BinaryTree* root){
int data = root->data;
bool flag = true;
stack<BinaryTree*> s;
BinaryTree* cur = root;
while(cur||!s.empty()){
if(cur->lchild){
if(cur->lchild->data < data){
s.push(cur);
cur = cur->lchild;
data = cur->data;
}else{
flag = false;
break;
}
}else{
cur = cur->rchild;
if(cur){
if(cur->data > data){
data = cur->data;
}else{
flag = false;
break;
}
}
while(!cur&&!s.empty()){
cur = s.top();
s.pop();
cur = cur->rchild;
data = cur->data;
}
}
}
return flag;
} 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录