Даны два бинарных деревьев, найдем ли второй поддерева первого


Даны два бинарных деревьев, вы должны найти, является ли второй поддерева первого.

Первая попытка (перебором):

int issubtree(tree *tree1p, tree * tree2p)
{
    if (tree2p == NULL)
        return 1;

    if (tree1p == NULL)
        return 0;

    if (tree1p->data == tree2p->data)
        return (issubtree(tree1p->leftp,tree2p->leftp) 
                && (issubtree(tree1p->leftp,tree2p->leftp));
    else
        return (issubtree(tree1p->leftp,tree2p) || (issubtree(tree1p->rightp,tree2p));
}

Пожалуйста, дать обратную связь о правильности более эффективный код.



2663
5
задан 29 мая 2011 в 02:05 Источник Поделиться
Комментарии
2 ответа

Во-первых, что все "п"? Я предполагаю, что они означают указатель? Они глупы, от них избавиться.

Рассмотрим эти деревья:

     [A]                     [A]
/ \ / \
[B] [C] [D] [C]
/
[D]

Ваш код будет утверждать, что второе дерево поддеревом первого. Проблема в том, что вы не можете проверить левый/правый с использованием issubtree, потому что они должны быть точных совпадений не поддеревьев. Вам нужно отделить поддерево поиска из сопоставления:

int matches(tree * tree1, tree * tree2)
{
if(tree1 == tree2) return 1;
if(tree1 == NULL || tree2 == NULL) return 0;
if(tree1->data != tree2->data) return 0;
return matches(tree1->left, tree2->left) && matches(tree1->right, tree2->right);
}

int issubtree(tree *haystack, tree * needle)
{
if(tree1 == haystack) return 0;
if( matches(haystack, needle) ) return 1;
return issubtree(haystack->left, tree2) || issubtree(haystack->right, needle);
}

Для повышения эффективности, мы можем взглянуть на проблему по-другому. Мы можем выразить дерева обход в прямом порядке. Так что для первого выше дерева мы имеем:

A,B,D,(NULL),(NULL),(NULL),C,(NULL), (NULL)

Мы можем восстановить исходное дерево от этой последовательности. Кроме того, поддерево будет отображаться как подстрока в этой последовательности. Это означает, что мы можете просмотреть проблемы поддерево так же, как и проблема поиска подстроки. Это хорошо изученная проблема, и вы можете просмотреть различные алгоритмы для это здесь: http://en.wikipedia.org/wiki/String_searching_algorithm

8
ответ дан 29 мая 2011 в 07:05 Источник Поделиться

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

Если эти двоичные деревья поиска, есть по крайней мере один оптимизации вы можете сделать прямо с места в карьер: внутри еще блок вы не должны проверить обе стороны. Подумайте, как бы вы найти корневой узел поддерева в дерево.

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

0
ответ дан 29 мая 2011 в 07:05 Источник Поделиться