โปรแกรม C++ หาขนาด Largest Independent Set (LIS) ใน Binary Tree

นี่คือโปรแกรม C++ สำหรับหาขนาดของ Largest Independent Set (LIS) ใน Binary Tree ที่กำหนดให้

อัลกอริทึม

เริ่มต้น
  สร้างโครงสร้าง n ประกอบด้วยข้อมูล d, pointer ลูกซ้าย l และ pointer ลูกขวา r
  สร้างฟังก์ชัน max() คืนค่าสูงสุดระหว่างสองจำนวนเต็ม
  สร้างฟังก์ชัน LIS() คืนค่าขนาด LIS ใน binary tree ที่กำหนด
    คำนวณขนาดไม่รวมโหนดปัจจุบัน: size_excl = LIS(root->l) + LIS(root->r)
    คำนวณขนาดรวมโหนดปัจจุบัน: size_incl = 1
    if (root->l) size_incl += LIS(root->l->l) + LIS(root->l->r)
    if (root->r) size_incl += LIS(root->r->l) + LIS(root->r->r)
    คืนค่าสูงสุดของสองขนาด
  สร้างฟังก์ชันสร้างโหนดใหม่ newnode()
สิ้นสุด

ตัวอย่างโค้ด

#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 << "Size of the Largest Independent Set is " << LIS(root);
    return 0;
}

ผลลัพธ์

Size of the Largest Independent Set is 5