Question

B_Tree.h

#include <iostream>
using namespace std;

#define N 10
int t = 2;
//B 树结点结构
struct node
{
  int n;//当前存储在结点 x 中的关键字数
  char key[N];//n 个关键字，以非降序存放
  bool leaf;//TRUE:x 是叶子；FALSE:x 是内结点
  node *child[N+1];//指向其 n+1 个孩子的指针
  //构造函数
  node(int num, bool IsLeaf):n(num),leaf(IsLeaf){}
  //磁盘读写操作
  void Disk_Read(){}
  void Disk_Write(){}
};
//B 树结构
class B_Tree
{
public:
  //指向根结点
  node *root;
  B_Tree():root(NULL){}

  //从以 x 为根结点的树中寻找关键字为 k 的结点，若找到，将结果存入 y 中，返回其是第几个关键字
  int B_Tree_Search(node *x, char k, node&y);
  //构造一棵带树结点的空树
  void B_Tree_Create();
  //分裂，把 y 分裂为两个结点，选择其中一个关键字插入到 x 中的第 i 个位置
  void B_Tree_Split_Child(node *x, int i, node *y);
  //将关键字 k 插入到一个未满的结点 x 中
  void B_Tree_Insert_Nonfull(node *x, char k);
  //向 T 中插入关键字 k
  void B_Tree_Insert(char k);
  //删除 T 树中关键字为 k 的结点，由于是递归方法，当前处理的是 x 结点
  void B_Tree_Delete(node *x, char k);
  //按关键字从小到大输出结点
  void Print(node *n);
};

//从以 x 为根结点的树中寻找关键字为 k 的结点，若找到，将结果存入 y 中，返回其是第几个关键字
int B_Tree::B_Tree_Search(node *x, char k, node&y)
{
  int i = 1;
  //找到第一个关键字不大于 k 的 i
  while(i < x->n && k > x->key[i])
    i++;
  //若 key[i] = k，则找到了
  if(i <= x->n && k == x->key[i])
  {
    //将结果存入 y 中
    y = *x;
    //返回其是第几个关键字
    return i;
  }
  //若没找到，则返回空
  if(x->leaf)
  {
  //  &y = NULL;
    return 0;
  }
  //若还有子树可以找，则递归查找第 i 个子树
  x->child[i]->Disk_Read();
  return B_Tree_Search(x->child[i], k, y);
}
//构造一棵带树结点的空树
void B_Tree::B_Tree_Create()
{
  //生成一个根结点
  //初始时，根结点为叶子结点，根结点中没有关键字
  root = new node(0, true);
  root->Disk_Write();
}
//分裂，把 y 分裂为两个结点，选择其中一个关键字插入到 x 中的第 i 个位置
void B_Tree::B_Tree_Split_Child(node *x, int i, node *y)
{
  int j;
  //生成一个新结点 z
  //要把 y 分裂为 y 和 z，因此 z 的叶子属性与 y 相同
  //分裂前 y 有 2t-1 个关键字，分裂后前 t-1 个属于 y，后 t-1 个属于 z，中间第 t 个属于 x
  node *z = new node(t-1, y->leaf);
  y->n = t - 1;
  //后 t-1 个关键字依次复制给 z
  for(j = 1; j < t; j++)
    z->key[j] = y->key[j+t];
  //如果有孩子，孩子也要复制过去，原来有 2t 个子树，前 t 个属于 y，后 t 个属于 z
  if(y->leaf == false)
  {
    for(j = 1; j <= t; j++)
      z->child[j] = y->child[j+t];
  }
  //使 z 作为 x 的第 i+1 个孩子(y 已经是 x 的第 i 个孩子)
  for(j = x->n+1; j > i; j--)
    x->child[j+1] = x->child[j];
  x->child[i+1] = z;
  //把 y 中第 t 个关键字插入到 x 的第 i 个位置
  for(j = x->n; j >= i; j--)
    x->key[j+1] = x->key[j];
  x->key[i] = y->key[t];
  //x 的关键字+1
  x->n++;
  y->Disk_Write();
  z->Disk_Write();
  x->Disk_Write();
}
//将关键字 k 插入到一个未满的结点 x 中
void B_Tree::B_Tree_Insert_Nonfull(node *x, char k)
{
  int i = x->n;
  //若 x 是叶子结点
  if(x->leaf)
  {
    //找到该插入的位置
    while(i >= 1 && k < x->key[i])
    {
      x->key[i+1] = x->key[i];
      i--;
    }
    //插入关键字 k
    x->key[i+1] = k;
    x->n++;
    x->Disk_Write();
  }
  //若不是叶子结点
  else
  {
    //找到该插入的位置
    while(i >= 1 && k < x->key[i])
      i--;
    i++;
    //读取其孩子，将关键字插入到它的孩子中，分两种情况
    x->child[i]->Disk_Read();
    //孩子已满
    if(x->child[i]->n == 2 * t - 1)
    {
      //对孩子执行分裂操作，分裂后，孩子不变为不满
      B_Tree_Split_Child(x, i, x->child[i]);
      if(k > x->key[i])
        i++;
    }
    //孩子不满，直接对孩子进行插入操作
    B_Tree_Insert_Nonfull(x->child[i], k);
  }
}
//向 T 中插入关键字 k
void B_Tree::B_Tree_Insert(char k)
{
  node *r = root, *s;
  //若根结点已满
  if(r->n == 2*t-1)
  {
    //申请一个新的结点，将新的结点作为根结点
    root = new node(0, false);
    root->child[1] = r;
    //将原根结点分裂为两个结点，分别作为 s 的第 0 个孩子和第 1 个孩子
    B_Tree_Split_Child(root, 1, r);
    //把关键字 k 插入到根结点中，此时根结点一定不满
    B_Tree_Insert_Nonfull(root, k);
  }
  //若根结点不满
  else
    //直接把关键字插入到根结点中
    B_Tree_Insert_Nonfull(r, k);
}
//删除 T 树中关键字为 k 的结点，由于是递归方法，当前处理的是 x 结点
void B_Tree::B_Tree_Delete(node *x, char k)
{
  int i, j;
  //找到 x 中第一个不小于 k 的关键字，即待处理的位置
  for(i = 1; i <= x->n; i++)
    if(x->key[i] >= k)
      break;
  //y 是关键字 k 之前的结点，即小于 k 的最大孩子
  //z 是关键字 k 之后的结点，即大于 k 的最小孩子
  node *y = x->child[i], *z = x->child[i+1], *d;
  //若关键字 k 在结点 x 中的第 i 个位置
  if(x->key[i] == k && i <= x->n)
  {
    //1)y 是叶子结点，则直接从 x 中删除 k
    if(x->leaf == true)
    {
      //关键字依次前移
      for(j = i; j < x->n; j++)
        x->key[j] = x->key[j+1];
      //关键字数-1
      x->n--;
      return;
    }
    //2)x 是内结点
    //2-a：x 中前于 k 的子结点 y 包含至少 t 个关键字
    if(y->n >= t)
    {
      //找出 k 在以 y 为根的子树中的前驱 d
      d = y;
      while(d->leaf == false)
        d = d->child[d->n+1];
      //用 d 取代 k
      x->key[i] = d->key[d->n];
      //递归地删除 d
      B_Tree_Delete(y, d->key[d->n]);
    }
    //2-b：x 是位于 k 之后的子结点 z 包含至少 t 个关键字
    else if(z->n >= t)
    {
      //找出 k 在以 z 为根的子树中的后继 d
      d = z;
      while(d->leaf == false)
        d = d->child[1];
      //用 d 取代 k
      x->key[i] = d->key[1];
      //递归地删除 d
      B_Tree_Delete(z, d->key[1]);
    }
    //2-c：y 和 z 都只有 t-1 个关键字，将 k 和 z 中所有关键字合并进 y，使得 x 失去 k 和指向 z 的指针
    else
    {
      //将 k 关键字合并进 y
      y->key[y->n+1] = k;
      //将 z 中所有关键字合并进 y
      for(j = 1; j <= z->n; j++)
        y->key[y->n+j+1] = z->key[j];
      //如果有孩子，孩子也要合并
      if(y->leaf == false)
      {
        //使得 x 指向 z 的指针
        for(j = 1; j <= z->n+1; j++)
          y->child[y->n+j+1] = z->child[j];
      }
      //y 包含 2t-1 个关键字
      y->n = y->n + 1 + z->n;
      //使得 x 失去 k
      for(j = i; j < x->n; j++)
        x->key[j] = x->key[j+1];
      //使 x 失去指向 z 的指针
      for(j = i+1; j <= x->n; j++)
        x->child[j] = x->child[j+1];
      x->n--;
      //如果 x 是根结点，x
      if(x->n == 0 && root == x)
        root = y;
      //释放 z
      delete z;
      //将 k 从 y 中递归删除
      B_Tree_Delete(y, k);
    }
  }
  //3) 关键字不在结点 x 中，则必定包含 k 的正确的子树的根 x->child[i]
  else
  {
    //x 是叶子结点，找到根结点都没有找到 k，则 k 不在树中
    if(x->leaf == true)
    {
      cout<<"error:not exist"<<endl;
      return;
    }
    //x 是内结点
    //3-a:child[i]中只有 t-1 个关键字
    if(y->n == t-1)
    {
      //它的相邻兄弟 x->child[i+1](用 z 表示) 包含至少 t 个关键字
      if(i <= x->n && i <= x->n && z->n >= t)
      {
        //将 x 中的关键字下降至 y
        y->n++;
        y->key[y->n] = x->key[i];
        //将 z 的某一关键字上升至 x
        x->key[i] = z->key[1];
        for(j = 1; j < z->n; j++)
          z->key[j] = z->key[j+1];
        //将 z 适合的子女指针移到 y
        if(y->leaf == false)
        {
          y->child[y->n+1] = z->child[1];
          for(j = 1; j <= z->n; j++)
            z->child[j] = z->child[j+1];
        }
        //z 的关键字数-1
        z->n--;
      }
      //它的相邻兄弟 x->child[i-1]包含至少 t 个关键字
      else if(i > 1 && x->child[i-1]->n >= t )
      {
        //将 x 中的关键字下降至 y
        for(j = y->n; j >= 1; j--)
          y->key[j+1] = y->key[j];
        y->key[1] = x->key[i-1];
        y->n++;
        //将 y 的相邻兄弟 x->child[i-1]的某一关键字上升至 x
        x->key[i-1] = x->child[i-1]->key[x->child[i-1]->n];
        //将该兄弟适合的子女指针移到 y
        if(y->leaf == false)
        {
          for(j = y->n; j >= 1; j--)
            y->child[j+1] = y->child[j];
          y->child[1] = x->child[i-1]->child[x->child[i-1]->n+1];
        }
        //x->child[i-1]的关键字数-1
        x->child[i-1]->n--;
      }
      //y 和其所有相邻兄弟都只有 t-1 个关键字，则与其中一个兄弟合并
      else
      {
        //与后面一个结点（用 z 表示) 合并
        if(i <= x->n)
        {
          //将 x->key[i]并入 y 中
          y->key[y->n+1] = x->key[i];
          //将 z 中所有关键字并入 y 中
          for(j = 1; j <= z->n; j++)
            y->key[j+y->n+1] = z->key[j];
          //如果有孩子，所有孩子也要并入
          if(y->leaf == false)
          {
            for(j = 1; j <= z->n+1; j++)
              y->child[j+y->n+1] = z->child[j]; 
          }
          //修改 y 的关键字数
          y->n = y->n + 1 + z->n;
          //将 x->key[i]从 x 中移出
          for(j = i; j < x->n; j++)
            x->key[j] = x->key[j+1];
          //把指向 z 的指针从 x->child 中移出
          for(j = i+1; j <= x->n; j++)
            x->child[j] = x->child[j+1];
          //x 的关键字数-1
          x->n--;
          //若根结点被删除，更新根结点
          if(x->n==0 && root == x)
            root = y;
        }
        //与前面一个结点合并
        else
        {
          //令 z=x->child[i-1],y=x->child[i]，把 z 并入 y 中
          z = y;i--;
          y = x->child[i];
          //将 x->key[i]并入 y 中
          y->key[y->n+1] = x->key[i];
          //将 z 中所有关键字并入 y 中
          for(j = 1; j <= z->n; j++)
            y->key[j+y->n+1] = z->key[j];
          //如果有孩子，所有孩子也要并入
          if(y->leaf == false)
          {
            for(j = 1; j <= z->n+1; j++)
              y->child[j+y->n+1] = z->child[j]; 
          }
          //修改 y 的关键字数
          y->n = y->n + 1 + z->n;
          //将 x->key[i]从 x 中移出
          for(j = i; j < x->n; j++)
            x->key[j] = x->key[j+1];
          //把指向 z 的指针从 x->child 中移出
          for(j = i+1; j <= x->n; j++)
            x->child[j] = x->child[j+1];
          //x 的关键字数-1
          x->n--;
          //若根结点被删除，更新根结点
          if(x->n==0 && root == x)
            root = y;
        }
      }
    }
    //递归执行删除操作
    B_Tree_Delete(y, k);
  }
}
//按关键字从小到大输出结点
void B_Tree::Print(node *n)
{
  int i;
  for(i = 1; i <= n->n; i++)
  {
    if(n->leaf == false)
      Print(n->child[i]);
    cout<<n->key[i]<<' ';
  }
  if(n->leaf == false)
    Print(n->child[n->n+1]);
}

main.cpp

#include <iostream>
using namespace std;
#include "B_Tree.h"
int main()
{
  //测试数据
  char ch[] = {'F','S','Q','K','C','L','H','T','V','W','M','R','N','P','A','B','X','Y','D','Z','E'};
  //生成一棵 B 树
  B_Tree *T = new B_Tree;
  T->B_Tree_Create();
  //依次插入关键字
  cout<<"插入测试"<<endl;
  int i;
  for(i = 0; i < 21; i++)
  {
    T->B_Tree_Insert(ch[i]);
    T->Print(T->root);
    cout<<endl;
  }
  //输出这棵树
  T->Print(T->root);
  cout<<endl;
  //B 树删除操作测试
  cout<<"查找与删除测试"<<endl;
  char c;
  for(i = 0; i < 100; i++)
  {
    cin>>c;
    T->B_Tree_Delete(T->root, c);
    T->Print(T->root);
    cout<<endl;
  }
  return 0;
}