두 개의 이진 트리가 있다고 가정합니다. 더 작은 트리가 다른 이진 트리의 하위 트리인지 여부를 확인해야 합니다. 이 두 나무가 주어졌다고 생각해 보십시오.
두 그루의 나무가 있습니다. 두 번째 트리는 첫 번째 트리의 하위 트리입니다. 이 속성을 확인하기 위해 후순위 방식으로 트리를 탐색한 다음 이 노드를 기반으로 하는 하위 트리가 두 번째 트리와 동일하면 하위 트리입니다.
예시
#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