Chương trình C++ kiểm tra cây nhị phân có phải cây con của cây nhị phân khác

Cây nhị phân là cấu trúc dữ liệu cây mà mỗi nút có tối đa hai con, định nghĩa là con trái và con phải.

Thuật toán

Bắt đầu
  Hàm identical(): nhận hai nút r1, r2.
    Nếu r1 và r2 là NULL thì trả về true.
    Nếu r1 hoặc r2 là NULL thì trả về false.
    Trả về (r1->d == r2->d và Gọi Identical(r1->l, r2->l) và Gọi Identical(r1->r, r2->r)).
  Hàm Subtree(node *T, node *S):
    Nếu S == NULL trả về true.
    Nếu T == NULL trả về false.
    Nếu Identical(T, S) trả về true.
    Trả về Subtree(T->l, S) hoặc Subtree(T->r, S).
Kết thúc.

Mã ví dụ

#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() {
    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 << "Cây cho là cây con của cây nhị phân" << "\n";
    else
        cout << "Cây cho không phải cây con của cây nhị phân" << "\n";
    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 << "Cây cho là cây con của cây nhị phân";
    else
        cout << "Cây cho không phải cây con của cây nhị phân";
    getchar();
    return 0;
}

Kết quả

Cây cho không phải cây con của cây nhị phân
Cây cho là cây con của cây nhị phân