|
B+树可以看作是B树的变形，对于存放在外存贮器上的字典，B+树比B树更为常用。
一个m阶的B+树满足下列条件∶
(1) 每个结点至多有m棵子树。
(2) 除根结点外，其它每个分支至少有m/2棵子树。
(3) 非叶结点的根结点至少有两棵子树。
(4) 有n棵子树的结点有n个关键码，叶结点中至少包含n/2个关键码。
(5) 叶结点都在同一层中，其中存放数据文件中记录的关键码及指向该记录的指针，或存放数据文件分块后每块的最大关键码及指向该块的指针。叶结点按关键码值大小顺序链接。可以把每个叶结点看成是一个基本索引块(直接指向数据文件中的记录)。
(6) 所有分支结点可看成是索引的索引。使结点中仅包含它的各个子结点中最大(或最小)关键码的分界值及指向子结点的指针。
/*=========================== BinTreeh.h =========================*/
#include <stdio.h>
/*=========================== data struct =====================*/
typedef char ElementType;
typedef struct Node{
ElementType data;
struct Node *LChild; /* 左子树 */
struct Node *RChild; /* 右子树*/
} TreeNode;
/*=============================== function prounce ===============*/
int CreateBinTree( TreeNode **rootp,ElementType **lp );
void FreeTree( TreeNode *rootp );
int DelTree( TreeNode *rootp,ElementType e );
int Insert( TreeNode *rootp,ElementType Curr,ElementType e,int CurrPos );
TreeNode *FindNode( TreeNode *rootp,ElementType e );
TreeNode *FindParent( TreeNode *rootp,ElementType e );
void Leaf( TreeNode *rootp,int *np );
int Depth( TreeNode *rootp );
void PreOrder( TreeNode *rootp );
void MidOrder( TreeNode *rootp );
void BackOrder( TreeNode *rootp );
/*================================ function body ================*/
/*------------------------------------ 建树 -------------------------*/
int CreateBinTree( TreeNode **rootp,ElementType **lp )
{
ElementType CurrElement;
if(*lp==NULL) return 0; /* 字符串不存在，返回 0 */
if(**lp==0) return 1; /* 字符串为空，返回1 */
CurrElement=*(*lp);
(*lp)++;
if(CurrElement=='.') { (*rootp)=NULL; return 1; }
if(!((*rootp)=(TreeNode *) malloc(sizeof(TreeNode))) ) return 0;
(*rootp)->data=CurrElement;
if(!CreateBinTree(&(*rootp)->LChild,lp)) return 0;
return CreateBinTree(&(*rootp)->RChild,lp);
}
/*------------------------------------------------------- 前序遍历子树--------*/
void PreOrder( TreeNode *rootp )
{
if(rootp==NULL) return;
printf(" %c",rootp->data); /* 打印父节点 */
if(rootp->LChild!=NULL) PreOrder(rootp->LChild); /* 打印左子树节点*/
if(rootp->RChild!=NULL) PreOrder(rootp->RChild); /* 打印右子树节点 */
return;
}
/*-------------------------------------------------------- 中序遍历子树 --------*/
void MidOrder( TreeNode *rootp )
{
if(rootp==NULL) return;
if(rootp->LChild!=NULL) MidOrder(rootp->LChild);
printf(" %c",rootp->data);
if(rootp->RChild!=NULL) MidOrder(rootp->RChild);
return;
}
/*------------------------------------------------------ 后序遍历子树--------*/
void BackOrder( TreeNode *rootp )
{
if(rootp==NULL) return;
if(rootp->LChild!=NULL) BackOrder(rootp->LChild);
if(rootp->RChild!=NULL) BackOrder(rootp->RChild);
printf(" %c",rootp->data);
return;
}
/*------------------------------------------------------- 查找节点--------*/
TreeNode *FindNode( TreeNode *rootp,ElementType e )
{
TreeNode *temp;
if(rootp==NULL) return NULL; /* 根节点为空，没有找到（空树） */
if(rootp->data==e) return rootp;
if(temp=FindNode(rootp->LChild,e)) return temp;
return FindNode(rootp->RChild,e);
}
/*------------------------------------------------------- 释放树所占内存空间 --------*/
void FreeTree( TreeNode *rootp )
{
if(!rootp) return;
FreeTree(rootp->LChild);
FreeTree(rootp->RChild);
free(rootp);
}
/*----------------------------------------------------- 查询父节点--------*/
TreeNode *FindParent( TreeNode *rootp,ElementType e )
{
TreeNode *temp;
if((rootp==NULL)||(rootp->LChild==NULL && rootp->RChild==NULL)) return NULL;
if((rootp->LChild && rootp->LChild->data==e)
||(rootp->RChild && rootp->RChild->data==e)) return rootp;
temp=FindParent(rootp->LChild,e);
if(temp) return temp;
return FindParent(rootp->RChild,e);
}
/*-------------------------------------------------------- 删除树节点 --------*/
int DelTree( TreeNode *rootp,ElementType e )
{
TreeNode *temp;
temp=FindParent(rootp,e);
if(!temp) return 0;
if(temp->LChild &&(temp->LChild->data==e))
{ FreeTree(temp->LChild);
temp->LChild=NULL;
}
else
{ FreeTree(temp->RChild);
temp->RChild=NULL;
}
return 1;
}
/*-------------------------------------------------------- 插入节点--------*/
int Insert( TreeNode *rootp,ElementType Curr,ElementType e,int CurrPos )
{
TreeNode *parent,*new,*temp;
if(!(parent=FindParent(rootp,Curr))) return 0;
if(!(new=(TreeNode *) malloc(sizeof(TreeNode)))) return 0;
new->data=e;
if(parent->LChild->data==Curr) { temp=parent->LChild; parent->LChild=new; }
temp=parent->RChild;
parent->RChild=new;
if(CurrPos==0) new->LChild=temp; new->RChild=NULL;
if(CurrPos==1) new->RChild=temp; new->LChild=NULL;
return 1;
}
/*----------------------------------------------------------- 计算叶子节点 --------*/
void Leaf( TreeNode *rootp,int *np )
{
if(rootp==NULL) return ;
if(rootp->LChild==NULL && rootp->RChild==NULL) { (*np)++; return; }
Leaf(rootp->LChild,np);
Leaf(rootp->RChild,np);
}
/*---------------------------------------------------------- 计算树高--------*/
int Depth( TreeNode *rootp )
{
int ld,rd; /* ld:左子树深度*/
/* rd: 右子树深度*/
if(rootp==NULL) return 0;
ld=Depth(rootp->LChild);
rd=Depth(rootp->RChild);
if(ld>rd) return ld+1;
else return rd+1;
}
/*=========================== The end of BinTreeh.h ======================*/
RE：如有注释错误请指正，算法很奇妙，希望共同探讨，共同进步……
|
