1.题目

从空树出发构造一颗深度至少为 3（不包括失误结点）的 3 阶 B-树（又称 2-3 树）并可以随时进行查找、插入、删除等操作。

要求：能够把构造和删除过程中的 B-树随时显示输出来，能给出查找是否成功的有关信息。

2.软件功能

本软件作为数据结构中“B-树”的实现和演示软件，做到以下功能：

在软件运行时内部维护一个“B-树”的数据结构，可以对其进行增加、修改、删除结点的操作，并在程序运行完成后自行释放
软件应实现一个 GUI（Graphic User Interface，图形用户界面）能够适时显示 B-树经过改动后的结构
软件的 GUI 应提供给用户对于 B-树进行上述操作的接口（按钮、文本框），以便用户输入。用户通过输入给出指令后，软件应执行用户的指令，并在对 B-树修改后给出显示反馈

3.设计思想

本软件的体系结构为 MVC（Model-View-Controller）式，具体分“图形用户界面”和 “内部数据结构和算法”两部分。

3.1 图形用户界面的设计思想

图形用户界面包括 Model 和 Controller 的部分。

由于本软件基于 Qt 平台，因此可以利用 Qt 提供的图形用户界面库中的类（QWidget 等）来实现图形界面。

本软件设计时优先考虑 Microsoft Windows 等 PC 平台，故 GUI 的设计是窗口式的。 GUI 包括：

提供给用户的指令按钮
指令配套的参数的输入框
实时显示树结构的显示区域

在 Qt Creator 中设计的 GUI 窗体如下图所示。

对于 B-树的打印，由于显示空间有限而树的构造可以无限，故不采用直接的图形来打印 B-树。Qt 提供了一个名叫 QTreeView 的控件，能以类 Windows 下文件目录结构的方式展示树结构的内容，具有层次性强、延展性强、易于实现的特点，故采用 QTreeView 来显示树。

3.2 数据结构和算法的设计思想

本软件只涉及 B-树这一种数据结构。在 B-树上，有“添加键值”、“删除键值”、“查找键值”三个算法。其中，添加键值算法用到了结点分裂算法、删除键值算法用到了结点合并以及关键字不足的结点的补全算法。它们均为纯粹基于 B-树的算法。

除此之外，为使 GUI 能打印该 B-树，另有一个将 B-树映射为 QTreeView 下具有层次的 QStandardItem(Model)对象的显示算法。

4.逻辑结构与物理结构

4.1 逻辑结构

B-树为多路平衡查找树，与二叉搜索树的不同在于：

它是多路的，这要求它是多叉树（最大分支数取决于阶）且它每两个分叉之间需要有一个搜索键值用来定位。故 n+1 叉结点存 n 个键值
它的空间利用率相比较低，因为每个结点的分支数不一定达到阶（最大分支数）m，其可能值在 m/2 + 1 和 m 之间（根节点不受最小值限制）
结点和关键字在每次插入后会进行调整，以保持每个叶节点等深

以硬盘存储中使用的 B-树结构为例，逻辑结构图如下：

4.2 物理结构

B-树数据结构涉及 BTree 类（一棵树的整体）以及 BTreeNode 类（树中的结点）。为方便内存管理，它们全都继承 Qt 提供的标准 QObject 类。它在纯 C++类之上，添加了父/ 子对象关系设置的功能以便内存管理、信号/槽的实现以便异步调用。这样，数据结构类便能继承这些优点。

BTree 类的定义包括 B-树的阶数 m，和一个 BTreeNode *指针，用于指向树的哨兵结点（sentinel），该哨兵结点的唯一孩子为 B-树的根。亦即，BTree 对象只包括一个整数成员变量和一个指针成员变量，BTreeNode 对象与 BTree 对象分开、分散放置在内存中。

BTreeNode 对象存有该节点的键值数 n，以及键值的列表和子结点的列表。这两个列表均用 Qt 提供的 QList\<Element>模板类实现。这个模板类实现时，将在内存的另一处维护一个顺序表，存储键值或子节点。键值数 n 为整数 qint32 类型，键值采用可比较的 QVariant 类型，可以作为 int、double 等类型的任何一种。子结点则为指向其他 BTreeNode 的 BTreeNode *指针。当该 BTreeNode 为叶节点时，所有的子结点皆为空（nullptr）。

这两个类的头文件（列出了成员变量和成员函数）：

class BTree : public QObject
{
    Q_OBJECT
public:
    // 显式构造函数
    explicit BTree(QObject *parent, qint32 m);
    // 哨兵结点
    BTreeNode *sentinel;
    // 阶
    qint32 m;
    // 获取该树的根结点
    BTreeNode *root();
    const BTreeNode *croot() const;
    // 树中搜索
    const QVector<QVariant> search(const QVariant &x);
    // 树中添加键值
    bool add(const QVariant &x);
    // 树中删除键值
    bool del(const QVariant &x);
signals:
    // 信号函数，当树的内容更新时会释放该信号
    void updated();
public slots:
};

class BTreeNode : public QObject
{
    Q_OBJECT
private:
    // 拆分结点的算法
    static void split(BTreeNode *toBeSplitted, qint32 m);
    // 在叶结点删除一个键值
    void delAtLeaf(qint32 m, qint32 searchIndex);
    // 处理结点缺少足够的键值的算法
    static void dealWithKeywordShortage(BTreeNode *me, qint32 m, qint32 keyWordBackup);
    // 插入键值的算法
    bool insertKey(const QVariant *x, BTreeNode *childNodeLeft, BTreeNode *childNodeRight, qint32 m, qint32 searchIndex = -1);
    // 获取父结点
    BTreeNode *parentNode();
    // 根据键值在本结点的索引来删除键值的算法
    void delByIndex(qint32 m, qint32 searchIndex);
public:
    // 显式的构造函数
    explicit BTreeNode(QObject *parentNode = nullptr);
    // 结点的键值数，等于 keyWords 的长度
    qint32 n;
    // 键值表
    QList<QVariant> keyWords;
    // 子结点表
    QList<BTreeNode *> childNodes;
    // 在以该结点为根的子树中查找
    const QVector<QVariant> search(const QVariant *x);
    // 在以该结点为根的子树中添加键值
    bool add(const QVariant *x, qint32 m);
    // 在以该结点为根的子树中删除键值
    bool del(const QVariant *x, qint32 m);
signals:
public slots:
};