Самый простой способ объединить два двоичных дерева - это пройти по левому дочернему элементу одного дерева до достижения узла без левого дочернего элемента. Затем добавьте корень другого дерева в качестве левого потомка. Результирующее дерево для вашего примера будет:
8
5 7
9
4 20
30
Однако обратите внимание, что результирующее дерево в этом примере очень несбалансированное. Это приведет к неэффективным операциям с результирующим деревом, если это является намерением. Лучшее решение состоит в том, чтобы равномерно распределить узлы из второго дерева в первое дерево. Одним из способов достижения этого является рекурсивное добавление корневого и левого поддерева второго дерева к левому поддереву первого дерева и правого поддерева к правому поддереву. Для более равномерного распределения случайным образом выберите, на какую сторону выделять корень на каждом шаге.
Обратите внимание, что двоичные деревья здесь , а не деревья бинарного поиска. Работа с BST является немного более интересным случаем, так как вы должны убедиться, что результирующее дерево также является действительным BST. Для тех, кто заинтересован, вот решение этой проблемы: Поиск корневого значения дерева 2 в дереве 1. Если мы заходим в тупик, не найдя это значение, мы можем просто вставить дерево 2 в место, где будет было ли это в дереве. Если мы найдем значение, то мы можем заменить этот узел на дерево 2. Затем взять поддерево с корнем в смещенном узле и вставить его в дерево 2, используя тот же алгоритм.