首先看一下二叉搜索树的定义:
或者是一棵空树,或者是具有下列性质的二叉树:
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。
原理:一棵二叉搜索树的中续遍历结果是从小到大排序好的,反之亦然。
代码:时间复杂度O(n),空间复杂度O(1)
-
boolisBSTInOrder(BinaryTree*root)
-
{
-
intprev=INT_MIN;
-
returnisBSTInOrderHelper(root,prev);
-
}
-
-
boolisBSTInOrderHelper(BinaryTree*p,int&prev)
-
{
-
if(!p)returntrue;
-
if(isBSTInOrderHelper(p->left,prev)){
-
if(p->data>prev){
-
prev=p->data;
-
returnisBSTInOrderHelper(p->right,prev);
-
}else{
-
returnfalse;
-
}
-
}
-
else{
-
returnfalse;
-
}
-
}
如果觉得上面的思路不好理解,可以先对二叉搜索树进行中序遍历,然后将遍历结果存放到一个数组中,然后判断这个数组是否是从小到大排好序,而且无重复元素的。时间复杂度O(n),空间复杂度O(n).
分享到:
相关推荐
写一算法,判断一棵二叉树是否是一棵二叉排序树。
算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、...
主要介绍了C语言判定一棵二叉树是否为二叉搜索树的方法,结合实例形式综合对比分析了C语言针对二叉搜索树判定的原理、算法、效率及相关实现技巧,需要的朋友可以参考下
一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树...
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
//该程序用于判断二叉树是否为二叉排序树
判别给定二叉树是否为二叉排序树
二叉树、二叉搜索树的构建,前序、中序、后序的 递归和非递归遍历;前序中序序列构建二叉树……
该程序是在VC2005下基于二叉搜索树实现的,主要功能包括查找、删除、添加、修改等基本操作,另外还有关于MFC位图显示,文件读写的操作
数据结构实验课,关于判断二叉树是不是二叉排序树》》》》》
NULL 博文链接:https://128kj.iteye.com/blog/1765663
1.实现二叉搜索树的基本操作 2.包括建立,查找,删除,显示 3.得到最长路径和最短路径,并能分别计算长度
设一棵二叉树以二叉链表表示,试编写有关二叉树的递归算法
而在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关: ①在最坏情况下,二叉排序树是通过把一个有序表的n个结点依次插入而生成的,此时所得的二叉排序树蜕化为棵深度为n的单支树,它的平均查找长度和...
用C++实现的最优二叉查找树,简单,明了,是数据结构里经典必学算法,初学者适用
常见的二叉树面试题大汇总(涵盖二叉搜索树)
/*选择二叉链式存储结构作为二叉树的存储结构,设计一个程序实现二叉树的基本操作(包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等) 【实验内容】 必做内容 程序的菜单功能项如下: 1----...
(1)键盘输入一个元素序列创建一棵二叉排序树,输出该二叉排序树的中序遍历序列; 例如,若输入 45,24,55,12,37,53,60,23,40,70 则创建的二叉排序树为: 输出结果为:12 23 24 37 40 45 53 55 60 70 (2)在(1)中...
现在大二,学数据结构,实验可写的程序,希望大家会喜欢