4.5.1 二叉排序树

1、二叉排序树的定义

左子树结点值<根结点值<右子树结点值

2、二叉排序树的查找

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的关键字大于给定关键字时,在根结点的左子树中查找,否则在根结点的右子树中查找。

二叉排序树的非递归查找算法:

BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p){
//查找函数返回指向关键字为key的结点指针,若不存在,则返回NULL
	p=NULL;//p指向被查找结点的双亲,用于以后的插入和删除操作
	while(T!=null&&key!=T->data){
		p=T;
		if(key<T->data)
			T=T->lchild;
		else
			T=T->Rchild;
	}
	return T;
}

二叉排序树的递归查找算法:

BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p){
//查找函数返回指向关键字为key的结点指针,若不存在,则返回NULL
<pre name="code" class="cpp">        p=NULL;//p指向被查找结点的双亲,用于以后的插入和删除操作

  if(key==T->data){return T;}

        p=T;

  if(key<T->data)BST_Search(T->Lchild);elseBST_Search(T->Rchild);}

3、二叉排序树的插入

二叉排序树作为一种动态集合,其特点是树的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的结点时再进行插入。

由于二叉排序树是递归定义的,插入结点的过程是,若原二叉排序树为空,则直接插入结点,否则,若关键字k小于根结点关键字,则插入到左子树中,若关键字K大于根结点关键字,则插入到右子树中。

int BST_insert(BiTree &T,keyType k){
//在二叉排序树T中插入一个关键字为k的结点
	if(T==null){//原树为空,新插入的记录为根结点
		T=(BiTree)malloc(sizeof(BSTNode));
		T->key=k;
		T->lchild=T->rchild=null;
		return 1;//返回1,表示成功
	}
	else if(k==T->key)//树中存在相同关键字的结点
		return 0;
	else if(k<T->key)//插入到T的左子树中
		return BST_insert(T->lchild,k);
	else
		return BST_insert(T->rchild,k);
}

4.二叉排序树的构造

构造一棵二叉排序树就是依次输入数据元素,并将它们插入二叉排序树中的适当位置上的过程。

具体过程是,每读入一个元素就建立一个新结点,若二叉排序树非空,则将新结点的值与根结点的值比较,如果小于根结点的值,则插入到左子树,否则插入到右子树;若二叉排序为空,则新结点作为二叉排序树的根结点。

void create_BST(BiTree &T,KeyType Str[],int n){
//用关键字数组str[]建立一个二叉排序树
	T=null;//初始时bt为空树
	int i=0;
	while (i<n){//依次将每个元素插入
		BST_insert(T,str[i]);
		i++;
	}
}

5、二叉排序树的删除

在二叉排序树中删除一个结点时,不能把以该结点为根的子树的结点都删除,必须先把被删除结点从存储二叉排序树的链表上摘下来,将因删除结点而断开的二叉链表重新链接起来,同时确保二叉排序树的性子不会丢失。

①如果被删除结点Z是叶结点,则直接删除,不会破坏二叉排序树的性质。

②若结点Z只有一棵左子树或右子树,则让z的子树成为z父结点的子树,代替z的位置。

③若结点z有左、右两棵子树,则令z的直接后继(或直接前驱)代替Z,然后从二叉排序树中删除这个直接后继(或直接前驱),这样就转化成第一种或第二种情况。

6、二叉排序树的查找效率分析

对于高度为H的二叉树,其插入和删除操作的运行时间都是O(H),但在最坏的情况下,即构造二叉排序树的输入序列是有序的,则会形成一个倾斜的单支树,此时二叉排序树的性能显著变坏,树的高度也增加为元素个数N。

二叉排序树查找算法的平均查找长度,主要取决于树的高度,即与二叉树的形态相关。如果二叉排序树是一个只有右(左)孩子的单支树(类似于有序的单链表),其平均查找长度和单链表相同,为O(n).如果二叉排序树的左、右子树的高度之差的绝对值不超过1,这样的二叉排序称为平衡二叉树,它的平均查找长度达到O(log2 N)。

从查找过程看,二叉排序树与二分查找相似。就平均时间性能而言,二叉排序树的上的查找和二叉查找差不多。但二分查找的判定树唯一,二叉排序树不唯一,相同的关键字其插入顺序不同可能生成不同的二叉排序树。

就维护表的有序性而言,二叉排序树无须移动结点,只需修改指针即可完成插入和删除操作,平均执行时间为O(log2 n)。

二分查找的对象是有序顺序表,若有插入和删除结点的操作,所花的代价是O(n)。

当有序表是静态查找表时,宜用顺序表作为其存储结构,而采用二分查找实现其查找操作。

若有序表是动态查找表时,则应选择二叉排序树作为其逻辑结构。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏趣学算法

数据结构 第4讲 单链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位...

983
来自专栏cmazxiaoma的架构师之路

Java数据结构和算法(1)--自定义一个数组类和动态数组类

1534
来自专栏xingoo, 一个梦想做发明家的程序员

B树 B-树 B+树 B*树

B树 即二叉搜索树:        1.所有非叶子结点至多拥有两个儿子(Left和Right);        2.所有结点存储一个关键字;        3...

1977
来自专栏ACM算法日常

二叉搜索树(BST)- HDU 3791

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sor...

1121
来自专栏拭心的安卓进阶之路

Java 集合深入理解(7):ArrayList

今天心情有点美丽,学学 ArrayList 放松下吧! 什么是 ArrayList ? ? ArrayList 是 Java 集合框架中 List接口 的一个实...

2177
来自专栏Java呓语

迭代器模式(控制访问集合中的元素)

现在我们需要思索,JDK是怎么做到这一切的?现在让我们先利用迭代器实现一个数组类型Array,这个类型需要支持添加、移除、遍历操作。

992
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

1432
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——ArrayList

27712
来自专栏Java后端技术

一道面试题引发的思考

为什么呢?那么我们怎么来发现它背后的秘密呢?答案只有一个:那就是通过源码来解惑(ArrayList部分源码)。

660
来自专栏JavaQ

源码阅读之ArrayList

源码阅读是基于JDK7,本篇主要涉及ArrayList常用方法源码分析。 1.概述 ArrayList是List接口的可调整大小的数组实现,可以包含任何类型的元...

3364

扫码关注云+社区