12345678910
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();
}
|