动态查找表
动态查找表除了支持查找操作,还支持插入、删除等改变表中数据的操作。
动态查找表的表结构是在查找过程中动态生成的,即对于给定的key值,若表中存在其关键字等于key的记录,则查找成功;否则插入关键字等于key的记录。
为了方便插入和删除操作,通常采用链表、树等存储结构来表示动态查找表。
1.1 二叉排序树(binary sort tree,BST)是一棵空树,或满足如下性质的二叉树:
(1) 若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
(2) 若它的右子树非空,则右子树上所有结点的值均大于根结点的值;
(3) 左右子树本身也分别是一棵二叉树。
由二叉树的性质可得知:
(1) 二叉排序树中任一结点x,其左子树中任一结点y的关键字必小于x的关键字,右子树亦然;
(2) 二叉排序树中,各结点关键字是唯一的;
(3) 按中序遍历该树得到的中序序列是一个递增有序序列。
二叉排序树的运算包括插入、删除、生成和查找等,因此常用二叉链表作为二叉排序树的存储结构,定义如下:
typedef int keytype;
typedef struct node{
keytype key;
struct node *lchild,*rchild;//左右子树指针
}BSTNode;
typedef BSTNode *BSTree;//定义二叉排序树类型的指针
a) 二叉排序树的插入
在二叉排序树中插入新结点,要保证插入后仍满足BST的性质,过程如下:
(1) 若二叉排序树T为空,则为待插入的关键字key申请一个新结点,并令其为根;
(2) 若二叉排序树T不为空,则将key和根的关键字比较;
(3) 若两者相等,则说明树中已有此关键字key,无需插入;
(4) 若key<T->key,则将key插入到根的左子树;
(5) 若key>T->key,则将key插入到根的右子树。
算法描述如下:
void insertBST(BSTree *bst,keytype key){
//若二叉排序树*bst中没有关键字为key,则插入
BSTNode *p = *bst;
while(p){
if(p->key == key) return;//已存在,不需要插入
p = (key < p->key) ? p->lchild:p->rchild;
//在左右子树中查找
}
BSTNode *f = (BSTNode *)malloc(sizeof(BSTNode));//新分配一个结点空间
//生成新结点f
f->key = key;
f->lchild = f->rchild = NULL;
if(*bst == NULL) *bst = f;//原树为空
else
if(key<p->key) p->lchild = f;
else p->rchild = f;
}//insertBST
b) 二叉排序树的生成
BSTree createBST(){
//输入一个结点序列,建立一棵二叉排序树,将根结点指针返回
BSTree T = NULL;
keytype key;
scanf("%d",&key);
while(key != '0'){
insertBST(&T,key);
scanf("%d",&key);//读入下一个关键字
}
return T;
}
c) 二叉排序树的删除
在二叉排序树中删除一个结点时,必须将因删除而断开的二叉链表重新连接起来,同时保持二叉排序树的性质不变。
假设二叉排序树上被删除结点为*p,其父节点为*parent,可设p是parent的左指针。
可分下面3中情况讨论:
(1) 若*p结点为叶子结点,只需要将*parent中指向*p的指针域置为NULL即可;
(2) 若*p结点只有左子树或右子树,只需要将*p的左或右子树直接连接到*parent即可。
(3) 若*p结点的左右子树均不空,中序遍历该树,得到*p的直接后继是*s,*s结点是*p结点的右子树的最左下的结点,且*s结点无左子树,降被删除的结点*p用*s代替,同时将*s结点的右子树作为*s结点的父结点的左子树。
程序描述如下:
void delBSTNode(BSTree *bst,keytype key){
if(!bst) return;//如果二叉排序树为空,则直接返回
BSTNode *parent = NULL,*p = *bst,*child,*s;
while(p){//从根开始查找关键字为key的待删结点
if(p->key == key) break;//找到,跳出循环
parent = p;//父结点为*p的双亲
p = (key < p->key) ? p->lchild : p->rchild;
}
if(!p) return; //找不到待删记录,返回
if(!parent){//只有一个根节点,删除之后就什么都没了
bst = NULL;
}
//处理情况1,*p为叶子结点,修改*p的父结点*parent指向*p的指针域为空即可
if(!p->lchild && !p->rchild){
child = parent->lchild ? parent - >lchild : parent ->rchild;
child = NULL;
}
//处理情况2,*p只有左子树或右子树,只需要将左子树或右子树与parent直接关联即可
if(!p->lchild || !p->rchild){
child = parent->lchild ? parent - >lchild : parent ->rchild;
child = p->lchild ? p->lchild : p->rchild;
}
//处理情况3,*p有左右子树,需要找到*p右子树的最左下结点*s,p被s代替,且s的右子树为s父结点的左子树
if(p->lchild && p-> rchild){
parent = p;
s = p->rchild;
while(!s->lchild){
parent = s;
s = s->lchild;
}
p->key = s->key;//替换数据,这样就不用替换其他关系了
parent->lchild = s->rchild;//s的右子树为s父结点的左子树
p = s;
}
free(p);
}
d) 二叉排序树的查找
过程如下:
(1) 从根结点开始,沿某一个分支逐层向下比较判断,相等,则成功返回。
(2) 若查找值小于根节点的值,从根节点的左子树查找,否则,从右子树查找。
(3) 若查找到最后,左子树或右子树为空,则查询失败。
算法描述如下:
BSTNode *searchBST(BSTree *bst,keytype key){
if(bst == NULL || bst->key == key){//递归查询终止条件
return bst;//bst为空,则查找失败,成功则返回结点位置
}
return key < bst->key?searchBST(T->lchild,key) : searchBST(T->rchild,key)
}
e) 二叉排序树的查找分析
二叉排序树查找时,与关键字比较的次数不超过树的深度。
查找时的平均查找长度与二叉排序树的形态有关。
最坏的情况为n个关键字已基本有序,得到一个深度为n的单枝树,此时平均查找长度为(n+1)/2。
最好的情况,二叉排序树左右形态比较平衡,其平均查找长度为[log(2)n]+1
分享到:
相关推荐
【二叉排序树与文件操作】 功能要求: (1)从键盘输入一组学生记录建立二叉排序树; (2)二叉排序树存盘; (3)由文件恢复内存的二叉排序树; (4)中序遍历二叉排序树; (5)求二叉排序树深度; (6)求二叉...
二叉排序树的实现 二叉排序补充概念(也可以参考书上第九章第二节) 左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,简单一点,二叉排序树左边的数据小于右边. 1)编程实现二叉排序树, 包括生成、...
二叉排序树C语言的简单实现,包含如下操作: 1.创建二叉排序树; 2.销毁二叉排序树; 3.清空二叉排序树; 4.插入指点结点至二叉排序树; 5.删除二叉排序树指点结点; 5.获取二叉排序树指定结点; 6.获取二叉排序树根...
代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树,二叉排序树查找递归算法,二叉排序树查找非递归算法
1.构造一棵二叉排序树并对其进行中序遍历输出;2.在二叉排序树中查找某一关键字,若存在,显示查找成功;若不存在,将其插入到二叉排序树中,再中序遍历输出。
一、实验目的 (1)理解动态查找表的动态生成过程; (2)任意给出一组数(不少于10个),建立对应二叉排序树;...(2)实现二叉排序树的插入算法与查找算法,并建立二叉排序树; (3)进行数据查找和建树过程的比较。
用二叉链表作存储结构,编写程序实现二叉排序树上的基本操作:以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T......
二叉排序树实现的学生管理 有创建插入 删除 查找等功能
二叉排序树插入
第一个程序:实现将两个二叉排序树合并为一个二叉排序树的算法; 第二个程序:N个人围成一圈,从第一个人开始计数,凡是数到1,2,4,8,也就是2的N次方的退出圈子。编写程序,把这些人退出的顺序输出,要求用链表。
采用llink-rlink方式存储二叉排序树,编写能够通过键盘输入建立二叉排序树,并在建立完立即在屏幕显示中序遍历结果的程序
ios编程:实现二叉排序树增删改查。 开发环境:windows下codeblocks。
1.2.1编程实现二叉排序树,包括生成、插入,删除; 1.2.2对二叉排序树进行先根、中根、和后根非递归遍历; 1.2.3每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 1.2.4分别用二叉排序树...
(1)以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T; (2)对二叉排序树T作中序遍历,输出结果; (3)计算二叉排序树T查找成功的平均查找长度,输出结果; 2.用顺序表(一维数组)作存储结构 (1)以回车...
二叉排序树。用二叉链表作存储结构。 要求: (1)以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T; (2)对二叉排序树T作中序遍历,输出结果; (3)计算二叉排序树T查找成功的平均查找长度,输出结果; (4)...
掌握二叉排序树的存储方法,实现二叉排序树的创建、查找、插入、删除、平均查找长度等基本操作。 三、实验内容及要求 1、构造二叉排序树的存储结构。 2、实现创建、查找、插入、删除、平均查找长度等操作。
设二叉排序树的二叉链表存储结构的类型定义如下: typedef struct node{ int data; //用整数表示一个结点的名 struct node *LChild,*RChild; //左右指针域 }BSTNode,*BSTree; 设计算法并编写程序求解以下几个问题...
二叉排序树的建立 搜索 插入 删除 遍历 等功能的实现 希望对你有所帮助