中文名称 | 二叉排序树 | 外文名称 | BiNARy Sort Tree |
---|---|---|---|
别 称 | 二叉查找树、二叉搜索树 | 别称外文名 | Binary Search Tree |
若根结点的关键字值等于查找的关键字,成功。
否则,若小于根结点的关键字值,递归查左子树。
若大于根结点的关键字值,递归查右子树。
若子树为空,查找不成功。
插入算法:
首先执行查找算法,找出被插结点的父亲结点。
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
若二叉树为空。则首先单独生成根结点。
注意:新插入的结点总是叶子结点。
void InsertBST(t,key)
//在二叉排序树中插入查找关键字key
{
if(t==NULL){
t=new BiTree;
t->lchild=t->rchild=NULL;
t->data=key;
return; }
if(keydata ) InsertBST(t->lchild,key);
else InsertBST (t->rchild, key );
}
void CreatEBITree(tree,d【 】,n)
//n个数据在数组d中,tree为二叉排序树根
{tree=NULL;
for(i=0;i InsertBST(tree,d);
}
市场价 | 信息价 | 询价 |
如何排序
击【分部整理】,会显示下方窗口,如图一: 钩选分部规则后点击“执行分部整理”即可。 点击【分部整理】,会显示下方窗口,如图二: 点击“执行子目排序”即可
如何排序
使用08定额,建筑与装饰最好分开(分两个预算)做,就不会出现借用定额的代号了,直接点分部整理即可排序,如果不想分为两个预算,装饰部分可以按鼠标右键插入分部输入编号、分部名称,然后将该分部的子目用上下移...
树和二叉树的基本知识?
二叉树在计算机科学中,二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用作二叉查找树和二叉堆。二叉...
按子类型排序是按什么排序m
你是说的定义构件中的构件排序吧,具体子类型是什么也搞不清,但排序最好是选择【按子类型和名称】排序最适当,我试过其它排序,混乱、不好使。
如何轴号排序
左右开间不一致 轴号顺序不一样 软件的自动排序功能排出来的轴号 不正确 该如何处理(问题如图) ——:可以手动修改的
1.二叉排序树的概念:
二叉排序树是一种动态树表。
二叉排序树的定义:二叉排序树或者是一棵空树,
或者是一棵具有如下性质的二叉树:
⑴ 若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
⑵ 若它的右子树非空,则右子树上所有结点的值均大于根结点的值;
⑶ 左、右子树本身又各是一棵二叉排序树。二叉排序树的性质: 按中序遍历二叉排序树,所得到的中序遍历序列是一个递增有序序列。
2.二叉排序树的插入:
在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义。
插入过程:若二叉排序树为空,则待插入结点*S作为根结点插入到空树中;
当非空时,将待插结点关键字S->key和树根关键字t->key进行比较,
若s->key = t->key,则无须插入,若s->key< t->key,则插入到根的左子树中,
若s->key> t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同,
如此进行下去,直到把结点*s作为一个新的树叶插入到二叉排序树中,或者直到发现树已有相同关键字的结点为止。
3. 二叉排序树生成:
从空的二叉排序树开始,经过一系列的查找插入操作以后,生成了一棵二叉排序树。
说明:
① 每次插入的新结点都是二叉排序树上新的叶子结点。
② 由不同顺序的关键字序列,会得到不同二叉排序树。
③ 对于一个任意的关键字序列构造一棵二叉排序树,其实质上对关键字进行排序。
4.二叉排序树查找的程序实现:
5. 二叉排序树的删除:
假设被删结点是*p,其双亲是*f,不失一般性,设*p是*f的左孩子,下面分三种情况讨论:
⑴ 若结点*p是叶子结点,则只需修改其双亲结点*f的指针即可。
⑵ 若结点*p只有左子树PL或者只有右子树PR,则只要使PL或PR 成为其双亲结点的左子树即可。
⑶ 若结点*p的左、右子树均非空,先找到*p的中序前趋结点*s(注意*s是*p的左子树中的最右下的结点,它的右链域为空),然后有两种做法:
① 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。
② 以*p的中序前趋结点*s代替*p(即把*s的数据复制到*p中),将*s的左子树链到*s的双亲结点*q的左(或右)链上。
6. 删除算法演示 :
7. 二叉排序树的查找:
在二叉排序树中进行查找的过程和二分查找类似,也是一个逐步缩小查找范围的过程。若查找成功,则是走了一条从根结点到待查结点的路径;若查找失败,则是走了一条根结点到某个叶子结点的路径。因此,查找过程中和关键字比较的次数不超过树的深度。
由于含有n个结点的二叉排序树不唯一,形态和深度可能不同。故含有n个结点的二叉排序树的平均查找长度和树的形态有关。
最好的情况是: 二叉排序树和二叉判定树形态相同。
最坏的情况是: 二叉排序树为单支树,这时的平均查找长度和顺序查找时相同。
最坏情况示例
就平均性能而言,
二叉排序树上的查找和二分查找相差不大,并且二叉排序树上的插入和删除结点十分方便,无须大量移动结点。
二叉排序树查找
二叉排序树的查找算法
当用线性表作为表的组织形式时,可以有3种查找算法,其中以二分查找效率最高,但由于二分查找要求表中结点按关键字有序,且不能用链表作存储结构,因此当表的插入或删除操作频繁时,为维护表的有序性,势必要移动表中很多结点。这种由移动结点引起的额外时间开销、就会抵消二分查找的优点。也就是说,二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找,可采用下面介绍的几种特殊的二叉树或树作为表的组织形式。不妨将它们统称为树表。下面将分别讲解在这些树表上进行查找和修改操作的方法。
扫码下载
免费看价格