ต้นไม้ฟิวชัน (Fusion Tree) เป็นโครงสร้างข้อมูลต้นไม้ที่นำอาเรย์สัมพันธ์ (associative array) ของจำนวนเต็ม w-bit มาใช้งาน นี่คือโปรแกรม C++ สำหรับการนำต้นไม้ฟิวชันมาใช้งาน ซึ่งสร้างอาเรย์ของจำนวนเต็ม 6-bit จากต้นไม้ทวิภาคที่กำหนดเป็นอินพุต
อัลกอริทึม
Begin รับจำนวนองค์ประกอบของต้นไม้และรับองค์ประกอบเหล่านั้น สร้างโครงสร้าง FusionTree เพื่อประกาศตัวแปร สร้างฟังก์ชัน init() สำหรับสร้างโหนด สร้างฟังก์ชัน traverse() เพื่อเดินทางต้นไม้ สร้างฟังก์ชัน sort() เพื่อจัดเรียงโหนดของต้นไม้ สร้างฟังก์ชัน split_child() เพื่อแยกโหนด สร้างฟังก์ชัน insert() เพื่อแทรกโหนดเข้าไปในต้นไม้ สร้างฟังก์ชัน main() เพื่อเรียก insert() เพื่อสร้างฟิวชันทรี จากนั้นเรียกฟังก์ชัน traverse เพื่อแสดงผลลัพธ์ 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
