数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C++ 程序来实现 B 树\n
B 树是二叉搜索树的推广，其中一个节点可以有多于两个子节点。它基本上是一个自我平衡树数据结构，可以维护已排序数据，并允许在对数时间内进行顺序访问、搜索、插入和删除。
这是一个 C++ 程序，用于实现 6 阶 B 树。
算法
Begin function insert() to insert the nodes into the tree: Initialize x as root. if x is leaf and having space for one more info then insert a to x. else if x is not leaf, do Find the child of x that is going to be traversed next. If the child is not full, change x to point to the child. If the child is full, split it and change x to point to one of the two parts of the child. If a is smaller than mid key in the child, then set x as first part of the child. Else second part of the child. When split the child, move a key from the child to its parent x. End
示例代码
#include<iostream>
using namespace std;
struct BTree//node declaration {
int *d;
BTree **child_ptr;
bool l;
int n;
}*r = NULL, *np = NULL, *x = NULL;
BTree* init()//creation of node {
int i;
np = new BTree;
np->d = new int[6];//order 6
np->child_ptr = new BTree *[7];
np->l = true;
np->n = 0;
for (i = 0; i < 7; i++) {
np->child_ptr[i] = NULL;
}
return np;
}
void traverse(BTree *p)//traverse the tree {
cout<<endl;
int i;
for (i = 0; i < p->n; i++) {
if (p->l == false) {
traverse(p->child_ptr[i]);
}
cout << " " << p->d[i];
}
if (p->l == false) {
traverse(p->child_ptr[i]);
}
cout<<endl;
}
void sort(int *p, int n)//sort the tree {
int i, j, t;
for (i = 0; i < n; i++) {
for (j = i; j <= n; j++) {
if (p[i] >p[j]) {
t = p[i];
p[i] = p[j];
p[j] = t;
}
}
}
}
int split_child(BTree *x, int i) {
int j, mid;
BTree *np1, *np3, *y;
np3 = init();//create new node
np3->l = true;
if (i == -1) {
mid = x->d[2];//find mid
x->d[2] = 0;
x->n--;
np1 = init();
np1->l= false;
x->l= true;
for (j = 3; j < 6; j++) {
np3->d[j - 3] = x->d[j];
np3->child_ptr[j - 3] = x->child_ptr[j];
np3->n++;
x->d[j] = 0;
x->n--;
}
for (j = 0; j < 6; j++) {
x->child_ptr[j] = NULL;
}
np1->d[0] = mid;
np1->child_ptr[np1->n] = x;
np1->child_ptr[np1->n + 1] = np3;
np1->n++;
r = np1;
} else {
y = x->child_ptr[i];
mid = y->d[2];
y->d[2] = 0;
y->n--;
for (j = 3; j <6 ; j++) {
np3->d[j - 3] = y->d[j];
np3->n++;
y->d[j] = 0;
y->n--;
}
x->child_ptr[i + 1] = y;
x->child_ptr[i + 1] = np3;
}
return mid;
}
void insert(int a) {
int i, t;
x = r;
if (x == NULL) {
r = init();
x = r;
} else {
if (x->l== true && x->n == 6) {
t = split_child(x, -1);
x = r;
for (i = 0; i < (x->n); i++) {
if ((a >x->d[i]) && (a < x->d[i + 1])) {
i++;
break;
} else if (a < x->d[0]) {
break;
} else {
continue;
}
}
x = x->child_ptr[i];
} else {
while (x->l == false) {
for (i = 0; i < (x->n); i++) {
if ((a >x->d[i]) && (a < x->d[i + 1])) {
i++;
break;
} else if (a < x->d[0]) {
break;
} else {
continue;
}
}
if ((x->child_ptr[i])->n == 6) {
t = split_child(x, i);
x->d[x->n] = t;
x->n++;
continue;
} else {
x = x->child_ptr[i];
}
}
}
}
x->d[x->n] = a;
sort(x->d, x->n);
x->n++;
}
int main() {
int i, n, t;
cout<<"enter the no of elements to be inserted\n";
cin>>n;
for(i = 0; i < n; i++) {
cout<<"enter the element\n";
cin>>t;
insert(t);
}
cout<<"traversal of constructed B tree\n";
traverse(r);
}输出
enter the no of elements to be inserted 7 enter the element 10 enter the element 20 enter the element 30 enter the element 40 enter the element 50 enter the element 60 enter the element 70 traversal of constructed B tree 10 20 30 40 50 60 70
更新日期： 2019 年 7 月 30 日
6k+ 浏览次数
广告