排序二叉树二叉排序树的操作

排序二叉树  时间:2021-09-12  阅读:()

二叉排序树的构造和查找方法

二叉排序树的构造过程:按照给定序列,以此将结点插入二叉排序树中,在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义。

  插入过程:若二叉排序树为空,则待插入结点*S作为根结点插入到空树中;   当非空时,将待插结点关键字S->key和树根关键字t->key进行比较,   若s->key = t->key,则无须插入,若s->key< t->key,则插入到根的左子树中,   若s->key> t->key,则插入到根的右子树中。

而子树中的插入过程和在树中的插入过程相同,   如此进行下去,直到把结点*s作为一个新的树叶插入到二叉排序树中,或者直到发现树已有相同关键字的结点为止。

  说明:   ① 每次插入的新结点都是二叉排序树上新的叶子结点。

  ② 由不同顺序的关键字序列,会得到不同二叉排序树。

  ③ 对于一个任意的关键字序列构造一棵二叉排序树,其实质上对关键字进行排序。

查找的过程类似,从根结点开始进行比较,小于根结点的在左子树上,大于根结点的在右子树上,以此查找下去,直到查找成功或不成功(比较到叶子结点)。

100。120。110。130。80。60。90。构造二叉排序树

构造二叉排序树时遵照定义即可: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树; 则该树应为 100 ╱ ╲ 80 120 ╱ ╲ ╱ ╲ 60 90 110 130

二叉排序树

二叉排序树 目录[隐藏] 二叉排序树 二叉排序树的查找 二叉排序树的插入和删除 插入算法 [编辑本段]二叉排序树 二叉排序树(Binary Sort Tree)又称二叉查找树。

它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树; [编辑本段]二叉排序树的查找 步骤:若根结点的关键字值等于查找的关键字,成功。

否则,若小于根结点的关键字值,递归查左子树。

若大于根结点的关键字值,递归查右子树。

若子树为空,查找不成功。

[编辑本段]二叉排序树的插入和删除 与次优二叉树相对,二叉排序树是一种动态树表。

其特点是:树的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的节点时再进行插入。

新插入的结点一定是一个新添加的叶子节点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

[编辑本段]插入算法 首先执行查找算法,找出被插结点的父亲结点。

判断被插结点是其父亲结点的左、右儿子。

将被插结点作为叶子结点插入。

若二叉树为空。

则首先单独生成根结点。

注意:新插入的结点总是叶子结点。

//在二叉排序树中插入查找关键字key void InsertBST(t,key) { if(t==NULL) { t=new BiTree; t->lchild=t->rchild=NULL; t->data=key; return; } if(key<t->data ) InsertBST(t->lchild,key); else InsertBST (t->rchild, key ); } //n个数据在数组d中,tree为二叉排序树根 void CreateBiTree(tree,d[ ],n) { tree=NULL; for(i=0;i<n;i++) InsertBST(tree,d); } 最小值二叉树c例程: #include<stdio.h> struct priorityqueue { int capacity; int size; int *elements; }*tryit; struct priorityqueue *initialize ( int maxelements ) { struct priorityqueue *h; h = malloc ( sizeof ( struct priorityqueue ) ); h -> elements = malloc ( sizeof ( int ) * ( maxelements + 1 ) ); h -> capacity = maxelements; h -> size = 0; h -> elements[0] = -23767; return h; } void insert ( int x , struct priorityqueue *h ) { int i; for ( i = ++h -> size ; h -> elements[ i / 2 ] > x ; i /= 2 ) h -> elements[ i ] = h -> elements[ i / 2 ]; h -> elements [ i ] = x; } int deletemin ( struct priorityqueue *h ) { int i , child ; int minelement , lastelement; minelement = h -> elements[ 1 ]; lastelement = h -> elements[ h -> size-- ]; for ( i = 1 ; i * 2 <= h -> size ; i = child ) { child = i * 2; if ( child != h -> size && h -> elements[ child + 1 ] < h -> elements[ child ] ) child++; if ( lastelement > h -> elements[ child ] ) h -> elements[ i ] = h -> elements[ child ]; else break; } h -> elements[ i ] = lastelement; return minelement; } main() { tryit = initialize ( 10 ); insert ( 4 , tryit ); insert ( 5 , tryit ); insert ( 10 , tryit ); insert ( 3 , tryit ); printf ( "%d " , deletemin ( tryit ) ); printf ( "%d " , deletemin ( tryit ) ); printf ( "%d " , deletemin ( tryit ) ); printf ( "%d " , deletemin ( tryit ) ); getch(); }

二叉排序树的操作

实验目的】 由读入数据构造二叉排序树,并进行插入,查找,删除操作。

【设计原理】 二叉排序树:或者是一棵空树,或者是具有下列性质的二叉树: 1. 若它的左子树不空,则右子树上所有结点的值均大于它的根结点的值 2. 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值 3. 它的左,右子树也分别为二叉排序树 【算法描述】 查找:以二叉链表为存储结构,二叉排序树不空时,首先将给定值和根结点的关键字比较,若相等,则查找成功,否则按大小关系,分别在左,右子树上继续查找。

插入:在查找过程中,当树中不存在关键字等于定值的结点时再进行插入。

插入的是在叶子结点。

删除:1.若待删结点为叶子结点,即删去该结点。

2.若待删结点只有左或右子树,即将该子树直接连到待删结点的双亲的对应子树。

4. .若待删结点左右子树都不空,则将它中序遍历的直接前驱替代它,再删去这个前驱结点。

【程序清单】 #include <stdio.h> #include <conio.h> #define NULL 0 #define MAX 20 struct node {int data; struct node *r,*l; }*head,*inord[MAX]; int count=0; int n=0; myprint(int x,int y,char *s,int tc,int bc) { gotoxy(x,y); textcolor(tc); textbackground(bc); cprintf(s);

CloudCone月付$48,MC机房可小时付费

CloudCone商家在前面的文章中也有多次介绍,他们家的VPS主机还是蛮有特点的,和我们熟悉的DO、Linode、VuLTR商家很相似可以采用小时时间计费,如果我们不满意且不需要可以删除机器,这样就不扣费,如果希望用的时候再开通。唯独比较吐槽的就是他们家的产品太过于单一,一来是只有云服务器,而且是机房就唯一的MC机房。CloudCone 这次四周年促销活动期间,商家有新增独立服务器业务。同样的C...

野草云提供适合入门建站香港云服务器 年付138元起 3M带宽 2GB内存

野草云服务商在前面的文章中也有多次提到,算是一个国内的小众服务商。促销活动也不是很多,比较专注个人云服务用户业务,之前和站长聊到不少网友选择他们家是用来做网站的。这不看到商家有提供香港云服务器的优惠促销,可选CN2、BGP线路、支持Linux与windows系统,支持故障自动迁移,使用NVMe优化的Ceph集群存储,比较适合建站用户选择使用,最低年付138元 。野草云(原野草主机),公司成立于20...

BuyVM新设立的迈阿密机房速度怎么样?简单的测评速度性能

BuyVM商家算是一家比较老牌的海外主机商,公司设立在加拿大,曾经是低价便宜VPS主机的代表,目前为止有提供纽约、拉斯维加斯、卢森堡机房,以及新增加的美国迈阿密机房。如果我们有需要选择BuyVM商家的机器需要注意的是注册信息的时候一定要规范,否则很容易出现欺诈订单,甚至你开通后都有可能被禁止账户,也是这个原因,曾经被很多人吐槽的。这里我们简单的对于BuyVM商家新增加的迈阿密机房进行简单的测评。如...

排序二叉树为你推荐
阿里校园招聘阿里巴巴校园招聘内推有什么优势java队列java中的队列都有哪些,有什么区别?体系文件企业质量管理体系文件指的是什么?a8处理器什么是A8处理器?什么是cookie电脑中cookie是什么意思?小项目奥运会一共有几个大项目小项目?t320华为T320怎么样硬盘分区格式化新硬盘分区格式化有哪些方法?硬盘分区格式化怎样给硬盘分区并格式化sd卡座sd卡座使用过程中需注意哪些事项
网站空间商 域名城 tk域名注册 qq空间域名 cn域名个人注册 ftp空间 sub-process 国外代理服务器地址 qq对话框 美国在线代理服务器 太原网通测速平台 yundun 华为k3 杭州电信宽带优惠 阿里云邮箱申请 云销售系统 广州主机托管 电信主机托管 hdchina 贵州电信 更多