Объединение двоичных деревьев

Question

Предположим, что у нас есть набор бинарных деревьев с заданными их порядками и предлогами, и ни одно дерево не является поддеревом другого дерева в данном наборе. Теперь дается другое двоичное дерево Q. Определите, может ли он быть образован путем объединения двоичных деревьев из заданного набора. (При соединении каждого дерева в наборе следует рассматривать один раз один раз). Соединительные операции:

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

Можем ли мы сделать это с использованием LCA (наименее общего предка)? Или ему нужна какая-либо специальная структура данных для решения?

Answer 1

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

И я не понимаю, как вы будете использовать LCA для этого. Насколько мне известно, LCA используется для того, чтобы узнать наименьшего общего предка для двух NODES в одном и том же дереве. Это не помогло бы сравнивать два дерева. (что я бы сделал, чтобы проверить, может ли быть Q)

Мое решение на словах.

Дерево Q, которое необходимо проверить, если оно может быть сделано из набора деревьев. Поэтому я бы взял подход сверху вниз. В основном сравнение Q с возможными деревьями, сформированными из набора.

Логика: Если Q.root не соответствует ни одному из корней деревьев в наборе (A, B, C .... Z ...), решения не допускается.

Если Q.root соответствует корню дерева (скажем, A), проверьте соответствующие дети и отметьте A как использованный/посетивший. (Это то, что я понимаю из вопроса: дерево можно использовать только один раз)

Мы должны продолжить работу с А в нашем решении, только если все дети Q совпадают с соответствующими дочерними элементами A. (Я бы сделал первый шаг по глубине , Breadth First тоже будет работать).

Мы можем добавить добавление нового дерева из набора (т. Е. Добавить новый корень (дерево B) только в листовые узлы A, поскольку мы должны поддерживать двоичное дерево). Следите за тем, где был добавлен B.

Повторите ту же проверку с соответствующим сравнением детей, как это сделано для A. Если нет совпадения, удалите B и попробуйте добавить дерево C в том месте, где был добавлен B.

Мы продолжаем делать это до тех пор, пока не закончим узлы в Q. (если мы не хотим ИДЕНТИЧЕСКОГО МАТЧИ, в этом случае мы будем использовать другие древовидные комбинации, отличные от тех, которые у нас есть, которые соответствуют Q, но имеют больше узлов) ,

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

Надеюсь, это поможет.

Альтернативное решение: будет намного менее эффективным (попробуйте только в том случае, если имеется относительно меньшее количество деревьев): формирование всего возможного набора деревьев (сначала в 2 с, затем 3 с .... N) и и проверка сформированных деревьев если они идентичны Q. сравнивающая часть можно назвать здесь: http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/