1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树。（有些地方写的是B-树，注意不要误读
成"B减树"）
一棵M阶(M>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：
1. 根节点至少有两个孩子
2. 每个非根节点有[,M]个孩子
3. 每个非根节点有[ -1,M-1]个关键字，并且以升序排列
4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间
5. 所有的叶子节点都在同一层
ps： 是向上取整
B树是一种高度平衡树
这里以M=3为例进行解释
例如一个树中有数组int arr[]={3，4，10，15，16，20，30，35，36，40，45，46，50，76，77};那么它的结构如下图
B树的插入
例如插入20 30 10 ，画图分析如下
源代码
#pragma once
#include <vector>
#include <iostream>
using namespace std;
template<class K,int M>
struct BTreeNode
{
K _keys[M];//关键字数组，多一个便于分解
BTreeNode<K,M>* _subs[M+1];//连接子树的指针数组
BTreeNode<K,M>* _parent;
int size;//关键字个数
BTreeNode()
:size(0),_parent(NULL)
{
size_t i=0;
for (i=0;i<M;++i)
{
_keys[i]=K();
_subs[i]=NULL;
}
_subs[M]=NULL;
}
};
template<class K,int M>
class BTree
{
typedef BTreeNode<K,M> Node;
public:
BTree()
:_root(NULL)
{}
pair<Node*,int> Find(const K& key)
{
Node* cur=_root;
Node* parent=NULL;
while(cur)
{
int i=0;
while(i<cur->size)
{
if(cur->_keys[i]<key)
{
++i;
}
else if (cur->_keys[i]>key)
{
break;
}
else//找到关键字
{
return pair<Node*,int>(cur,i);
}
}
parent=cur;
cur=cur->_subs[i];
}
return pair<Node*,int>(parent,-1);//没有找到关键字返回-1；
}
bool Insert(const K& key)
{
if(_root==NULL)//空树的插入
{
_root=new Node;
_root->_keys[0]=key;
_root->size=1;
return true;
}
pair<Node*,int> ret=Find(key);
if(ret.second!=-1)//如果没有找到则插入，找到则不插入
return false;
Node* cur=ret.first;
K newkey=key;
Node* sub=NULL;
while(1)
{
InsertKey(cur,newkey,sub);
if(cur->size<M)//如果插入后没有满，则直接返回
return true;
size_t mid=cur->size/2;//插入后导致M满了，进行分裂
Node* tmp=new Node;
int j=0;
for(int i=mid+1;i<cur->size;++i)//拷贝key及孩子，连续分裂
{
tmp->_keys[j]=cur->_keys[i];
if (cur->_subs[i])
{
tmp->_subs[j]=cur->_subs[i];
tmp->_subs[j+1]=sub;
cur->_subs[i]=NULL;
tmp->_subs[j]->_parent=tmp;
tmp->_subs[j+1]->_parent=tmp;
}
tmp->size++;
cur->_keys[i]=K();
cur->size--;
j++;
}
if(cur->_parent==NULL)//分裂到根节点
{
_root=new Node;
_root->_keys[0]=cur->_keys[mid];
_root->_subs[0]=cur;
_root->_subs[1]=tmp;
_root->size++;
cur->_keys[mid]=K();
cur->size--;
cur->_parent=_root;
tmp->_parent=_root;
return true;
}
//没有分裂到根节点
newkey=cur->_keys[mid];
cur->_keys[mid]=K();
cur->size--;
sub=tmp;
cur=cur->_parent;//上移
}
return true;
}
void Inorder()
{
_Inorder(_root);
cout<<endl;
}
protected:
void InsertKey(Node* node,const K& key,Node* sub)
{
int i=node->size-1;
while (i>=0)
{
if(node->_keys[i]>key)
{
node->_keys[i+1]=node->_keys[i];
node->_subs[i+2]=node->_subs[i+1];
--i;
}
else
{
break;
}
}
node->_keys[i+1]= key;
node->_subs[i+2]=sub;
if(sub)
sub->_parent=node;
node->size++;
}
void _Inorder(Node* root)//打印完一个子树再递归下一步进行打印
{
if(root==NULL)
return;
_Inorder(root->_subs[0]);
for (int i=0;i<root->size;i++)
{
// _Inorder(root->_subs[i]);
cout<<root->_keys[i]<<" ";
}
for(int i=1;i<M;++i)
{
_Inorder(root->_subs[i]);
}
}
private:
Node* _root;
};
void testBTree()
{
BTree<int,3> bt;
int arr[]={53,75,139,49,145,36,101};
for(int i=0;i<sizeof(arr)/sizeof(arr[0]);++i)
{
bt.Insert(arr[i]);
}
bt.Inorder();
}
#include "BTree.h"
#include <cstdlib>
int main()
{
testBTree();
system("pause");
return 0;
}
中序遍历结果为
