数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究使用B树进行排序的C++程序
在这里，我们将学习如何使用B树获取排序后的序列。B树是n元树。为了获得排序后的序列，我们可以创建一个B树，然后将数字添加到其中。这里的B树最多可以容纳5个节点。如果节点数量增加，则分割节点并形成新的层级。由于节点最多只包含少量元素（例如5个），我们使用冒泡排序技术对其进行排序。由于元素数量非常少，因此不会对性能造成太大影响。
遍历树之后，我们将获得不同节点的所有值。这些元素将按非递减顺序排序。
算法
traverse(p)
输入：树节点p
输出：树的遍历序列
Begin for i in range 0 to n-1, do if p is not a leaf node, then traverse(child of p at position i) end if print the data at position i done if p is not a leaf node, then traverse(child of p at position i) end if End
sort(a, n)
输入：待排序的数组a，数组中元素的数量n
输出：排序后的数组
Begin for i in range 0 to n-1, do for j in range 0 to n-1, do if a[i] > a[j], then swap a[i] and a[j] end if done done End
split_node(x, i)
输入：要分割的节点x，i对于叶子节点为(-1)，否则为某个正值
输出：节点分割后的中间元素
Begin Create a node np3, and mark it as leaf node if i is -1, then mid := Data from position 2 of x Set the data at position 2 of x to 0 Reduce the number of data in x by 1 create a new node called np1, and mark it as non-leaf node mark x as leaf node Insert all of the nodes of x from position 3 to 5 into np3 Also insert all of the child reference of x from position 3 to 5 into np3 Remove the inserted elements from the node x insert mid into the first position of np1 make x as left child and np3 as right child of np1 increase the element count of np1, and make this as root. else y := the subtree at location i mid := data from position 2 of y Set the data at position 2 of y to 0 Reduce the number of data in y by 1 Insert all of the nodes of y from position 3 to 5 into np3 increase the element count of np3, and remove inserted elements from y add y child at position i, and add np3 at position i+1 end if End
insert(a)
输入：要插入的元素a。
输出：更新后的B树
Begin x := root if x is null, then create a root node and take root into x else if x is leaf node, and has 5 elements, then temp_node := split_child(x, -1) x := root i := find correct position to insert a x := child of x at position i else while x is not a leaf node, do i := find correct position to insert a if child of x at position i, has 5 elements, then temp_node := split_child(x, i) add temp_node data at position x->n of x else x := child of x at position i end if done end if end if add a into x at position x->n sort elements of x End
示例代码
#include<iostream>
using namespace std;
struct BTreeNode{ //create a node structure of a B-tree
int *data;
BTreeNode **child_ptr;
bool leaf;
int n;
}*root = NULL, *np = NULL, *x = NULL;
BTreeNode * getNode(){
int i;
np = new BTreeNode;
np->data = new int[5]; //set five data fiels and 6 link field
np->child_ptr = new BTreeNode *[6];
np->leaf = true; //initially the node is a leaf
np->n = 0;
for (i = 0; i < 6; i++) {
np->child_ptr[i] = NULL; //initialize all pointer to null
}
return np;
}
void traverse(BTreeNode *p) {
cout<<endl;
int i;
for (i = 0; i < p->n; i++) { //recursively traverse the entire b-tree
if (p->leaf == false){
traverse(p->child_ptr[i]);
}
cout << " " << p->data[i];
}
if (p->leaf == false) {
traverse(p->child_ptr[i]);
}
cout<<endl;
}
void sort(int *p, int n) {
for (int i = 0; i < n; i++) {
for (int j = i; j <= n; j++) {
if (p[i] > p[j]){
swap(p[i], p[j]);
}
}
}
}
int split_child(BTreeNode *x, int i){ //split the node into three nodes, one root and two children
int mid;
BTreeNode *np1, *np3, *y;
np3 = getNode(); //create a new leaf node called np3
np3->leaf = true;
if (i == -1) {
mid = x->data[2]; //get the middle element
x->data[2] = 0;
x->n--;
np1 = getNode();
np1->leaf = false;
x->leaf = true;
for (int j = 3; j < 5; j++) {
np3->data[j - 3] = x->data[j];
np3->child_ptr[j - 3] = x->child_ptr[j];
np3->n++;
x->data[j] = 0;
x->n--;
}
for (int j = 0; j < 6; j++) {
x->child_ptr[j] = NULL;
}
np1->data[0] = mid;
np1->child_ptr[np1->n] = x;
np1->child_ptr[np1->n + 1] = np3;
np1->n++;
root = np1;
} else {
y = x->child_ptr[i];
mid = y->data[2];
y->data[2] = 0;
y->n--;
for (int j = 3; j < 5; j++) {
np3->data[j - 3] = y->data[j];
np3->n++;
y->data[j] = 0;
y->n--;
}
x->child_ptr[i] = y;
x->child_ptr[i + 1] = np3;
}
return mid;
}
void insert(int a){ //insert into BTree
int i, tmp_node;
x = root;
if (x == NULL) {
root = getNode();
x = root;
} else {
if (x->leaf == true && x->n == 5){ //when the node is a leaf node and has 5 data
tmp_node = split_child(x, -1); //make a new level by spliting the node
x = root;
for (i = 0; i < (x->n); i++) {
if ((a > x->data[i]) && (a < x->data[i + 1])) {
i++;
break;
} else if (a < x->data[0]) {
break;
} else {
continue;
}
}
x = x->child_ptr[i];
} else {
while (x->leaf == false) {
for (i = 0; i < (x->n); i++) {
if ((a > x->data[i]) && (a < x->data[i + 1])) {
i++;
break;
} else if (a < x->data[0]) {
break;
} else {
continue;
}
}
if ((x->child_ptr[i])->n == 5) {
tmp_node = split_child(x, i);
x->data[x->n] = tmp_node;
x->n++;
continue;
} else {
x = x->child_ptr[i];
}
}
}
}
x->data[x->n] = a;
sort(x->data, 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 tree\n";
traverse(root);
}输出
enter the no of elements to be inserted 8 enter the element 54 enter the element 23 enter the element 98 enter the element 52 enter the element 10 enter the element 23 enter the element 47 enter the element 84 traversal of constructed tree 10 23 23 47 52 54 84 98
更新于：2019年7月30日
366 次查看
广告