C ++程序使用B树执行排序

2024-05-18 14:14:04 11

在这里，我们将看到如何使用B树获得排序的序列。B树是n元树。要获得排序的序列，我们可以创建一个B树，然后将数字添加到其中。此处B树最多可容纳5个节点。如果节点数增加，请分割节点并形成新级别。由于节点仅容纳少量元素（最多5个），因此我们正在使用Bubble排序技术对它们进行排序。由于元素的数量非常少，因此不会对其性能产生太大影响。

遍历树后，我们将获得不同节点的所有值。这些元素将以降序排列。

算法

遍历(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

排序(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

插入(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