实施融合树的C ++程序
融合树是一种树数据结构，可在w位整数上实现关联数组。这是一个实现融合树的C++程序，该树在给定的二进制树上生成6位整数数组作为输入。
算法
所需的功能和输入-
Begin Take the no of elements of the tree and take the elements. Create a structure FusionTree to declare variables. Create a function init() for creating the nodes. Create a function traverse() to traverse the tree. Create a function sort() to sort the nodes of the tree. Create a function split_child() to split the nodes. Create a function insert() to insert the nodes into the tree. Create a function main(), to call insert() to create the fusion tree and then call the function traverse to display the result. End
范例程式码
#include<iostream>
using namespace std;
struct FusionTree//declaration of nodes {
int *d;
FusionTree **child_ptr;
bool l;
int n;
}*r = NULL, *np = NULL, *x = NULL;
FusionTree* init()//cretae new node {
int i;
np = new FusionTree;
np->d = new int[6];
np->child_ptr = new FusionTree *[7];
np->l = true;
np->n = 0;
for (i = 0; i < 7; i++) {
np->child_ptr[i] = NULL;
}
return np;
}
void traverse(FusionTree *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(FusionTree *x, int i)//split the child {
int j, mid;
FusionTree *np1, *np3, *y;
np3 = init();// initialize new node
np3->l = true;
if (i == -1) {
mid = x->d[2];//calculate 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 fusion 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 fusion tree 10 20 30 40 50 60 70
热门推荐
10 新人红包祝福语简短精辟
11 幼师给毕业祝福语简短
12 生日高考祝福语妹妹简短
13 下飞机祝福语简短英文
14 元宵发客户祝福语简短
15 爸妈金婚文案祝福语简短
16 新郎朋友红包祝福语简短
17 虎年五一祝福语大全简短
18 出阁宴祝福语姐姐简短