โปรแกรม C++ ตรวจสอบว่า Binary Tree หนึ่งเป็น Subtree ของอีก Binary Tree

Binary Tree เป็นโครงสร้างข้อมูลต้นไม้ที่แต่ละโหนดมีลูกสูงสุด 2 ตัว คือ left child และ right child

อัลกอริทึม

เริ่มต้น
  ฟังก์ชัน identical():
    รับพารามิเตอร์ 2 โหนด r1 และ r2
    ถ้า r1 และ r2 เป็น NULL คืนค่า true
    ถ้า r1 หรือ r2 เป็น NULL คืนค่า false
    คืนค่า (r1->d เท่ากับ r2->d และ เรียก Identical(r1->l, r2->l) และ Identical(r1->r, r2->r))
  ฟังก์ชัน Subtree(node *T, node *S):
    ถ้า S == NULL คืนค่า true
    ถ้า T == NULL คืนค่า false
    ถ้า Identical(T, S) คืนค่า true
    คืนค่า Subtree(T->l, S) หรือ Subtree(T->r, S)
สิ้นสุด

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

#include <iostream>
using namespace std;

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

bool Identical(struct n *r1, struct n *r2) {
    if (r1 == NULL && r2 == NULL) return true;
    if (r1 == NULL || r2 == NULL) return false;
    return (r1->d == r2->d && Identical(r1->l, r2->l) && Identical(r1->r, r2->r));
}

bool Subtree(struct n *T, struct n *S) {
    if (S == NULL) return true;
    if (T == NULL) return false;
    if (Identical(T, S)) return true;
    return Subtree(T->l, S) || Subtree(T->r, S);
}

struct n* newN(int d) {
    struct n* nod = (struct n*)malloc(sizeof(struct n));
    nod->d = d;
    nod->l = NULL;
    nod->r = NULL;
    return nod;
}

int main() {
    // Test case 1: ไม่ใช่ subtree
    struct n *T = newN(24);
    T->r = newN(2);
    T->r->r = newN(5);
    T->l = newN(7);
    T->l->l = newN(3);
    T->l->l->r = newN(40);
    T->l->r = newN(6);
    
    struct n *S = newN(20);
    S->r = newN(5);
    S->l = newN(3);
    S->l->r = newN(50);
    
    if (Subtree(T, S))
        cout << "given tree is subtree of Binary tree" << "\n";
    else
        cout << "given tree is not subtree of Binary tree" << "\n";
    
    // Test case 2: เป็น subtree
    struct n *T1 = newN(30);
    T1->r = newN(20);
    T1->r->r = newN(19);
    T1->l = newN(17);
    T1->l->l = newN(4);
    T1->l->l->r = newN(40);
    T1->l->r = newN(15);
    
    struct n *S1 = newN(17);
    S1->r = newN(15);
    S1->l = newN(4);
    S1->l->r = newN(40);
    
    if (Subtree(T1, S1))
        cout << "given tree is subtree of Binary tree";
    else
        cout << "given tree is not subtree of Binary tree";
    
    return 0;
}

ผลลัพธ์

given tree is not subtree of Binary tree
given tree is subtree of Binary tree