《数据结构》第七章：树和森林

在客观世界中，存在着诸多如行政机构、磁盘目录和族谱的组织结构，与动物分类类似，是一种层次化结构，可采用树形结构表示。譬如磁盘目录，一个目录的子目录通常不止两个，无法用二叉树表示，需要采用多叉树的形式，即每个结点可以有不同数目的子结点。

7.1树的定义

树是含有n个结点的有限集合。在任意一棵非空树中：

1. 有且仅有一个特定的称为根的结点
2. 当n＞1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身也是一棵树。并且T1，T2，…，Tm称为根的子树。

树中的相关概念，如结点的度、孩子结点和双亲结点等，定义与二叉树中的相同。

森林是m（m≥0）棵互不相交的树的集合，可记为F=（T1，T2，…，Tm）。对树中的每个结点而言，其子树的结合即为子树森林。

7.2树的存储结构

树的存储结构有多种，可以应用于不同场合。但无论采用哪种存储结构，都要求其不仅能存储各结点本身的信息，还能表示树中各结点之间存在的关系。

7.2.1双亲表示法

在树中，除根结点没有双亲（即父结点）外，其他结点的双亲是唯一确定的。根据这个特性，可用数组存储树中结点及其关系。数组中的每个分量含有两个域：元素值data和该结点的双亲位置parent。树的这种表示方法称为双亲表示法。

树的双亲存储结构类型定义如下：

typedef struct PTNode{TElemType data;//数据域int parent;//双亲位置，根结点的parent值为-1}PTNode;//双亲结点类型typedef struct{PTNode *nodes;//由初始化分配的结点数组int r,nodeNum;//根结点和结点数 }PTree;//树的双亲存储结构类型

显然，这种存储结构可由parent直接找到双亲，并可容易地找到所有祖先。但如果需要查找结点的孩子及其子孙，则需要遍历整个结构。

7.2.2双亲孩子表示法

双亲孩子表示法是对双亲表示法的扩展，为各结点构造孩子单链表，以便访问结点的孩子及其子孙。在结点数组元素增加firstChild域作为结点的孩子链表头指针。在孩子链表中，每个结点包含孩子在结点数组的位置child Index和指向下一个孩子结点的指针nextChild。

树的双亲孩子存储结构的类型定义如下：

typedef struct ChildNode{int ChildIndex;//孩子在结点数组的位置struct ChildNode *nextChild;//下一个孩子}ChildNode;//孩子链表中的结点类型typedef struct{TElemType data;//元素值int parent;//双亲位置struct ChildNode *firstChild;//孩子链表头指针}PCTreeNode;//双亲孩子结点类型typedef struct{PCTreeNode *nodes;//结点数组4int nodeNum,r;//结点元素个数、根位置}PCTree;//树的双亲孩子存储结构类型

双亲孩子表示法存储了孩子结点的信息，便于实现涉及孩子或双亲的操作。若不涉及双亲操作，则可以去掉parent域，简化为孩子链表存储结构。

7.2.3孩子兄弟表示法

在树中，结点的最左孩子（第一个孩子）和右兄弟（下一个孩子）如果存在则都是唯一的。因此，孩子兄弟表示法采用二叉链式存储结构，每个结点包含三个域：元素值域data、最左孩子指针firstChild和右兄弟指针nextSibling。

树的孩子兄弟链表的类型定义如下：

typedef struct CSTNode{TElemType data;//数据域struct CSTNode*firstChild,*nextSibling;//最左孩子指针、右兄弟指针}CSTNode,*CSTree,*CSForest;//孩子兄弟链表

以下是基于孩子兄弟表示法的树接口。

Status InitTree(CSTree &L);//构造空树LCSTree MakeTree(CSTree &T);//创建根结点e和n棵子树的树Status DestroyTree(CSTree &T);//销毁树Tint TreeDepth(CSTree T);//返回树T的深度CSNode*Search(CSTree T,TElemType e);//查找树T中的结点e并返回其指针Status InsertChild(CSTree &T,int i,CSTree c);//插入c为T的第i棵子树，c非空并与T不相交Status DeleteChild(CSTree &T,int i);//删除T的第i棵子树

上述基本接口未提供双亲操作，如果需要频繁访问双亲结点，则可在结点中增设parent指针域。下面给出几个基本接口的实现。

1.创建树。

该操作创建一棵有n棵子树的树，根结点值为e。由于子树数目事先无法确定，所以需要使用变长参数，并使用标准库stdarg以获取n棵子树的实参。

算法：创建树

#include <stdrag.h>//标准头文件，提供宏va_start、va_arg和va_end//用于存储变长参数CSTree MakeTree(TElemType e,int n,...){//创建根结点e和n棵子树的树，变长参数为n棵子树int i;CSTree t,p,pi;va_list argptr;//argptr是存放变长参数表信息的数组t=(CSTree)malloc(sizeof(CSTNode));//开辟空间if(NULL==t){return NULL;//开辟失败}t->data=e;//根结点的值为et->firtsChild=t->nextSibling=NULL;if(n<=0){return t;//若无子树，则返回根结点}va_start(argptr,n);//令argptr指向参数n后的第一个实参p=va_arg(argptr,CSTree);//取第一棵子树的实参转换为CSTree类型t->firstChild=p;pi=p;for(i=1;i<n;i++){//将n棵树作为根结点的子树插入p=va_arg(aargptr,CSTree);//取下一棵子树的实参并转换为CSTree类型pi->nextSibling=p;pi=p;}va_end(argptr);//取实参结束}

2.插入第i棵子树。

插入树c作为树T的第i棵子树。当树非空时，若i==1，则树c直接作为第一颗子树插入；否则，先确定第i-1棵子树的位置，然后将c子树插入其后

算法：插入第i棵子树

Status InsertChild(CSTree &T,int i,CSTree c){//插入c作为T的第i棵子树，c非空并与T不相交int j;CSTree p;if(NULL==T||i<1){return ERROR;//树为空}if(i==1){//c插入为T的第1棵子树c->nextSibling=T->firstChild;T->firstChild=c;//c成为T的第一棵子树}else{p=T->firstChild;//p指向T的第i棵子树for(j=2;p!=NULL&&j<i;j++){p=p->nextSibling;//寻找插入位置}if(j==i)//找到插入位置{c->nextSibling=p->nextSibling;p->nextSibling=c}else{return ERROR;//插入位置i过大}}return OK;}

由于二叉树和树都可以二叉链表作为存储结构，则以二叉链表为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到唯一的一棵二叉树与之对应，从存储结构上看，树的孩子兄弟表示法和二叉树的二叉链表是相同的，只是解释不同而已。

从树的孩子兄弟表示的定义可知，任何一棵树与树对应的二叉树，其根结点的右子树必为空。若把森林中的第二棵树看成第一棵树的根结点的兄弟，则同样可以导出森林和二叉树的对应关系。

因此，给定一棵树或一个森林，可以找到唯一对应的一棵二叉树，反之亦然。这样，对数或森林的操作可以参考二叉树的相应操作实现。

7.3树和森林的遍历

树的先序和后序遍历的定义与二叉树相似。先序遍历先访问树的根结点，然后自左向右先序遍历根的每棵子树；序遍历先自左向右依次后序遍历每棵子树，再访问根结点。由于根结点的子树数目不确定，所以一般不考虑树的中序遍历。

树的先序遍历结果与对应二叉树的先序遍历结果一致，而树的后序遍历结果则与对应二叉树的中序遍历的结果一致。

由于森林与二叉树的一一对应关系，可将森林划分为3个部分：根结点、根结点的子树森林（即对应二叉树的子树）和除去第一棵树之外剩余的树构成的森林（简称剩余森林，即对应二叉树的右子树）。树是特例，是只有一棵树的森林，其余剩余森林为空。

当采用孩子兄弟表示法，森林的先序遍历的递归实现可以参考二叉树的先序遍历算法。森林的先序遍历过程是，先访问第一棵树的根结点，然后先序遍历第一棵树的子树森林，再先序遍历剩余森林。

算法：森林的先序遍历

Status PreOrderTraverseForest(CSForest F,Status(*visit)(TElemType)){//先序遍历森林Fif(NULL==F){return OK;//森林为空}if(ERROR==visit(F->data)){return ERROR;//访问第一棵树的根结点}if(ERROR==PreOrderTraverseForest(F->firstChild,visit)){return ERROR;//递归先序遍历第一棵子树森林}return PreOrderTraverseForest(F->nextSibling,visit);//递归先序遍历剩余森林}

与二叉树的遍历类似，树和森林的其他操作也可以通过遍历操作来实现。

1.求森林的深度

森林的深度应为“第一棵树的子树森林的深度加1”和“剩余森林的深度”之间的较大值

算法:求森林的深度

int ForestDepth(CSForest F){//求森林F的深度int dep1,dep2,dep;if(NULL==F){dep=0;//森林为空，深度为0}else{dep1=ForestDepth(F->firstChild);//求第一棵子树森林的深度dep2=ForestDepth(F->nextSibling);//求剩余森林的深度dep=dep1+1>dep2?dep1+1:dep2;//森林的深度}return dep;}

2.森林的查找

森林的查找操作Search是在森林F中查找结点e,可采用森林的先序遍历来实现.若查找成功则返回结点的指针,否则返回NULL.

算法:森林的查找

CSTNode *Search(CSForest F,TElemType e){//查找森林F中的结点e并返回其指针CSTNode *result=NULL;if(NULL==F){return NULL;//森林为空，返回NULL}if(F->data==e){return F;//找到结点，返回其指针}if((result=Search(F->firstChild,e))!=NULL)//在第一棵树的子树森林查找{return result;}return Search(F->nextSibling,e);//在剩余森林中查找}

7.4并查集

在集合的一些应用中，需将n（n＞0）个不同的元素划分为若干个等价的子集。这类问题的一种解决办法是，首先令每个元素自成一个单元素集合，然后将等价的元素所属的集合合并。

并查集合适描述这类问题。

例如，一致三个人A，B，C，他们之间可能存在亲戚关系，比如A和B是亲戚，B和C也是亲戚关系，能否从这些信息中判断A和C是否为亲戚？解决办法是首先令每个人自成一个集合{A}，{B}，{C}，根据存在的两两亲戚关系，将两个人所属的集合合并，最终可得到一个集合{A，B，C}，从而得到A和C是亲戚关系。

并查集是指一组不相交的子集所构成的集合，记作

S={S1，S2，S3，…，S4}

其中，任意两个子集Si和Sj（1≤i≠j≤n）两两不相交。每个子集选取某个元素作为其标识，称为代表元。约定在存储含m个数据元素的并查集前，需对所有元素进行0

到m-1的编号，并用编号表示对应的元素。例如，有9个数据元素，依次编号为0至8，根据等价关系构成并查集S={S1，S2，S3}，其中S1={1，2，4，7},S2={3,5,8},S3={0,6}，子集S1，S2，S3两两不相交。

并查集通常需要以下两种操作：

1. 查找某个元素所属的子集，简称查找（Find）操作。
2. 合并两个元素所属的集合，简称合并（Union）操作。

为了高效地实现上述操作，可用森林F=（T1，T2，T3，…，Tn）来表示并查集S。森林中地每棵树Ti（1≤i≤n）表示并查集S中的一个子集Si，Ti中每个结点表示Si中的一个元素，根结点作为代表元。为方便操作，结点应含有指向双亲结点的位标

其中S1={1，2，4，7}，S2={3，5，8}，S3={0，6}

上述森林易于实现并查集的操作。并查集可采用森林的双亲表示法作为存储结构，其类型定义如下：

typedef struct{int *parent;//双亲数组，其数组下标表示元素，数组存储对应元素所属树//的双亲结点的位序，当为-1时，表示是树的根结点int n;//森林的结点数目}PForest,MFSet;//森林、并查集

并查集的基本操作可定义为如下接口：

Status InitMFSet(MFSet &S,int n);//构造由n个单元子集构成的并查集SStatus DestroyMFSet(MFSet &S);//销毁并查集Sint FindMFSet(MFSet &S,int i);//查找元素i并在并查集S中的所属的子集，返回其代表元Status DiffMFSet(MFSet &S,int i,int j);//判断并查集S中的元素i和j是否在同一子集；若是，返回TRUE，否则返回FALSEStatus UnionMFSet(MFSet &S,int i,int j);//合并并查集S中元素i和j所属的两个子集。

1.并查集的初始化

该操作分配指定容量n的存储空间，且存储空间的初值置为-1，即每个元素自成一棵树。

算法：并查集的初始化

Status InitMFSet(MFSet &S,int n)//构造由n个单元素子集构成的并查集S{int i;S.parent=(int *)malloc(n*sizeof(int));//开辟空间if(NULL==S.parent){return OVERFLOW;//开辟失败}for(int i=0;i<n;i++){S.parent[i]=-1;//每个元素自成一棵树}S.n=n;return OK;}

2.查找操作

该操作是从元素i（即下标i）出发，沿着双亲数组的值一直找到根结点（根结点的值小于0），并返回根结点的位置。

算法：并查集的查找

int FindMFSet(MFSet &S,int i)//查找i在并查集S中所属子集，返回代表元{if(i<0||i>S=S.n){return -1;//元素i不存在}while(S.parent[i]>0){i=S.parent[i];//沿双亲位标链找到根结点}return i;//返回代表元}

3.合并操作

该操作首先分别查找元素i和j所在树的根结点ri和rj­，若ri和rj相等，则是同一子集，无需合并；否则吧根结点ri（或rj）的双亲结点值置为rj（或ri）。

算法：并查集的子集合并

Status Union(MFSet &S,int i,int j){//合并并查集S中元素i和j所属的两个子集int ri,rj;if(i<0||i>=S.n||j<0||j>=S.n){return FALSE;//元素i和j找不到}ri=FindMFSet(S,i);//i的根结点rj=FindMFSet(S,j);//j的根结点if(ri==rj){return FALSE;//ij本就为一个子集，无需合并}S.parent[ri]=rj;//把根结点ri的双亲结点置为rj，实现合并return TRUE;}

合并操作所需的时间主要取决于查找长度，即树的高度。有两种改进方法可降低树的高度：加权合并规则法和路径压缩法

1.加权合并规则法

加权合并规则法的基本思路是，合并时，让结点数较少的跟根结点指向结点数较多的树的根结点，即把小树合并到大树里面。此方法可将树的整体深度限制在O（log n）。为此，将根结点存储的“-1”该为该树所含结点个数的负值。

算法：采用加权合并规则的合并

Status UnionMFSet(MFSet &S,int i,int j){//采用加权合并规则法合并并查集S中元素i和j所属的两个子集int ri,rj;if(i<0||i>=S.n||j<0||j>=S.n){return FALSE;//查找不到}ri=FindMFSet(S,i);rj=FindMFSet(S,j);if(ri==rj){return FALSE;}if(S.parent[ri]>S.parent[rj]){//注意：比较的是结点个数的负值S.parent[rj]+=S.parent[ri];//两个均为负值S.parent[ri]=rj;//将元素i的子集并到元素j所在的子集}else{S.parent[ri]+=S.parent[rj];//两个均为负值S.parent[rj]=ri;//将元素j的子集并到元素i所在的子集}return TRUE;}

2.路径压缩法

路径压缩法更为高效，在查找结点所在树的根结点的过程中，置查找路径上的每个结点的双亲位标值为根结点。

算法：采用路径压缩法的查找

int FindMFSet_PC(MFSet &S,int i){//采用路径压缩法查找元素i在并查集S中所属的子集，返回该子集的代表元if(i<0||i>=S.n){return -1;//查找不到}if(S.parent[i]<0){return i;//找到根结点}S.parent[i]=FindMFSet_PC(S,S.parent[i]);//i的双亲值置为根结点return S.parent[i];//返回根结点}

并查集可应用于许多实际问题中。如判断是否为亲戚的问题，初始时每个人自成一个子集；若a和b存在亲戚关系，则合格两个人所在的子集；如此重复，直至处理完所有已知的亲戚关系。于是亲戚关系判定转化为判断任意两个人是否为同一子集。

算法：判断亲戚

Status hasRelationship(MFSet &S,int a,int b){//判断元素a和b是否是亲戚，若是则返回TRUE，否则返回FALSEif(a<0||b<0||a>=S.n||b>=S.n){return FALSE;//查找失败}if(FindMFSet_PC(S,a)==FindMFSet_PC(S,b)){return TRUE;}else{return FALSE;}}

7.5 B树

二叉查找树树和二叉平衡树都是典型的二叉查找树的结构，其查找的时间复杂度与树的高度相关。一般而言，树的高度越低，则查找效率越高。为了降低树的高度，可令每个结点存储更多元素，将平衡二叉树扩展为平衡多叉查找树。

7.5.1 B树的定义

一棵m阶B树，或为空树，或为满足以下特性的m叉树：

1. 树中的每个结点最多含有m棵子树。
2. 若根结点是非终端结点，则至少有两颗子树。
3. 除根结点之外的所有非终端结点至少有⌈m/2⌉棵子树。
4. 每个非终端结点中包含信息：（n，A0，K1，A1，K1，A2，…，K­n，An）。其中：
   • Ki（1≤i≤n）为关键字，且关键字按升序排序。
   • 指针A­i（0≤i≤n）指向子树的根结点，Ai-1指向子树中所有结点的关键字均小于Ki，且大于Ki-1.
   • 关键字的个数n必须满足：⌈m/2⌉-1≤n≤m-1.
5. 所有子叶结点必须出现在同一层，叶子结点不包含任何信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空。

实际上，B树的结点还应包含n个指向每个关键字相应记录的指针。

B树主要用于文件的检索，查找操作涉及外村的读取。m阶B树的结点类型定义如下：

#define m 3//B树的阶数，此处设为3typedef struct{int keynum;//结点当前的关键字个数KeyType key[m+1];//关键字数组，key[0]未用struct BTNode *parent;//双亲结点指针struct BTNode *ptr[m+1];//孩子结点的指针数组Record *recptr[m+1];//B树的结点及指针类型}BTNode,*BTree;//B树的结点及指针类型

7.5.2 B树的查找

B树的查找从根结点开始，重复以下过程：若给定关键字等于结点中的某个关键字Ki，则查找成功；若给定关键字比结点中的Ki小，则进入指针A0指向下一层结点继续查找；若在两个关键字Ki-1和Ki之间，则进入它们之间的指针Ai—1指向的下一层结点继续查找；若比该结点所有关键字大，则在其最后一个指针A­n指向的下一层结点继续查找；若找到叶子结点，则说明给定值对应的数据记录不存在，查找失败。

由于查找需要返回的信息包括找到的结点、该结点中关键字位序以及查找标记，所以将这些信息封装成一个结构体。

算法：B树的查找

typedef struct{BTree pt;//指向找到的结点int i;//1≤i≤m，在结点中的关键字位序int tag;//1:查找成功；0：查找失败}result;//B树查找结构类型void SearchBTree(BTree t,int k,result &r){//在m阶B树t上查找关键字k，用r返回（pi，i，tag）//若查找成功，则标记tag=1，指针pt所指结点中第i个关键字等于k//否则tag=0，若要插入关键字为k的记录，应位于pt结点中第i-1个和第i个关键字之间int i=0,found=0;BTree p=t,q=NULL;//初始，p指向根结点；p将用于指向待查结点，q指向其双亲while(p!=NULL&&0==found){i=Search(p,k);//在p->key[1..p->keynum]之间查找p->key[i-1]<k<=p->key[i]if(i<=p->keynum&&p->key[i]==k){found=1;//找到待查关键词}else{q=p;p=p->ptr[i-1];//指针下移}}if(1==found)//查找成功，返回k的位置和p及i{r.pt=p;r.i=i;r.tag=1;}else//查找不成功，返回k的插入位置q及i{r.pt=q;r=i;r.tag=0;}}int Search(BTree p,int k){//在p->key[1..p->keynum]找kint i=1;while(i<=p->keynum&&k>p->key[i]){i++;}return i;}

7.5.3 B树的插入

B的插入过程可描述为，利用B树的查找操作查找关键字k的插入位置。若找到，则说明该关键字已经存在，直接返回；否则查找操作失败于某个最底层的非终端结点上，在该结点插入后，若其关键字总数n未达到m，算法结束，否则需分裂结点。

分裂的方法是，生成一新结点，从中间位置把结点（不包括中间位置的关键字）分成两部分。前半部分留在旧结点中，后半部分复制到新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。如果插入后父结点的关键字个数也超过m-1，则继续分裂。这个向上分裂的过程如果持续到根结点，则会产生新的根结点。

算法：B树的插入操作

void InsertBTree(BTree &t,int k){//在B树t中q结点的key[i-1]和key[i]之间插入关键字k//若插入后结点关键字个数等于B树的阶，则沿双亲指针链进行结点分裂，使t仍是m阶B树int x,s,finished=0,needNewRoot=0;BTree ap;if(NULL==q){newRoot(t,NULL,k,NULL);//生成新的结点}else{x=k;ap=NULL;while(0==needNewRoot&&0==finished){Insert(q,i,x,ap);//x和ap到q->key[i-1]和q->ptr[i]if(q->keynum<m){finished=1;//插入完成}else//分裂结点{s=(m+1)/2;split(q,s,ap);x=q->key[s];if(q->parent!=NULL){q=q->parent;i=Search(q,x);//在双亲结点中查找x的插入位置}else{needNewRoot=1;}}}//whileif(needNewRoot==1)//t是空树或者根结点已分裂为q和ap结点{newRoot(t,q,x,ap);//生成含有（q，x，ap）的新的根结点t}}}void split(BSTree &q,int s,BTree &ap){//将q结点分裂为两个结点，前一半保留在原结点，后一半移入ap所指新结点int i,j,n=q->keynum;ap=(BTNode*)malloc(sizeof(BTNode));//生成新结点ap->ptr[0]=q->ptr[s];for(i=s+1,j=1;j<=n;i++,j++)//后一半移入ap结点{ap->key[j]=q->key[i];ap->ptr[j]=q->ptr[i];}ap->keynum=n-s;ap->parent=q->parent;for(i=0;i<n-s;i++)//修改新结点的子结点的parent域{if(ap->ptr[i]!=NULL){qp->ptr[i]->parent=ap;//}q->keynum=s-1;//q结点的前一半保留，修改keynum}}void newRoot(BTree &t,BTree p,int x,BTree ap){//生成新的根结点t=(BTNode*)malloc(sizeof(BTNode));t->keynum=1;t->ptr[0]=p;t->ptr[1]=ap;t->key[1]=x;if(p!=NULL){p->parent=t;}if(ap!=NULL){ap->parent=t;}t->parent=NULL;//新根的双亲是空指针}void Insert(BTree &q,int i,int x,BTree ap){//关键字x和新结点ap分别插入到q->key[i]和q->ptr[i]int j,n=q->keynum;for(j=n;j>=i;j--){q->key[j+1]=q->key[j];q->ptr[j+1]=q->ptr[j];}q->key[i]=x;q->ptr[i]=ap;if(ap!=NULL){ap->parent=q;}q->keynum++;}

7.5.4 B树的删除

在B树上删除关键字k的过程可利用前述的查找过程找出该关键字所在的结点，然后根据k所在结点是否为最下层非终端结点进行不同的处理。

1.该结点为最下层非终端结点

首先直接从该结点删除关键字k，然后根据以下3种可能分别作相应处理。

1. 如果被删除关键字结点的原关键字个数n≥⌈m/2⌉，则删去该关键字后该关键字仍满足B树的定义。

1.如果被删关键字所在结点的关键字个数n等于⌈m/2⌉-1，则删去该关键字后该结点将不满足B树的定义，需要调整：如果其左右兄弟结点中有“富余”的关键字，即与该结点相邻的右（或左）兄弟结点中的关键字数目大于⌈m/2⌉-1，则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。

2.如果相邻兄弟结点中没有“多余”的关键字，即相邻兄弟结点中关键字数目均等于⌈m/2⌉-1。此时比较复杂，需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割两者的关键字Ki一起，合并到Ai-1（或Ai）结点，即删除该关键字结点的左（右）兄弟结点。如果导致双亲结点中关键字个数小于⌈m/2⌉-1，则对此双亲结点做相同的处理。如果直到对根结点也做合并处理，则整棵树减少一层。

2.该结点不是最下层非终端结点

假设被删关键字为该结点中第i个关键字K­i，则可从指针Ai所指的子树中找到位于最下层非终端结点的最小关键字代替K­i­，并将其删除。

算法：B树的删除操作

void DeleteBTree(BTree &p,int i){//删除B树上p结点的第i个关键字if(p->ptr[i]!=NULL)//若不是最下层非终端结点{Successor(p.i);//在Ai子树中找到最下层非终端结点的最小关键字代替KiDeleteBTree(p,1);//转换为删除最下层非终端结点的最小关键字}else//若是最下层非终端结点{Remove(p,i);//从结点p中删除key[i]if(p->keynum<(m-1)/2)//删除后关键字个数小于（m-1）/2、{Restore(p,i);//调整B树}}}void Successor(BTree &p, int i) {// 在p结点的第i个指针指向的子树中找到最小的关键字代替Ki// 如果是叶子节点，直接返回if (p->ptr[i]->leaf) {return;}// 找到最小的关键字，即最左边的子树BTree successor = p->ptr[i];while (!successor->leaf) {successor = successor->ptr[0];}// 将最小关键字代替Kip->key[i] = successor->key[0];}void Remove(BTree &p, int i) {// 从结点p中删除key[i]// 将key[i+1:]往前移动for (int j = i + 1; j <= p->keynum; j++) {p->key[j-1] = p->key[j];}// 将ptr[i+1:]往前移动for (int j = i + 1; j <= p->keynum + 1; j++) {p->ptr[j-1] = p->ptr[j];}// 关键字数量减一p->keynum--;}void Restore(BTree &p, int i) {// 调整B树结点p// 如果左兄弟结点存在且关键字数量大于(m-1)/2，则从左兄弟结点借一个关键字if (i > 1 && p->ptr[i-1]->keynum > (m-1)/2) {// 将p的第一个关键字后移一位for (int j = p->keynum; j >= 1; j--) {p->key[j] = p->key[j-1];}// 将左兄弟结点的最后一个关键字插入到p的第一个位置p->key[0] = p->ptr[i-1]->key[p->ptr[i-1]->keynum-1];// 如果左兄弟结点不是叶子节点，将最后一个指针也转移到pif (!p->ptr[i-1]->leaf) {p->ptr[0] = p->ptr[i-1]->ptr[p->ptr[i-1]->keynum];}// 更新左兄弟结点的关键字数量p->ptr[i-1]->keynum--;// 更新p的关键字数量p->keynum++;return;}// 如果右兄弟结点存在且关键字数量大于(m-1)/2，则从右兄弟结点借一个关键字if (i <= p->keynum && p->ptr[i+1]->keynum > (m-1)/2) {// 将p的第i个关键字后移一位for (int j = p->keynum; j >= i+1; j--) {p->key[j] = p->key[j-1];}// 将右兄弟结点的第一个关键字插入到p的第i个位置p->key[i] = p->ptr[i+1]->key[0];// 如果右兄弟结点不是叶子节点，将第一个指针也转移到pif (!p->ptr[i+1]->leaf) {p->ptr[i] = p->ptr[i+1]->ptr[0];}// 将右兄弟结点的关键字和指针往前移动for (int j = 1; j <= p->ptr[i+1]->keynum - 1; j++) {p->ptr[i+1]->key[j-1] = p->ptr[i+1]->key[j];}for (int j = 1; j <= p->ptr[i+1]->keynum; j++) {p->ptr[i+1]->ptr[j-1] = p->ptr[i+1]->ptr[j];}// 更新右兄弟结点的关键字数量p->ptr[i+1]->keynum--;// 更新p的关键字数量p->keynum++;return;}// 如果左右兄弟结点的关键字数量都是(m-1)/2，则将关键字从父结点借一个，并和左右兄弟结点合并if (i > 1) {// 从父结点借一个关键字BorrowFromLeftSibling(p, i);} else {// 从父结点借一个关键字BorrowFromRightSibling(p, i);}}void BorrowFromLeftSibling(BTree &p, int i) {// 从左兄弟结点借一个关键字// 取得左兄弟结点BTree leftSibling = p->ptr[i-1];// 将p的第一个关键字后移一位for (int j = p->keynum; j >= 1; j--) {p->key[j] = p->key[j-1];}// 将左兄弟结点的最后一个关键字插入到p的第一个位置p->key[0] = leftSibling->key[leftSibling->keynum-1];// 如果左兄弟结点不是叶子节点，将最后一个指针也转移到pif (!leftSibling->leaf) {p->ptr[0] = leftSibling->ptr[leftSibling->keynum];}// 更新左兄弟结点的关键字数量leftSibling->keynum--;// 更新p的关键字数量p->keynum++;}void BorrowFromRightSibling(BTree &p, int i) {// 从右兄弟结点借一个关键字// 取得右兄弟结点BTree rightSibling = p->ptr[i+1];// 将p的第i个关键字后移一位for (int j = p->keynum; j >= i+1; j--) {p->key[j] = p->key[j-1];}// 将右兄弟结点的第一个关键字插入到p的第i个位置p->key[i] = rightSibling->key[0];// 如果右兄弟结点不是叶子节点，将第一个指针也转移到pif (!rightSibling->leaf) {p->ptr[i] = rightSibling->ptr[0];}// 将右兄弟结点的关键字和指针往前移动for (int j = 1; j <= rightSibling->keynum - 1; j++) {rightSibling->key[j-1] = rightSibling->key[j];}for (int j = 1; j <= rightSibling->keynum; j++) {rightSibling->ptr[j-1] = rightSibling->ptr[j];}// 更新右兄弟结点的关键字数量rightSibling->keynum--;// 更新p的关键字数量p->keynum++;}

7.5.5 B+树

B+树是应文件系统所需而提出的一种B树的变型。一棵m阶的B+树和m阶B树的差异在于：

1. 有n棵子树的结点包含n个关键字。
2. 所有子树结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子本身依关键字大小自小而大顺序链接。
3. 所有的非终端结点可以看作索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。

通常B+树有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。因此B+树的查找方式有两种：一种是从最小关键字起顺序查找，另一种是从根结点开始，进行随机查找。

在B+树上进行随机查找、插入和删除过程基本上与B树类似。只是在查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。

索引是B+树的一种典型应用。索引是对数据库中一个或多个列的值进行排序的结构，与在表中搜素所有的行相比，索引用指针指向存储在表中指定列的数据值，然后根据指定的次序排列这些指针，有助于更快地获取信息，通常情况下，只有当经常查询索引列中的数据时，才需要在表上创建索引。索引会占用磁盘空间，并影响数据更新的速度。但是在多数情况下，索引所带来的数据检索速度优势大大超过它的不足之处。