資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究實現融合樹的 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
更新於： 30-Jul-2019
517 次瀏覽
廣告