फ्यूजन ट्री एक ट्री डेटा संरचना है जो w-बिट इंटीजर पर एक सहयोगी सरणी को लागू करती है। यह C++ प्रोग्राम दिए गए बाइनरी ट्री को इनपुट के रूप में लेकर 6-बिट इंटीजर की एक सरणी उत्पन्न करता है।
एल्गोरिदम
आवश्यक फ़ंक्शन और इनपुट:
शुरुआत
ट्री के तत्वों की संख्या लें और तत्वों को लें।
चर घोषित करने के लिए FusionTree संरचना बनाएं।
नोड्स बनाने के लिए init() फ़ंक्शन बनाएं।
ट्री को पार करने के लिए traverse() फ़ंक्शन बनाएं।
ट्री के नोड्स को सॉर्ट करने के लिए sort() फ़ंक्शन बनाएं।
नोड्स को विभाजित करने के लिए split_child() फ़ंक्शन बनाएं।
ट्री में नोड्स डालने के लिए insert() फ़ंक्शन बनाएं।
main() फ़ंक्शन बनाएं, insert() को कॉल करके फ्यूजन ट्री बनाएं और फिर traverse फ़ंक्शन को कॉल करके परिणाम प्रदर्शित करें।
समाप्ति
उदाहरण कोड
#include<iostream> using namespace std; struct FusionTree//नोड्स की घोषणा { int *d; FusionTree **child_ptr; bool l; int n; }*r = NULL, *np = NULL, *x = NULL; FusionTree* init()//नया नोड बनाएं { 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)//ट्री को पार करें { 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)//ट्री को सॉर्ट करें { 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)//चाइल्ड को विभाजित करें { int j, mid; FusionTree *np1, *np3, *y; np3 = init();// नया नोड इनिशियलाइज़ करें np3->l = true; if (i == -1) { mid = x->d[2];//मिड कैलकुलेट करें 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
