算法解析

创新互联坚实的技术研发基础赢得了行业内的良好口碑，公司成立十余年来，为千余家企业提供过网站建设、软件开发、搜索引擎优化技术、互联网大数据整合营销服务，多年的技术服务成功经验、众多的客户使我们能懂得更多，做得更好。"让您的网站跑起来"是我们一直追求的目标！

根据二叉排序树的定义，对二叉树进行递归遍历，左子树关键字比根结点关键字小，右子树的关键字比根结点的关键字大，一旦有不满足条件则可判断不是二叉排序树。通过参数 flag 的值来判断，flag 为 1 表示是二叉排序树，为 0 则表示非二叉排序树，flag 初值为 1。设定全局变量 pre(初始值为 NULL)来指向遍历过程结点的前驱。

代码

void JudgeBST(BiTree T, int &flag)
{//判断二叉树是否为二叉排序树
	if(T != NULL && flag)
	{JudgeBST(T->lchild, flag); //中序遍历左子树
		if(pre == NULL) //中序遍历的第一个结点不必判断
			pre = T;
		else if(pre->data< T->data)
			pre = T; //前驱指针指向当前结点
		else flag = 0; //不是二叉排序树
		JudgeBST(T->rchild, flag); //中序遍历右子树
	}
}

思路2

对二叉排序树来说，其中序遍历序列为一个递增有序序列，因此，对
给定的二叉树进行中序遍历，如果始终能保持前一个值比后一个值小，则说明该二叉树是一棵二叉排序树，算法如下。

代码

KeyType predt=-32767; //predt为全局变量，保存当前节点中序前驱的值，初值为
-∞
int judgeBST(BSTNode *bt)
{int b1, b2;
	if (bt==NULL) //空树是一棵二叉排序树
		return 1;
	else
	{b1=judgeBST (bt->lchild); //判断左子树
		if(b1==0ll predt>=bt->key)
			return 0;
		predt=bt->key; //保存当前节点的关键字
		b2=judgeBST (bt->rchild); //判断右子树
		return b2;
	}
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文标题：C语言：判断二叉树是否为二叉排序树的算法-创新互联
链接分享：http://myzitong.com/article/dgpscj.html