Chương trình C++ tìm tổ tiên chung thấp nhất trong cây tìm kiếm nhị phân

Cây nhị phân là cây có tối đa hai con, chỉ định là con trái và con phải. Đây là chương trình C++ tìm tổ tiên chung thấp nhất (Lowest Common Ancestor - LCA) trong cây nhị phân.

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.
  Tạo hàm newnode().
  Gọi hàm LCA() tìm tổ tiên chung thấp nhất:
    Giả sử nút n1 và n2 tồn tại trong cây.
    Nếu root là null, trả về NULL.
    Nếu root không null có hai trường hợp.
      a) Nếu cả n1 và n2 nhỏ hơn root, LCA nằm bên trái.
      b) Nếu cả n1 và n2 lớn hơn root, LCA nằm bên phải.
Kết thúc.

Mã ví dụ

#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 << "Tổ tiên chung thấp nhất của 20 và 4 là: " << t->d << endl;
    n1 = 7, n2 = 6;
    t = LCA(root, n1, n2);
    cout << "Tổ tiên chung thấp nhất của 7 và 6 là: " << t->d << endl;
}

Kết quả

Tổ tiên chung thấp nhất của 20 và 4 là: 9
Tổ tiên chung thấp nhất của 7 và 6 là: 7