Доказательство того, что одно двоичное дерево является поддеревом другого

Question

Предположим, у вас есть два бинарных дерева, и вы хотите знать, является ли это поддеревом другого. Одно из решений состоит в том, чтобы получить обход ордеров и предзаказов обоих деревьев и проверить, являются ли обходы поддерева-кандидата подстроками соответствующего обхода для другого дерева. Я прочитал несколько сообщений об этом посты об этом решении. Один из discussion показывает, что необходимы и порядок обхода предварительного заказа. Может кто-нибудь объяснить, почему их достаточно? Почему случается, что если обход порядка и предзаказов дерева2 является подстрокой из дерева дерева1, то tree2 является поддеревом дерева1?

Answer 1

Q: Одно обсуждение показывает, что Симметричное И обход оба необходимы. Может кто-нибудь объяснить, почему их достаточно?

Из-за простой факт, что можно однозначно реконструировать бинарное дерево из этих двух прохождений (или заказовМой и postorder, а). Проверьте этот пример:

Inorder : [1,2,3,4,5,6] 
    Preorder : [4,2,1,3,5,6] 

С предварительного заказа вы знаете, что 4 является корнем дерева. Из Симметричных, вы можете определить левое и правое поддерево, и вы приступите рекурсивны с этой точкой:

    4 
      / \ 
    Left subtree  Right subtree 
    Inorder : [1,2,3] Inorder : [5,6] 
    Preorder: [2,1,3] Preorder: [5,6] 

Проверить более подробную информацию в этой превосходной статье: Reconstructing binary trees from tree traversal. Поскольку эти две сериализации (траверсы фактически сериализуют дерево в строку) объединенного вместе дерева должны быть уникальными для двоичного дерева, мы получаем, что одно дерево является поддеревом другого тогда и только тогда, когда эти обходы являются подстроками других двух сериализаций.

Answer 2

Люди согласились, что бинарное дерево может представлять порядок на своих узлах по левому/правому отношению. Это означает, что левая часть появляется перед правой частью. Вы можете назвать деревья эквивалентными, если порядок одинаков. Таким образом, строка в последовательности представляет порядок, и если вы хотите проверить эквивалентность, то достаточно проверить только по порядку (по определению). Но когда вы хотите проверить полное равенство деревьев, мы должны найти способ, как мы можем различать эквивалентные деревья. Например, это может быть проверка порядка уровня. Но для порядка поддеревьев порядок не подходит, потому что строка порядка уровня для поддерева разделяется. Для предварительного заказа вы пропустите корневую форму корня перед другими частями дерева.

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

1) Значение узла одного дерева отличается от другого. Это означает, что строки предварительного заказа отличаются, потому что вы ходите по дереву в предварительном порядке.

2) Дети подписи (нет детей, только слева, только справа, оба ребенка). Но в этой ситуации легко понять, что порядок в порядке изменится, а деревья не будут эквивалентны, что противоречит условиям.

Обратите внимание, что это работает только тогда, когда все узлы уникальны. Если у вас есть все значения значений типа «a», то независимо от того, как вы ходите, ваша строка всегда «aa ... a». Поэтому вы должны каким-то образом отличать узлы не только от «значения».