Бинарное дерево содержится в другом бинарном дереве - C

Question

Так что у меня только что было интервью, которое, я уверен, я испортил по-королевски. Меня бросили в кучу вопросов, и у меня не было достаточно времени, чтобы ответить на последний.

После того, как все начальные вопросы были правильными, меня попросили написать функцию, которая бы определяла, содержится ли двоичное дерево b в другом двоичном дереве a. До этого я правильно закодировал вопрос, в котором он попросил меня написать функцию, чтобы определить, равны ли два дерева:

int sameTree(struct node *a, struct node *b){
//both empty = TRUE
if(a == NULL && b == NULL)
    return TRUE;
//both not empty, compare them
else if(a != NULL && b != NULL){
    return(
    a->data == b->data &&
    sameTree(a->left, b->left) &&
    sameTree(a->right, b->right)
    );
}
//one empty, one not = FALSE
else 
    return FALSE;

}

Тьфу. Просто для того, чтобы очистить мою совесть, опять же, как бы вы определили, находится ли дерево b внутри дерева a?

Спасибо за любую помощь, ребята.

Answer 1

int in(struct node* outer, struct node* inner){
    if(inner == null){
        return true; // say every tree contains the empty tree
    } else if(outer == null){
        return false;
    } else if(same(outer, inner)){
        return true;
    } else return in(outer->left, inner) || in(outer->right, inner);
}

Мы не должны использовать sameTree ОП, а скорее эту функцию:

int same(struct node* outer, struct node* inner){
    return !inner || outer && outer->data == inner->data && same(outer->left, inner->left) && same(outer->right, inner->right);
}

Или, более подробно,

int same(struct node* outer, struct node* inner){
    if(inner == null){
        return true;
    } else if(outer == null){
        return false;
    } else if(outer->data == inner->data){
        return same(outer->left, inner->left) && same(outer->right, inner->right);
    } else return false;
}

Answer 2

Чтобы проверить, содержится ли дерево A как есть в дереве B, найдите узел C в B такой, что C.data == A.data. Если такого узла нет, A не содержится в B. Если существует C, проверьте, равны ли A и C, используя модифицированную функцию sameTree - которая игнорирует несоответствия между нулевыми дочерними элементами A и ненулевыми дочерними элементами C (возвращает true, если A.left / right нулевой).

Спасибо @Kobi за исправление.

Answer 3

Предполагается, что вы хотите одно и то же дерево с одинаковой структурой, содержащееся в a:

Например, если b равно нулю, а a нет, a содержит b (вы должны проверить это в вашем последнем else). Во-вторых, это не бинарные деревья поиска (не отсортированные), поэтому чтобы проверить, находится ли b внутри a, следует также пройти a (при условии, что вы переименовали функцию):

int containsTree(struct node *a, struct node *b){
//both empty = TRUE
if(a == NULL && b == NULL)
        return TRUE;
//both not empty, compare them

else if(a != NULL && b != NULL){
    return(
      // sameTree should be changed to allow nulls, as below
      sameTree(a, b)
      // check recursively
      || containsTree(a->left, b)
      || containsTree(a->right, b)
    );
//one empty, one not = FALSE
else 
    return B == NULL;