B-

B-树 ////////////////////////////////////////////////////////////////////////// // File: b-tree.h // Date: 2005 / 07 / 10 // Author: centaurus // Email: vim_user@126.com ////////////////////////////////////////////////////////////////////////// #ifndef __BSubtractTree_H__ #define __BSubtractTree_H__ #include using namespace std; template class BSubtractTree { private: //data: 0 1 2 ... // | | | | //child: 0 1 2 3 ... typedef struct TNode // 树结点，如上结构 { T *data; // 结点数据序列，假设增序排列 struct TNode **child; // 子结点指针数组 struct TNode *parent; // 父结点指针 int key_num; // 结点数据个数 }TNode; typedef struct Location // 查找关键字结果 { TNode *node; // 所在结点 int offset; // 所在结点数据偏移量 }Location; private: TNode *head; // 树头 int tnode_num; const int LIMIT; // 阶，结点数据最多个数 T *array; const int SIZE; private: // 得到一新结点 TNode *GetNode(); // 在指定结点p、结点数据偏移量*i处插入关键字 void Add(TNode *p, int *i, T key, TNode *new_node); // 自结点p、分割点partition以右的数据，分割出一新结点 void Split(TNode *p, int partition, TNode **new_node); // 修改head void NewRoot(T key, TNode *new_node); // 在结点数据序列中查找关键字 int SearchKey(TNode *p, T key); // 查找树结点 bool SearchNode(T key, Location *position); // 中序遍历显示树结点 void InOrder(TNode *n); // 先序遍历 void PreOrder(TNode *n); public: BSubtractTree(); BSubtractTree(T *a, int s, int l); // 在查找结果处插入关键字 void Insert(T key, Location *position); void InOrderShow(); void PreOrderShow(); void Delete(T key, Location *position); ~BSubtractTree(); }; #endif ////////////////////////////////////////////////////////////////////////// // File: b-tree.h // Date: 2005 / 07 / 10 // Author: centaurus // Email: vim_user@126.com ////////////////////////////////////////////////////////////////////////// #ifndef __BSubtractTree_Fun_Def_H__ #define __BSubtractTree_Fun_Def_H__ #include "b-tree.h" template int BSubtractTree:: SearchKey(TNode *p, T key) { int i; if(key > p->data[p->key_num - 1]) // 关键字小于序列最小值 return p->key_num; else if(key < p->data[0]) // 大于最大值 return 0; else if(key >= p->data[0] && key <= p->data[p->key_num - 1]) // 关键字在序列中 { for(i = 0; i < p->key_num; i++) { if(key <= p->data[i]) // 返回等于或小于序列数据的下标 { break; } } } return i; } template bool BSubtractTree:: SearchNode(T key, Location *position) { TNode *p = head; TNode *pre = NULL; bool found = false; int i = 0; while(p && !found) { i = SearchKey(p, key); if(i > 0 && p->data[i] == key) found = true; else { pre = p; p = p->child[i]; } } if(found) // 找到返回true，offset指向该值下标 { position->node = p; position->offset = i; return true; } else // 未找到，offset指向第一个大于key的下标 { position->node = pre; position->offset = i; return false; } } template BSubtractTree:: TNode* BSubtractTree:: GetNode() { int i; TNode *temp = new TNode; temp->parent = NULL; temp->key_num = 0; temp->data = new T [LIMIT]; for(i = 0; i < LIMIT; i++) { temp->data[i] = 0; } temp->child = new TNode* [LIMIT + 1]; for(i = 0; i < LIMIT + 1; i++) { temp->child[i] = NULL; } tnode_num++; return temp; } template void BSubtractTree:: Add(TNode *p, int *i, T key, TNode *new_node) { int _i; for(_i = p->key_num; _i > *i; _i--) // 将数据序列*i及其以后数值向后挪一位 { p->data[_i] = p->data[_i - 1]; } p->data[_i] = key; // 在*i位插入关键字 for(_i = p->key_num + 1; _i > *i + 1; _i--) // 挪动child指针数组 { p->child[_i] = p->child[_i - 1]; } p->child[_i] = new_node; // 插入子结点，子结点为NULL或分割结点 p->key_num++; if(new_node) new_node->parent = p; } template void BSubtractTree:: Split(TNode *p, int partition, TNode **new_node) { *new_node = GetNode(); // 存放新结点地址 int _i; int j = 0; int m = p->key_num; for(_i = partition + 1; _i < m; _i++) { (*new_node)->data[j++] = p->data[_i]; (*new_node)->key_num++; p->data[_i] = 0; p->key_num--; } j = 0; for(_i = partition + 1; _i < m + 1; _i++) { (*new_node)->child[j] = p->child[_i]; if(p->child[_i]) (*new_node)->child[j]->parent = *new_node; p->child[_i] = NULL; j++; } } template void BSubtractTree:: NewRoot(T key, TNode *new_node) { TNode *temp = GetNode(); temp->data[0] = key; temp->key_num = 1; temp->child[0] = head; temp->child[1] = new_node; if(head) head->parent = temp; if(new_node) new_node->parent = temp; head = temp; } template void BSubtractTree:: Insert(T key, Location *position) { TNode *p = position->node; int i = position->offset; T k = key; int partition; TNode *new_node = NULL; bool condition = false; while(p && !condition) { Add(p, &i, k, new_node); if(p->key_num < LIMIT) condition = true; else { partition = LIMIT / 2; Split(p, partition, &new_node); k = p->data[partition]; p->data[partition] = 0; p->key_num--; p = p->parent; if(p) i = SearchKey(p, k); } } if(!condition) // 为空树或将树头结点进行了分割 NewRoot(k, new_node); } template BSubtractTree:: BSubtractTree() : SIZE(0), LIMIT(0) { head = NULL; tnode_num = 0; array = NULL; } template BSubtractTree:: BSubtractTree(T *a, int s, int l) : SIZE(s), LIMIT(l) { head = NULL; tnode_num = 0; int i; Location position; array = new T [SIZE]; for(i = 0; i < SIZE; i++) { array[i] = a[i]; } for(i = 0; i < SIZE; i++) { if(!SearchNode(array[i], &position)) // 查找关键字失败则插入关键字 { Insert(array[i], &position); } } } template void BSubtractTree:: Delete(T key, Location *position) { } template BSubtractTree:: ~BSubtractTree() { Location position; for(int i = 0; i < SIZE; i++) { if(SearchNode(array[i], &position)) { Delete(array[i], &position); } } } template void BSubtractTree:: InOrder(TNode *n) { if(n) { int i; for(i = 0; i < n->key_num + 1; i++) { InOrder(n->child[i]); if(i < n->key_num) cout << n->data[i] << endl; } } } template void BSubtractTree:: PreOrder(TNode *n) { if(n) { int i; cout << "NodeAddress:" << n << " "; cout << "NodeParent:" << n->parent <key_num; i++) { cout << "DataKey " << i << " : " << n->data[i] << " | "; } cout << "\n"; for(i = 0; i < n->key_num + 1; i++) { cout << "Child[" << i <<"] : " << n->child[i] << " | "; } cout << "\n\n"; for(i = 0; i < n->key_num + 1; i++) { PreOrder(n->child[i]); } } } template void BSubtractTree:: InOrderShow() { cout << "InOrder List : " << endl; InOrder(head); } template void BSubtractTree:: PreOrderShow() { cout << "PreOrder List : " << endl; PreOrder(head); } #endif ////////////////////////////////////////////////////////////////////////// // File: b-tree.h // Date: 2005 / 07 / 10 // Author: centaurus // Email: vim_user@126.com ////////////////////////////////////////////////////////////////////////// #include using namespace std; #include "b-tree_fun_def.cpp" void main() { int a[10] = ; BSubtractTree test(a, 10, 3); test.InOrderShow(); //test.PreOrderShow(); }

原文转自：http://www.ltesting.net