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

สมมติเรามี Binary Tree สองต้น เราต้องตรวจสอบว่า Tree ที่เล็กกว่าเป็น Subtree ของ Tree อีกต้นหนึ่งหรือไม่ พิจารณา Tree สองต้นดังภาพ:

Tree ที่สองเป็น Subtree ของ Tree แรก ในการตรวจสอบคุณสมบัตินี้ เราจะทำการ Traverse Tree แบบ Post-order แล้วตรวจสอบว่า Subtree ที่ rooted ณ โหนดนั้นเหมือนกับ Tree ที่สองหรือไม่ ถ้าเหมือนกันก็ถือว่าเป็น Subtree

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

#include <bits/stdc++.h>
using namespace std;

class node {
public:
    int data;
    node *left, *right;
};

bool areTwoTreeSame(node * t1, node *t2) {
    if (t1 == NULL && t2 == NULL)
        return true;
    if (t1 == NULL || t2 == NULL)
        return false;
    return (t1->data == t2->data && areTwoTreeSame(t1->left, t2->left) && areTwoTreeSame(t1->right, t2->right) );
}

bool isSubtree(node *tree, node *sub_tree) {
    if (sub_tree == NULL)
        return true;
    if (tree == NULL)
        return false;
    if (areTwoTreeSame(tree, sub_tree))
        return true;
    return isSubtree(tree->left, sub_tree) || isSubtree(tree->right, sub_tree);
}

node* getNode(int data) {
    node* newNode = new node();
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    node *real_tree = getNode(26);
    real_tree->right = getNode(3);
    real_tree->right->right = getNode(3);
    real_tree->left = getNode(10);
    real_tree->left->left = getNode(4);
    real_tree->left->left->right = getNode(30);
    real_tree->left->right = getNode(6);
    node *sub_tree = getNode(10);
    sub_tree->right = getNode(6);
    sub_tree->left = getNode(4);
    sub_tree->left->right = getNode(30);
    if (isSubtree(real_tree, sub_tree))
        cout << "Second tree is subtree of the first tree";
    else
        cout << "Second tree is not a subtree of the first tree";
}

ผลลัพธ์

Second tree is subtree of the first tree