Как вы объединяете 2 двоичных дерева поиска таким образом, чтобы результирующее дерево содержало все элементы обоих деревьев, а также поддерживало свойство BST.
Я видел решение, представленное в Как эффективно объединить два BST?
Однако это решение включает преобразование в Double Linked List. Мне было интересно, есть ли более элегантный способ сделать это, что можно было бы сделать без преобразования. Я придумал следующий псевдокод. Он работает для всех случаев? Также у меня возникают проблемы с третьим случаем.
node* merge(node* head1, node* head2) {
if (!head1)
return head2;
if (!head2)
return head1;
// Case 1.
if (head1->info > head2->info) {
node* temp = head2->right;
head2->right = NULL;
head1->left = merge(head1->left, head2);
head1 = merge(head1, temp);
return head1;
} else if (head1->info < head2->info) { // Case 2
// Similar to case 1.
} else { // Case 3
// ...
}
}