B_Tree 的数据结构

本文介绍: include//NULL的头文件#define m 3//BTree的阶每个节点至多有m棵子树且非终端节点至少有[m/2]棵子树int keynum;//节点中关键字的个数//关键字向量0号单元未用//子树指针向量//记录指针向量0号单元未用//均多留出一个单元分裂时使用BTNode *pt;//指向找到的节点int i;//在节点中的关键字序号1到mint tag;//1查找成功0查找失败}Result;//B树的查找结果类型。

头文件（结构体定义与函数声明）：

#ifndef BTREE_H_INCLUDED
#define BTREE_H_INCLUDED
#include<stdbool.h>
#include<stdlib.h>//NULL的头文件
#define m 3//BTree的阶每个节点至多有m棵子树且非终端节点至少有[m/2]棵子树
#define KeyType int
#define Record int
typedef enum{OK,ERROR}Status;
typedef struct BTNode
{
    int keynum;//节点中关键字的个数
    struct BTNode *parent;
    KeyType Key[m+1];//关键字向量0号单元未用
    struct BTNode* ptr[m+1];//子树指针向量
    Record* recptr[m+1];//记录指针向量0号单元未用
}BTNode,*BTree;//均多留出一个单元分裂时使用
typedef struct
{
    BTNode *pt;//指向找到的节点
    int i;//在节点中的关键字序号1到m
    int tag;//1查找成功0查找失败
}Result;//B树的查找结果类型

int Search(BTree p,KeyType K);
Result SearchBTree(BTree T,KeyType K);
void Insert(BTree q,int i,KeyType x,BTree ap);
void split(BTree q,int s,BTree ap);
void NewRoot(BTree *T,BTree p,KeyType x,BTree ap);
Status InsertBTree(BTree *T,KeyType K,BTree q,int i);
void Merge(BTree v);
void Delete(BTree v,int i);
Status DeleteBTree(BTree T,KeyType K);
#endif // BTREE_H_INCLUDED

函数实现

（需要在源文件即后缀为.c的文件中实现，否则编译器会报错，重复定义函数）：

#include "BTree.h"
#include<math.h>
int s=ceil((double)m/2);

int Search(BTree p,KeyType K)
{
    int i;
    for(i=1;i<=p->keynum&&p->Key[i]<K;i++);
    if(p->Key[i]!=K)i--;
    return i;
}
Result SearchBTree(BTree T,KeyType K)
{
    BTree p=T;
    BTree q=NULL;
    bool found=false;int i=0;
    while(p&&!found)
    {
        i=Search(p,K);//在p->Key中查找使得p->Key[i]<=K<p->Key[i+1]
        if(i>0&&p->Key[i]==K)found=true;
        else
        {
            q=p;p=p->ptr[i];
        }
    }
    if(found)return (Result){p,i,1};
    else return (Result){q,i,0};
}
void Insert(BTree q,int i,KeyType x,BTree ap)
{
    int j;
    for(j=q->keynum;j>i;j--)
    {
        q->Key[j+1]=q->Key[j];
        q->ptr[j+1]=q->ptr[j];
        q->recptr[j+1]=q->recptr[j];
    }
    q->Key[i+1]=x;
    q->ptr[i+1]=ap;
    q->recptr[i+1]=NULL;
    if(ap!=NULL)
    {
        ap->parent=q;
    }
    q->keynum++;
    return;
}
void split(BTree q,int s,BTree ap)
{//ap将成为q的右兄弟
    ap=(BTree)malloc(sizeof(BTNode));
    ap->keynum=m-s;
    ap->parent=q->parent;
    for(int j=s+1;j<=m;j++)
    {
        ap->Key[j-s]=q->Key[j];
        ap->ptr[j-s]=q->ptr[j];
        ap->recptr[j-s]=q->recptr[j];
        if(q->ptr[j]!=NULL)
        {
            q->ptr[j]->parent=ap;
        }
    }
    q->keynum=s;
    if(q->parent!=NULL)
    {
        Insert(q->parent,Search(q->parent,q->Key[s]),q->Key[s],ap);
    }
    return;
}

void NewRoot(BTree *T,BTree p,KeyType x,BTree ap)
{
    BTree root=(BTree)malloc(sizeof(BTNode));
    root->parent=NULL;
    root->keynum=1;
    root->Key[1]=x;
    root->ptr[0]=p;
    root->ptr[1]=ap;
    root->recptr[0]=NULL;
    root->recptr[1]=NULL;
    p->parent=root;
    ap->parent=root;
    *T=root;
    return;
}
Status InsertBTree(BTree *T,KeyType K,BTree q,int i)
{
    KeyType x=K;bool finished=false;
    BTree ap=NULL;
    while(q&&!finished)
    {
        Insert(q,i,x,ap);//将x和ap分别插入q->Key[i+1]和q->ptr[i+1]
        if(q->keynum<m)finished=true;
        else//分裂节点
        {//s=m/2向上取整
            split(q,s,ap);
            x=q->Key[s];//将q->Key[s+1,m],q->ptr[s,m]和q->recptr[s+1,m]移入新节点*ap
            q=q->parent;
            if(q)i=Search(q,x);
        }
    }
    if(!finished)//T是空树或根节点已经分裂为节点关*q和*ap
        NewRoot(T,q,x,ap);//生成含信息(T,x,ap)的新的根节点关*T,原T和ap为子树指针
    return OK;
}
void Merge(BTree v)
{
    if(v->keynum>=s-1)return;
    BTree pt=v->parent;
    if(pt==NULL)return;
    int j;
    for(j=0;j<=pt->keynum;j++)if(pt->ptr[j]==v)break;
    BTree r=NULL,l=NULL;
    if(j<pt->keynum)r=pt->ptr[j+1];
    if(j>0)l=pt->ptr[j-1];

    if(r)
    {
        int k=v->keynum;
        v->ptr[++k]=r->ptr[0];
        v->recptr[k]=pt->recptr[j+1];
        v->Key[k]=pt->Key[j+1];
        for(int i=1;i<=r->keynum;i++)
        {//合并时不一定是终端节点所以需要考虑子树的改变
            v->Key[++k]=r->Key[i];
            v->ptr[k]=r->ptr[i];
            v->recptr[k]=r->recptr[i];
        }
        v->keynum=k;
        for(k=j+1;k<pt->keynum;k++)
        {
            pt->Key[k]=pt->Key[k+1];
            pt->ptr[k]=pt->ptr[k+1];
            pt->recptr[k]=pt->recptr[k+1];
        }
        pt->keynum--;
        Merge(pt);
    }
    else
    {
        int k=++l->keynum;
        l->ptr[k]=v->ptr[0];
        l->recptr[k]=pt->recptr[j];
        l->Key[k]=pt->Key[j];
        for(int i=1;i<=v->keynum;i++)
        {
            l->Key[++k]=v->Key[i];
            l->ptr[k]=v->ptr[i];
            l->recptr[k]=v->recptr[i];
        }
        l->keynum=k;
        for(int i=j;i<pt->keynum;i++)
        {
            pt->Key[i]=pt->Key[i+1];
            pt->recptr[i]=pt->recptr[i+1];
            pt->ptr[i]=pt->ptr[i+1];
        }
        pt->keynum--;
        Merge(pt);
    }
    return;
}
void Delete(BTree v,int i)
{
    BTree pt=v->parent;
    if(v->keynum>=s||pt==NULL)
    {//该节点的关键字数目不小于s
        for(int j=i;j<v->keynum;j++)
        {
            v->Key[j]=v->Key[j+1];
            v->recptr[j]=v->recptr[j+1];
        }
        v->keynum--;
    }
    else if(v->keynum==s-1)
    {
        int j;
        for(j=0;j<=pt->keynum;j++)
        {
            if(pt->ptr[j]==v)break;
        }
        BTree r=NULL,l=NULL;
        if(j<pt->keynum)r=pt->ptr[j+1];
        if(j>0)l=pt->ptr[j-1];

        if(r&&r->keynum>s-1)
        {
            int k;
            for(k=i;k<v->keynum;k++)
            {//此时v一定是终端节点所以不用考虑子树
                v->Key[k]=v->Key[k+1];
                v->recptr[k]=v->recptr[k+1];
            }
            v->Key[k]=pt->Key[j+1];
            pt->Key[j+1]=r->Key[1];
            Delete(r,1);
        }
        else if(l&&l->keynum>s-1)
        {
            int k;
            for(k=i;k>1;k--)
            {
                v->Key[k]=v->Key[k-1];
                v->recptr[k]=v->recptr[k-1];
            }
            v->Key[k]=pt->Key[j];
            pt->Key[j]=l->Key[l->keynum];
            l->keynum--;
        }
        else
        {
            for(int k=i;k<v->keynum;k++)
            {
            v->Key[k]=v->Key[k+1];
            v->recptr[k]=v->recptr[k+1];
            }
            v->keynum--;
            Merge(v);
        }
    }
    return;
}
Status DeleteBTree(BTree T,KeyType K)
{
    Result res=SearchBTree(T,K);
    if(res.tag==0)return ERROR;
    BTree v=res.pt;
    int i=res.i;

    if(v->ptr[0]==NULL)
    {//终端节点
        Delete(v,i);
    }
    else
    {//存在于内部节点
        BTree p=v->ptr[0];
        while(p->ptr[0]!=NULL)p=p->ptr[0];
        v->Key[i]=p->Key[1];
        Delete(p,1);
    }
    return OK;
}

最后在main源文件中只需要包含该头文件即可使用定义的抽象数据类型：

#include <stdio.h>
#include <stdlib.h>
#include "BTree.h"

int main()
{
    printf("Hello world!n");
    return 0;
}

这里没有提供具体样例，可根据实际情况自行编写。

原文地址:https://blog.csdn.net/Xm041206/article/details/135518090

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_55159.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

头文件（结构体定义与函数声明）：

函数实现

相关文章

发表回复 取消回复

发表回复取消回复