首页 > 花鸟鱼虫

B 树素引结构的根结点包含的指针塾可能小子，n21（向上取整）

2024-11-30 17:55:19 作者：靠谱爱好网
2024-11-30 17:55:19 作者：靠谱爱好网

B树和二叉排序树，B树和B+树的区别

一、B树的起源


B树，最早是由德国计算机科学家Rudolf Bayer等人于1972年在论文 《Organization and Maintenance of Large Ordered Indexes》提出的，不过我去看了看原文，发现作者也没有解释为什么就叫B-trees了，所以把B树的B，简单地解释为Balanced或者Binary都不是特别严谨，也许作者就是取其名字Bayer的首字母命名的也说不定啊……


二、B树长啥样


还是直接看图比较清楚，图中所示，B树事实上是一种平衡的多叉查找树，也就是说最多可以开m个叉（m>=2），我们称之为m阶b树，为了体现本博客的良心之处，不同于其他地方都能看到2阶B树，这里特意画了一棵5阶B树 。

总的来说，m阶B树满足以下条件：

  • 每个节点至多可以拥有m棵子树

  • 根节点，只有至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)

  • 非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉)

  • 非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki

  • 从根到叶子的每一条路径都有相同的长度，也就是说，叶子节在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空

    • B树的查询过程和二叉排序树比较类似，从根节点依次比较每个结点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针

    例如查询图中字母表中的K

  • 从根节点P开始，K的位置在P之前，进入左侧指针

  • 左子树中，依次比较C、F、J、M，发现K在J和M之间

  • 沿着J和M之间的指针，继续访问子树，并依次进行比较，发现第一个关键字K即为指定查找的值

    • 三、Plus版——B+树

    作为B树的加强版，B+树与B树的差异在于：

  • 有n棵子树的节点含有n个关键字（也有认为是n-1个关键字）

  • 所有的叶子节点包含了全部的关键字，及指向含这些关键字记录的指针，且叶子节点本身根据关键字自小而大顺序连接

  • 非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字

    • 请点击输入图片描述

    B+树的查找过程，与B树类似，只不过查找时，如果在非叶子节点上的关键字等于给定值，并不终止，而是继续沿着指针直到叶子节点位置。因此在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子节点的路径

一道数据结构题，请问10阶B树,根结点所包含关键字个数的最大值和最小值分别是多少，谢谢

N阶B树的非根节点的关键字个数为（上取整）[m/2]-1<=n<=m-1,10阶B树的关键字个数为[4,9],即最小是4，最大是9。根节点至少两个分支，故根节点至少有1个元素，最多有9个元素

设有ABCDEF，6个数据项，其出现的频度分别为654321，构造一棵哈夫曼树，

六个权值(频率)是654321
(1)从小到大排序123456(这是有序序列)
(2)每次提取最小的两个结点,取结点1和结点2,组成新结点N3,其权值=1+2=3,
取数值较小的结点作为左分支,1为左分支,2为右分支.
(3)将新结点N3放入有序序列,保持从小到大排序:
3N3456(注意,新结点N3要放在结点3的后面)
(4)重复步骤(2),提取最小的两个结点,结点3与N3组成新结点N6,其权值=3+3=6,
结点3与N3权值一样,但是,将结点3看成较小,所以,结点3作为左分支,N3就作为右分支.
(5)将新结点N6放入有序序列,保持从小到大排序:
456N6(注意,新结点N6要放在结点6的后面)
(6)重复步骤(2),提取最小的两个结点,结点4与结点5组成新结点N9,其权值=4+5=9,
4的数值较小,作为左分支,5就作为右分支.
(7)将新结点N9放入有序序列,保持从小到大排序:
6N6N9
(8)重复步骤(2),提取最小的两个结点,结点6与N6组成新结点N12,其权值=6+6=12,
结点6作为左分支,N6就作为右分支.
(9)将新结点N9放入有序序列,保持从小到大排序:
N9N12
(10)重复步骤(2),提取剩下的两个结点,N9与N12组成新结点N21,其权值=9+12=21,
数值较小的N9作为左分支,N12就作为右分支.
有序序列已经没有结点,最后得到"哈夫曼树":
N21
/\
N9N12
/\/\
456N6
/\
3N3
/\
12
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N21到结点6,先经历右分支,后经历左分支,结点6的编码就是10
从根结点N21到结点5,先经历左分支,后经历右分支,结点5的编码就是01
从根结点N21到结点4,先后经历两次左分支,结点4的编码就是00
从根结点N21到结点3,先经历两次右分支,最后经历左分支,结点3的编码就是110
从根结点N21到结点2,先后经历四次右分支,结点2的编码就是1111
从根结点N21到结点1,先经历三次右分支,最后经历左分支,结点1的编码就是1110
得出所有结点的"哈夫曼编码":
字符A(频率6):10
字符B(频率5):01
字符C(频率4):00
字符D(频率3):110
字符E(频率2):1111
字符F(频率1):1110
//C语言测试程序(来自其他网友)
//
//输入构造哈夫曼树中带权叶子结点数(n)：6
//输入6个整数作为权值：654321
//可以得出哈夫曼树的广义表形式,以及哈夫曼编码.
#include
#include
typedefintElemType;
structBTreeNode
{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};
//1、输出二叉树，可在前序遍历的基础上修改。
//采用广义表格式，元素类型为int
voidPrintBTree_int(structBTreeNode*BT)
{
if(BT!=NULL)
{
printf("%d",BT->data);//输出根结点的值
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintBTree_int(BT->left);//输出左子树
if(BT->right!=NULL)
printf(",");
PrintBTree_int(BT->right);//输出右子树
printf(")");
}
}
}
//2、根据数组a中n个权值建立一棵哈夫曼树，返回树根指针
structBTreeNode*CreateHuffman(ElemTypea[],intn)
{
inti,j;
structBTreeNode**b,*q;
b=malloc(n*sizeof(structBTreeNode));
//初始化b指针数组，使每个指针元素指向a数组中对应的元素结点
for(i=0;i{
b[i]=malloc(sizeof(structBTreeNode));
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i{
//k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
intk1=-1,k2;
//让k1初始指向森林中第一棵树，k2指向第二棵
for(j=0;j{
if(b[j]!=NULL&&k1==-1)
{
k1=j;
continue;
}
if(b[j]!=NULL)
{
k2=j;
break;
}
}
//从当前森林中求出最小权值树和次最小
for(j=k2;j{
if(b[j]!=NULL)
{
if(b[j]->datadata)
{
k2=k1;
k1=j;
}
elseif(b[j]->datadata)
k2=j;
}
}
//由最小权值树和次最小权值树建立一棵新树，q指向树根结点
q=malloc(sizeof(structBTreeNode));
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];
b[k1]=q;//将指向新树的指针赋给b指针数组中k1位置
b[k2]=NULL;//k2位置为空
}
free(b);//删除动态建立的数组b
returnq;//返回整个哈夫曼树的树根指针
}
//3、求哈夫曼树的带权路径长度
ElemTypeWeightPathLength(structBTreeNode*FBT,intlen)//len初始为0
{
if(FBT==NULL)//空树返回0
return0;
else
{
if(FBT->left==NULL&&FBT->right==NULL)//访问到叶子结点
{
printf("+%d*%d",FBT->data,len);
returnFBT->data*len;
}
else//访问到非叶子结点，进行递归调用，
{//返回左右子树的带权路径长度之和，len递增
returnWeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}
//4、哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）
voidHuffManCoding(structBTreeNode*FBT,intlen)//len初始值为0
{
//定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一
staticinta[10];
inti;
//访问到叶子结点时输出其保存在数组a中的0和1序列编码
if(FBT!=NULL)
{
if(FBT->left==NULL&&FBT->right==NULL)
{
printf("权值为%d的编码：",FBT->data);
for(i=0;iprintf("%d",a[i]);
printf("\n");
}
else//访问到非叶子结点时分别向左右子树递归调用，
{//并把分支上的0、1编码保存到数组a的对应元素中，
//向下深入一层时len值增1
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}
intmain()
{
intn,i;
ElemType*a;
structBTreeNode*fbt;
printf("输入构造哈夫曼树中带权叶子结点数(n)：");
while(1)
{
scanf("%d",&n);
if(n>1)
break;
else
printf("重输n值：");
}
a=malloc(n*sizeof(ElemType));
printf("输入%d个整数作为权值：",n);
for(i=0;iscanf("%d",&a[i]);
fbt=CreateHuffman(a,n);
printf("广义表形式的哈夫曼树：");
PrintBTree_int(fbt);
printf("\n");
//printf("哈夫曼树的带权路径长度：\n");
//printf("=");
//printf("\n=%d\n",WeightPathLength(fbt,0));
printf("树中每个叶子结点的哈夫曼编码：\n");
HuffManCoding(fbt,0);
return0;
}

1． 用c语言编写顺序存储结构下的顺序查找法和链式存储结构下的顺序查找法。

是啊！而且非常重要它在笔试中占30%！！！ 这是我找到的一些资料：第一章 数据结构与算法 1.1 算法 1、算法是指解题方案的准确而完整的描述。换句话说，算法是对特定问题求解步骤的一种描述。 *：算法不等于程序，也不等于计算方法。程序的编制不可能优于算法的设计。 2、算法的基本特征 （1）可行性。针对实际问题而设计的算法，执行后能够得到满意的结果。 （2）确定性。每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。 （3）有穷性。算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。 （

高分求数据结构（C语言）高手做题！（200悬赏+50追加+20采纳=270分）

1．数据结构在计算机中的表示称为数据的（ B ）。 A）存储结构 B）抽象结构 C）顺序结构 D）逻辑结构 12．在下列序列中，不是线性表的是（ D ）。 A）('a','b','c') B）('AB','CD') C）('a',true,'c') D）(a,b,c,d) 13．线性链表中各链结点之间的地址（ D ）。 A）必须连续 B）部分地址必须连续 C）不一定连续 D）连续与否无所谓 14．如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则（ D ）存储方式最节省运行时间。 A）单链表 B）带头结点的单链表 C）单循环链表 D）带头结点的双循环链表 26．从一个具

文章标签：理工学科信息技术编程编程语言学习

相关文章