Как я могу объединить два двоичных дерева

Question

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

Answer 1

1) Свести оба дерева в отсортированные списки.
2) Объединить списки из того, что вы получили в 1)
3) Построить дерево из того, что вы получили в 2)

Answer 2

Этот алгоритм может вам помочь.

Answer 3

Без учета эффективности этот ответ может сработать Алгоритм объединения двух двоичных деревьев? .Если отсортировано или сбалансировано, обсуждение эффективности в Как эффективно объединить два BST? и Объединение / Слияние / Соединение двух деревьев AVL

Answer 4

Дерево также является графом, поэтому выведите пары вершин ребер (u, v) для каждого дерева, а затем объедините эти множества ребер и выведите результирующий граф.

Возникает вопрос, как сопоставить вершины в одном дереве с вершинами в другом (например, у нас есть пара ребер (5,9) в дереве 1 и пара ребер (5,6) в дереве 2, соответствуют ли эти 5s) в одну и ту же вершину?).

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

Answer 5

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