이진 트리가 다른 이진 트리의 서브 트리인지 확인

Question

이진 트리가 다른 트리의 하위 트리인지 확인하려면 트리의 inorder 및 preorder 순회를 문자열 (각 노드에 문자를 할당하는 것과 같이)로 저장할 수있게 해줍니다. 그런 다음 트리가 하위 트리인지 확인하기 위해 부분 문자열 일치를 수행하십시오. 이 접근 방식이 효과가 있습니까?

Answer 1

없이 일치하면 순회 방문한 모든 노드에 대해, 그렇지 않은 것 참조. 1을 포함하는 루트 노드와 2를 포함하는 왼쪽 하위로 구성된 가능한 하위 트리를 고려하십시오. 루트 2, 왼쪽 하위 2 및 오른쪽 하위 1이있는 두 번째 트리를 고려하십시오.

첫 번째 하위 트리는 하위 트리가 아닙니다. 두 번째지만 당신의 방법은 선주문 통과가 2 1 2 1 2이고 inorder 순회가 2 1 및 2 2 1이기 때문에 말할 것입니다.

아마도 선주문과 엽서가 효과가 있을지 모르겠습니다. 지금 반례의 예를 들었지만 나는 그것을 증명할 수 없다.

Answer 2

두 개의 이진 트리가있는 경우 첫 번째 트리가 두 번째 트리의 하위 트리인지 확인하십시오. 트리 T의 서브 트리는 T의 노드와 T의 모든 자손으로 구성된 트리 S입니다. 루트 노드에 해당하는 서브 트리는 전체 트리입니다. 다른 노드에 해당하는 서브 트리를 적절한 서브 트리라고합니다.

예를 들어, 다음과 같은 경우에, 트리 S는 예약 주문 방식으로 트리 T 트래버스 나무 T.

Tree S 
     10 
    / \ 
    4  6 
    \ 
    30 


    Tree T 
      26 
     / \ 
     10  3 
    / \  \ 
    4  6  3 
    \ 
    30 

의 하위 트리입니다. 이 노드를 루트로하는 서브 트리가 S.

#include <stdio.h> 
#include <stdlib.h> 

/* A binary tree node has data, left child and right child */ 
struct node 
{ 
    int data; 
    struct node* left; 
    struct node* right; 
}; 

/* A utility function to check whether trees with roots as root1 and root2 are identical or not */ 
bool areIdentical(struct node * root1, struct node *root2) 
{ 
    /* base cases */ 
    if(root1 == NULL && root2 == NULL) 
     return true; 

    if(root1 == NULL || root2 == NULL) 
     return false; 

    /* Check if the data of both roots is same and data of left and right subtrees are also same */ 
    return (root1->data == root2->data && 
     areIdentical(root1->left, root2->left) && 
     areIdentical(root1->right, root2->right)); 
} 


/* This function returns true if S is a subtree of T, otherwise false */ 
bool isSubtree(struct node *T, struct node *S) 
{ 
    /* base cases */ 
    if (S == NULL) 
     return true; 

    if (T == NULL) 
     return false; 

    /* Check the tree with root as current node */ 
    if (areIdentical(T, S)) 
     return true; 

    /* If the tree with root as current node doesn't match then 
    try left and right subtrees one by one */ 
    return isSubtree(T->left, S) || 
     isSubtree(T->right, S); 
} 


/* Helper function that allocates a new node with the given data 
    and NULL left and right pointers. */ 
struct node* newNode(int data) 
{ 
    struct node* node = (struct node*)malloc(sizeof(struct node)); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 
    return(node); 
} 

/* Driver program to test above function */ 
int main() 
{ 
    /* Construct the following tree 
      26 
     / \ 
     10  3 
    / \  \ 
    4  6  3 
    \ 
    30 
*/ 
    struct node *T  = newNode(26); 
    T->right    = newNode(3); 
    T->right->right  = newNode(3); 
    T->left    = newNode(10); 
    T->left->left   = newNode(4); 
    T->left->left->right = newNode(30); 
    T->left->right  = newNode(6); 

/* Construct the following tree 
     10 
    / \ 
    4  6 
    \ 
    30 
*/ 
    struct node *S = newNode(10); 
    S->right   = newNode(6); 
    S->left   = newNode(4); 
    S->left->right = newNode(30); 


    if(isSubtree(T, S)) 
     printf("Tree S is subtree of tree T"); 
    else 
     printf("Tree S is not a subtree of tree T"); 

    getchar(); 
    return 0; 
} 

Output: Tree S is subtree of tree T

Answer 3

누가 @ genisage의 답변을 옳은 것으로 선택했는지 확신 할 수 없습니다. 선주문/후순위 하위 문자열 방식을 사용하는 경우이 문제에 대한 최상의 해결책입니다. 언급 된 @genisage 예에서 pre-order 순회는 1 2와 2 2 1입니다. 1 2는 2 2 1의 부분 문자열이 아니며 그 답은 거짓입니다.