Chương trình C++ triển khai cây Fusion (Fusion Tree)

Cây Fusion (Fusion Tree) là một cấu trúc dữ liệu cây triển khai mảng liên kết trên các số nguyên w-bit. Đây là chương trình C++ triển khai cây Fusion tạo ra mảng số nguyên 6-bit từ cây nhị phân đầu vào.

Thuật toán

Các hàm và đầu vào cần thiết:

Bắt đầu
  Nhập số phần tử của cây và các phần tử.
  Tạo cấu trúc FusionTree để khai báo biến.
  Tạo hàm init() để tạo nút.
  Tạo hàm traverse() để duyệt cây.
  Tạo hàm sort() để sắp xếp các nút của cây.
  Tạo hàm split_child() để tách nút con.
  Tạo hàm insert() để chèn nút vào cây.
  Tạo hàm main(), gọi insert() để tạo cây fusion rồi gọi traverse() để hiển thị kết quả.
Kết thúc

Mã ví dụ

#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 << "Nhập số phần tử cần chèn:\n";
    cin >> n;
    for(i = 0; i < n; i++) {
        cout << "Nhập phần tử:\n";
        cin >> t;
        insert(t);
    }
    cout << "Duyệt cây fusion đã xây dựng:\n";
    traverse(r);
    return 0;
}

Kết quả đầu ra

Nhập số phần tử cần chèn: 7
Nhập phần tử: 10
Nhập phần tử: 20
Nhập phần tử: 30
Nhập phần tử: 40
Nhập phần tử: 50
Nhập phần tử: 60
Nhập phần tử: 70
Duyệt cây fusion đã xây dựng:
10 20 30 40 50 60 70