Вопрос о бинарных деревьях. Проверка на похожую форму

Question

Привет, я застрял в этом, не знаю, как это сделать.

Если бы у меня было два двоичных дерева, как бы я проверил, имеют ли они одинаковую форму? Данные в узлах не имеют значения, только если древовидные структуры равны.

Есть идеи, как решить эту проблему?

Answer 1

Вы можете легко сделать это с помощью рекурсии. Следующий код работает, потому что два непустых дерева имеют одинаковую форму тогда и только тогда, когда их соответствующие поддеревья имеют одинаковую форму.

boolean equalTrees(Node lhs, Node rhs)
{
    // Empty trees are equal
    if (lhs == null && rhs == null)
        return true;

    // Empty tree is not equal to a non-empty one
    if ((lhs == null && rhs != null)
        || (lhs != null && rhs == null))
        return false;

    // otherwise check recursively
    return equalTrees(lhs.left(), rhs.left())
        && equalTrees(lhs.right(), rhs.right())
}

Чтобы проверить два дерева, передайте их корневые узлы указанной выше функции.

equalTrees(tree1.root(), tree2.root())

Answer 2

Если у меня есть два двоичных дерева, как бы я проверил, имеют ли они одинаковую форму?

Вам будет приятно узнать, что двоичные деревья обладают интересным свойством: они могут быть представлены в виде массивов . Просто преобразуйте каждое дерево в один из этих массивов и сравните содержимое массива. , Пустые ячейки соответствуют левым или правым дочерним элементам, которые не существуют, определяя структуру дерева. Вы хотите перебрать оба массива и убедиться, что каждая пустая ячейка, встречающаяся в одном массиве, появляется в другом массиве; это O (n).

Конечно, если массивы имеют разные размеры, вам вообще не нужно выполнять какую-либо работу, поскольку деревья с различным числом узлов не могут иметь одинаковую структуру. Оттуда все готово.

Answer 3

Два первых поиска в ширину параллельно будут проходить в одном направлении.

http://en.wikipedia.org/wiki/Breadth-first_search

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

Answer 4

Просто следуйте веткам, имитируя каждое движение в одном дереве в другом В Python псевдокод:

class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def same_shape(T1, T2):
    if T1 == None:
        return T2 == None

    if T2 == None:
        return T1 == None

    return same_shape(T1.left, T2.left) and same_shape(T1.right, T2.right)

Answer 5

Пройдите их в предварительном порядке и в порядке с символическими именами вместо фактических данных и сравните получившиеся строки. Может быть, вам понадобится больше информации о вашей структуре данных.

Не связанный с Java AFAICT