Chương trình C++ tìm kích thước tập hợp độc lập lớn nhất (LIS) trong cây nhị phân

Đây là chương trình C++ tìm kích thước của tập hợp độc lập lớn nhất (Largest Independent Set - LIS) trong một cây nhị phân cho trước.

Thuật toán

Bắt đầu.
  Tạo cấu trúc n khai báo dữ liệu d, con trỏ trái l và con trỏ phải r.
  Gọi hàm max() trả về max của hai integer.
  Tạo hàm LIS() trả về kích thước tập hợp độc lập lớn nhất trong cây nhị phân.
    Tính kích thước loại trừ nút hiện tại
    int size_excl = LIS(root->l) + LIS(root->r)
    Tính kích thước bao gồm nút hiện tại
    int size_incl = 1;
    if (root->l)
      size_incl += LIS(root->l->l) + LIS(root->l->r)
    if (root->right)
      size_incl += LIS(root->r->l) + LIS(root->r->r)
    Trả về max của hai kích thước.
  Tạo hàm newnode().
Kết thúc.

Mã ví dụ

#include <iostream>
using namespace std;

struct n {
    int d;
    int lis;
    struct n *l, *r;
};

int max(int x, int y) {
    return (x > y) ? x : y;
}

int LIS(struct n *root) {
    if (root == NULL)
        return 0;
    if (root->lis)
        return root->lis;
    if (root->l == NULL && root->r == NULL)
        return (root->lis = 1);
    int lis_excl = LIS(root->l) + LIS(root->r);
    int lis_incl = 1;
    if (root->l)
        lis_incl += LIS(root->l->l) + LIS(root->l->r);
    if (root->r)
        lis_incl += LIS(root->r->l) + LIS(root->r->r);
    root->lis = max(lis_incl, lis_excl);
    return root->lis;
}

struct n* newnode(int d) {
    struct n* t = (struct n *) malloc(sizeof(struct n));
    t->d = d;
    t->l = t->r = NULL;
    t->lis = 0;
    return t;
}

int main() {
    struct n *root = newnode(30);
    root->l = newnode(20);
    root->l->l = newnode(10);
    root->l->r = newnode(7);
    root->l->r->l = newnode(9);
    root->l->r->r = newnode(6);
    root->r = newnode(50);
    root->r->r = newnode(26);
    cout << "Kích thước tập hợp độc lập lớn nhất là " << LIS(root);
    return 0;
}

Kết quả

Kích thước tập hợp độc lập lớn nhất là 5