#include#include #include #include #define OK 1 #define ERROR 0 #define FALSE 0 #define TRUE 1 #define OVERFLOW -2 #define LH 1 #define RH -1 #define EH 0 #define GRADE 4 typedef int Status; typedef int KeyType; typedef struct { KeyType key; }ElemType; typedef struct { ElemType* elem; int length; }SSTable; typedef ElemType TElemType; typedef struct BiTNode { TElemType data; struct BiTNode* lchild, * rchild; }BiTNode, * BiTree; typedef struct BSTNode { TElemType data; int bf; struct BSTNode* lchild, * rchild; }BSTNode, * BSTree; typedef struct BTNode { int keynum; struct BTNode* parent; KeyType key[GRADE + 1]; struct BTNode* ptr[GRADE + 2]; ElemType* recptr[GRADE + 1]; }BTNode, * BTree; typedef struct { BTNode* ptr; int i; int tag; }Result; //查找表元素输入,关键字赋值以及比较 void InputTableElem(ElemType* e) { printf("请输入关键字信息n"); scanf("%d", &(e->key)); } void KeyWordAssign(KeyType* destination, KeyType source) { (*destination) = source; } void KeyWordPrint(KeyType key) { printf("%dn", key); } void TableElemAssign(ElemType* destination, ElemType source) { (*destination).key = source.key; } void TableElemPrint(ElemType e) { printf("%dn", e.key); } Status EQ(KeyType key1, KeyType key2) { if (key1 == key2) return TRUE; else return FALSE; } Status LT(KeyType key1, KeyType key2) { if (key1 < key2) return TRUE; else return FALSE; } Status LE(KeyType key1, KeyType key2) { if (key1 <= key2) return TRUE; else return FALSE; } Status MT(KeyType key1, KeyType key2) { if (key1 > key2) return TRUE; else return FALSE; } Status ME(KeyType key1, KeyType key2) { if (key1 >= key2) return TRUE; else return FALSE; } //静态查找表 Status CreatSSTable(SSTable* T, int n) { T->length = n; T->elem = (ElemType*)malloc(sizeof(ElemType) * (n + 1)); if (!T->elem) exit(OVERFLOW); for (int i = 1; i <= T->length; i++) { printf("请输入第%d个表项信息：n", i); InputTableElem(&(T->elem[i])); } return OK; } int Search_Seq(SSTable ST, KeyType key) //Sequence Search { KeyWordAssign(&(ST.elem[0].key), key); int i = ST.length; while (!EQ(ST.elem[i].key, key)) i--; return i; } int Search_Bin(SSTable ST, KeyType key) //Binary Search { int low = 1, high = ST.length; int mid = (low + high) / 2; while (low <= high) { if (EQ(ST.elem[mid].key, key)) return mid; if (MT(ST.elem[mid].key, key)) high = mid - 1; else low = mid + 1; } return 0; } void SecondOptimal(BiTree* T, SSTable S, int* sw, int low, int high) { int i = low; int w = sw[high] + sw[low - 1]; int min = abs(sw[high] - sw[low]); for (int j = low + 1; j <= high; j++) { if (abs(w - sw[j - 1] - sw[j]) < min) { i = j; min = abs(w - sw[i] - sw[i - 1]); } } (*T) = (BiTree)malloc(sizeof(BiTNode)); if (!(*T)) exit(OVERFLOW); KeyWordAssign(&((*T)->data.key), S.elem[i].key); if (i == low) (*T)->lchild = NULL; else SecondOptimal(&((*T)->lchild), S, sw, low, i - 1); if (i == high) (*T)->rchild = NULL; else SecondOptimal(&((*T)->rchild), S, sw, i + 1, high); } //队列函数 typedef BTNode* QElemType; typedef struct QNode { QElemType data; struct QNode* next; }QNode, * QueuePtr; typedef struct { QueuePtr head, tail; }LinkQueue; Status InitQueue(LinkQueue* Q) { Q->head = (QueuePtr)malloc(sizeof(QNode)); if (!Q->head) exit(OVERFLOW); Q->tail = Q->head; Q->head->next = NULL; return OK; } Status EnQueue(LinkQueue* Q, QElemType e) { QNode* p; p = (QNode*)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p->data = e; Q->tail->next = p; Q->tail = p; Q->tail->next = NULL; return OK; } Status DeQueue(LinkQueue* Q, QElemType* e) { if (Q->head == Q->tail) return ERROR; QNode* p = Q->head->next; (*e) = p->data; Q->head->next = p->next; if (p == Q->tail) Q->tail = Q->head; free(p); return OK; } Status QueueEmpty(LinkQueue Q) { if (Q.head == Q.tail) return TRUE; else return FALSE; } //B-树与B+树 void PrintBTree(BTree T) { if (!T) printf("B-树为空n"); else { printf("B树层序输出为：n"); LinkQueue Q; InitQueue(&Q); EnQueue(&Q, T); QElemType p; while (!QueueEmpty(Q)) { DeQueue(&Q, &p); int i = 0; while (i < p->keynum) { //KeyWordPrint(p->key[i]); TableElemPrint(*(p->recptr[i])); if (p->ptr[i]) EnQueue(&Q, p->ptr[i]); i++; } if (p->ptr[i]) EnQueue(&Q, p->ptr[i]); } } } int Search(BTree T, KeyType key) //找B-树的一个节点中找记录，若找到，为找到记录的位置，未找到则为插入位置 { //若树不存在，则位置为0 int i = 0; while (T && i < T->keynum && LT(T->key[i], key)) i++; return i; } Status SearchBTree(BTree T, KeyType key, Result* res) { BTNode* p = T, * q = NULL; int found = FALSE; int i = 0; while (p && (found == FALSE)) { i = Search(p, key); if (i < p->keynum && EQ(p->key[i], key)) found = TRUE; else { q = p; p = p->ptr[i]; } } if (found) { res->tag = TRUE; res->i = i; res->ptr = p; } else { res->tag = FALSE; res->i = i; res->ptr = q; } return OK; } Status CreatBTNode(BTree* T, ElemType e) { (*T) = (BTree)malloc(sizeof(BTNode)); if (!(*T)) exit(OVERFLOW); (*T)->keynum = 1; KeyWordAssign(&((*T)->key[0]), e.key); (*T)->recptr[0] = (ElemType*)malloc(sizeof(ElemType)); if (!(*T)->recptr[0]) exit(OVERFLOW); TableElemAssign((*T)->recptr[0], e); return OK; } int Split(BTree T1, BTree T2) { int split = ceil(GRADE / 2); T1->keynum = split - 1; T2->keynum = GRADE - split; split--; for (int i = split + 1; i < GRADE; i++) { KeyWordAssign(&(T2->key[i - split - 1]), T1->key[i]); T2->ptr[i - split - 1] = T1->ptr[i]; T2->recptr[i - split - 1] = T1->recptr[i]; } T2->ptr[GRADE - split - 1] = T1->ptr[GRADE]; return split; } Status InsertBTree(BTree* ROOT, BTree* T, int pos, ElemType e, BTree T1, BTree T2) { if (!(*T)) { CreatBTNode(ROOT, e); (*ROOT)->parent = NULL; (*ROOT)->ptr[pos] = T1; (*ROOT)->ptr[pos + 1] = T2; (*T) = (*ROOT); } else { if ((*T)->keynum < GRADE) { int i = (*T)->keynum - 1; while (i >= pos) { (*T)->ptr[i + 2] = (*T)->ptr[i + 1]; KeyWordAssign(&((*T)->key[i + 1]), (*T)->key[i]); (*T)->recptr[i + 1] = (*T)->recptr[i]; i--; } KeyWordAssign(&((*T)->key[pos]), e.key); (*T)->recptr[pos] = (ElemType*)malloc(sizeof(ElemType)); if (!(*T)->recptr[pos]) exit(OVERFLOW); TableElemAssign((*T)->recptr[pos], e); (*T)->ptr[pos] = T1; (*T)->ptr[pos + 1] = T2; (*T)->keynum++; } if ((*T)->keynum == GRADE) { BTNode* new; new = (BTNode*)malloc(sizeof(BTNode)); if (!new) exit(OVERFLOW); int splitpos = Split((*T), new); int i = Search((*T)->parent, (*T)->key[splitpos]); InsertBTree(ROOT, &((*T)->parent), i, *((*T)->recptr[splitpos]), (*T), new); new->parent = (*T)->parent; (*T) = (*T)->parent; } } return OK; } Status Delete_BT(BTree* ROOT, BTree* T, int pos) { int min = ceil(GRADE / 2) - 1; for (int i = pos; i <= (*T)->keynum - 2; i++) { KeyWordAssign(&((*T)->key[i]), (*T)->key[i + 1]); (*T)->recptr[i] = (*T)->recptr[i + 1]; } (*T)->keynum--; if ((*T) == (*ROOT)) { if ((*T)->keynum == 0) (*ROOT) = (*T)->ptr[0]; } else { if ((*T)->keynum < min) { BTNode* parent = (*T)->parent; BTNode* lsibling = NULL, * rsibling = NULL, * helpsibling = NULL; int childpos = Search(parent, (*T)->key[pos]); if (childpos - 1 > 0) lsibling = parent->ptr[childpos - 1]; if (childpos + 1 <= parent->keynum) rsibling = parent->ptr[childpos + 1]; int tag = 0; if (lsibling) { tag = 1; helpsibling = lsibling; } if (rsibling) { tag = 2; helpsibling = rsibling; } if (lsibling && lsibling->keynum > min) { tag = 3; helpsibling = lsibling; } if (rsibling && rsibling->keynum > min) { tag = 4; helpsibling = rsibling; } int last; switch (tag) { case 1: last = helpsibling->keynum; KeyWordAssign(&(helpsibling->key[last]), parent->key[childpos - 1]); helpsibling->recptr[last] = (ElemType*)malloc(sizeof(ElemType)); if (!helpsibling->recptr[last]) exit(OVERFLOW); helpsibling->recptr[last] = parent->recptr[childpos - 1]; helpsibling->keynum++; last++; for (int i = 0; i < (*T)->keynum; i++) { KeyWordAssign(&(helpsibling->key[last + i]), (*T)->key[i]); helpsibling->recptr[last + i] = (ElemType*)malloc(sizeof(ElemType)); if (!helpsibling->recptr[last + i]) exit(OVERFLOW); helpsibling->recptr[last + i] = (*T)->recptr[i]; helpsibling->keynum++; helpsibling->ptr[last + i] = (*T)->ptr[i]; } helpsibling->ptr[helpsibling->keynum] = (*T)->ptr[(*T)->keynum]; for (int i = parent->keynum - 1; i >= childpos; i--) parent->ptr[i] = parent->ptr[i + 1]; Delete_BT(ROOT, &parent, childpos - 1); break; case 2: last = (*T)->keynum; KeyWordAssign(&((*T)->key[last]), parent->key[childpos]); (*T)->recptr[last] = (ElemType*)malloc(sizeof(ElemType)); if (!(*T)->recptr[last]) exit(OVERFLOW); (*T)->recptr[last] = parent->recptr[childpos]; (*T)->keynum++; last++; for (int i = 0; i < helpsibling->keynum; i++) { KeyWordAssign(&((*T)->key[last + i]), helpsibling->key[i]); (*T)->recptr[last + i] = (ElemType*)malloc(sizeof(ElemType)); if (!(*T)->recptr[last + i]) exit(OVERFLOW); (*T)->recptr[last + i] = helpsibling->recptr[i]; (*T)->keynum++; (*T)->ptr[last + i] = helpsibling->ptr[i]; } (*T)->ptr[(*T)->keynum] = helpsibling->ptr[helpsibling->keynum]; for (int i = parent->keynum - 1; i >= childpos + 1; i--) parent->ptr[i] = parent->ptr[i + 1]; Delete_BT(ROOT, &parent, childpos); break; case 3: (*T)->ptr[(*T)->keynum + 1] = (*T)->ptr[(*T)->keynum]; for (int i = (*T)->keynum - 1; i > 0; i--) { KeyWordAssign(&((*T)->key[i + 1]), (*T)->key[i]); (*T)->recptr[i + 1] = (*T)->recptr[i]; (*T)->ptr[i + 1] = (*T)->ptr[i]; } KeyWordAssign(&((*T)->key[0]), parent->key[childpos - 1]); (*T)->recptr[0] = parent->recptr[childpos - 1]; (*T)->keynum++; last = helpsibling->keynum; KeyWordAssign(&(parent->key[childpos - 1]), helpsibling->key[last - 1]); parent->recptr[childpos - 1] = helpsibling->recptr[last - 1]; (*T)->ptr[0] = helpsibling->ptr[last]; Delete_BT(ROOT, &helpsibling, last - 1); break; case 4: last = (*T)->keynum; KeyWordAssign(&((*T)->key[last]), parent->key[childpos]); (*T)->recptr[last] = parent->recptr[childpos]; (*T)->keynum++; KeyWordAssign(&(parent->key[childpos]), helpsibling->key[0]); parent->recptr[childpos] = helpsibling->recptr[0]; (*T)->ptr[(*T)->keynum] = helpsibling->ptr[0]; for (int i = 0; i < helpsibling->keynum; i++) helpsibling->ptr[i] = helpsibling->ptr[i + 1]; Delete_BT(ROOT, &helpsibling, 0); break; default: return ERROR; } } } } Status DeleteBTree(BTree* ROOT, BTree* T, int pos) { if ((*T)->ptr[pos] != NULL) { Result res; SearchBTree((*T)->ptr[pos], (*T)->key[pos], &res); KeyWordAssign(&((*T)->key[pos]), res.ptr->key[res.i - 1]); (*T)->recptr[pos] = res.ptr->recptr[res.i - 1]; Delete_BT(ROOT, &(res.ptr), res.i - 1); } else Delete_BT(ROOT, T, pos); return OK; }
主函数：
//B-树主函数
int main()
{
BTree T = NULL, ROOT = NULL;
Result res;
int count = 10;
ElemType e;
while (count)
{
InputTableElem(&e);
SearchBTree(ROOT, e.key, &res);
T = res.ptr;
InsertBTree(&ROOT, &T, res.i, e, NULL, NULL);
count--;
}
PrintBTree(ROOT);
count = 10;
printf("--------------------------------nn");
while (count && ROOT)
{
printf("需要输入关键字以删除节点n");
InputTableElem(&e);
SearchBTree(ROOT, e.key, &res);
T = res.ptr;
DeleteBTree(&ROOT, &T, res.i);
PrintBTree(ROOT);
printf("--------------------------------nn");
count--;
}
return 0;
}
输入：（P245所示B树构造，然后将B树节点一一删去）
45 24 53 90 3 37 50 61 70 100
输出：
删除45：
以此类推以验证程序正确性
