Блог

Чтобы проверить, является ли двоичное дерево поддеревом другого дерева, я подумал, что позволяет сохранять порядок и предварительный порядок обхода дерева в виде строк (например, присвоение символов каждому узлу), а затем выполнить сопоставление подстрок, чтобы проверить, является ли дерево поддеревом или нет. Сработает ли этот подход?

Не уверен, кто выбрал ответ @ genisage как правильный. Лучшим решением для этой проблемы является подход Inorder с использованием подстроки preorder / postorder. В примере @genisage упомянутые обходы предварительного порядка равны 1 2 и 2 2 1. 1 2 не является подстрокой 2 2 1, и ответ ложный.

нет, это не так. рассмотрим возможное поддерево, состоящее из корневого узла, содержащего 1, и левого дочернего узла, содержащего 2. И второе дерево с корнем 1, левым дочерним элементом 2 и правым дочерним элементом 1.

Ясно, что первое не является поддеревом второго, но ваш метод сказал бы, что это так, поскольку обходы по предварительному заказу равны 1 2 и 1 2 1, а обходы по порядку равны 2 1 и 2 1 1.

Вам нужно будет добавлять значения null, когда они встречаются, для дифференциации, делая обход предварительного порядка 1 2 нулевым и 1 2 1 и порядок 2 1 нулевым и 2 1 1, который не является поддеревом.

Учитывая два двоичных дерева, проверьте, является ли первое дерево поддеревом второго. Поддерево дерева T — это дерево S, состоящее из узла в T и всех его потомков в T. Поддерево, соответствующее корневому узлу, является целым деревом; поддерево, соответствующее любому другому узлу, называется надлежащим поддеревом.

Например, в следующем случае дерево S является поддеревом дерева T.

     Tree S
      10  
    /     
  4       6
   
    30


    Tree T
          26
        /   
      10     3
    /         
  4       6      3
   
    30
  

Пройдите по дереву T в режиме предварительного заказа. Для каждого посещенного узла в обходе проверьте, идентично ли поддерево, корневое с этим узлом, 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 amp;amp; 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   amp;amp;
        areIdentical(root1->left, root2->left) amp;amp;
        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