关于程序员:B树

拜访【WRITE-BUG 数字空间】_[内附残缺源码和文档]

数据结构试验的实验报告 –B 树

环境及工具
环境：C

工具：AnyivewCL

B 定义
一棵 m 阶 B 树(Balance Tree of order m), 或为空树, 或满足下列的个性的 m 叉树：(本次试验采纳链式存储构造)

(1)树中每个结点最多含有 m 棵子树。

(2)若根结点是非终端结点, 则至多有 2 棵子树

(3)除根结点之外的所有非终端结点至多有「m/2 棵子树。

(4)每个非终端结点中蕴含信息:(n,A,K1,A1,K2,A2,…,Kn,An)。其中：

①K(1≤i≤n)为关键字, 且关键字按升序推入指针。

②A(0≤≤n)指向子树的根结点,A(i-1)指向子树中所有结点的关键字均小于 Ki，且大于 K(i-1）。

③ 关键字的个数 n 必须满足「m/2-1≤n≤m-1。

(5)所有叶子结点都呈现在同一层, 叶子结点不蕴含任何信息(能够看作是内部结点或查找失败的结点, 实际上这些结点不存在, 指向这些结点的指针为空。实际上,B 树的结点还应蕴含 n 个指向每个关键字相应记录的指针。这与利用相干, 从略。

存储构造定义和宏定义

define M 4 // B 树的阶，本次试验设置为 4 # define MAX M – 1 // 每个节点存储的最多关键字的数目 # define MIN M/2 // 每个节点存储的起码关键字的数目 # define N 14 // 选取 14 个关键字的树作为例子 # define ERROR 0 # define SUCCESS 1 # define TRUE 1 # define UNSUCCESS 0 # define OVERFLOW -1 # define FALSE -1 typedef int Status; typedef int KeyType;// 关键字类型为整形 typedef struct BTNode {int keynum; // 以后节点的关键字数目 KeyType key[M + 1]; // 关键字数组，key[0]未用 struct BTNode parent; // 双亲结点指针 struct BTNode ptr[M + 1]; // 孩子节点指针数组 //Record recptr[M + 1]; // 记录指针向量，0 号单元未用 } BTNode, BTree; // B 树的节点及指针类型 // B 树查找的后果类型 typedef struct {int tag; //1：查找胜利，0：查找失败 BTree pt; // 指向找到的后果类型 int index; //1 <= index <= M 在节点中的关键字位序} Result;