โปรแกรม C++ หา Lowest Common Ancestor ใน Binary Search Tree

Binary Tree เป็นต้นไม้ที่มีลูกสูงสุด 2 ตัว ระบุเป็น left child และ right child นี่คือโปรแกรม C++ สำหรับหา Lowest Common Ancestor (LCA) ใน Binary Tree

อัลกอริทึม

เริ่มต้น
  สร้างโครงสร้าง n ประกอบด้วยข้อมูล d, pointer ลูกซ้าย l และ pointer ลูกขวา r
  สร้างฟังก์ชันสร้างโหนดใหม่ newnode()
  เรียกฟังก์ชัน LCA() หา lowest common ancestor:
    สมมติโหนด n1 และ n2 อยู่ในต้นไม้
    ถ้า root เป็น NULL คืนค่า NULL
    ถ้า root ไม่เป็น NULL มี 2 กรณี:
      a) ถ้า n1 และ n2 น้อยกว่า root LCA อยู่ทางซ้าย
      b) ถ้า n1 และ n2 มากกว่า root LCA อยู่ทางขวา
สิ้นสุด

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

#include <iostream>
using namespace std;

struct n {
    int d;
    struct n* l, *r;
}*p = NULL;

struct n* newnode(int d) {
    p = new n;
    p->d = d;
    p->l = p->r = NULL;
    return p;
}

struct n *LCA(struct n* root, int n1, int n2) {
    if (root == NULL) return NULL;
    if (root->d > n1 && root->d > n2)
        return LCA(root->l, n1, n2);
    if (root->d < n1 && root->d < n2)
        return LCA(root->r, n1, n2);
    return root;
}

int main() {
    n* root = newnode(9);
    root->l = newnode(7);
    root->r = newnode(10);
    root->l->l = newnode(6);
    root->r->l = newnode(8);
    root->r->r = newnode(19);
    root->r->l->r = newnode(4);
    root->r->r->r = newnode(20);
    int n1 = 20, n2 = 4;
    struct n *t = LCA(root, n1, n2);
    cout << "Lowest Common Ancestor of 20 and 4 is: " << t->d << endl;
    n1 = 7, n2 = 6;
    t = LCA(root, n1, n2);
    cout << "Lowest Common Ancestor of 7 and 6 is: " << t->d << endl;
}

ผลลัพธ์

Lowest Common Ancestor of 20 and 4 is: 9
Lowest Common Ancestor of 7 and 6 is: 7