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

Question

public int merge(BNode node, int array[], int i) { 
    if (node == null) 
     return i; 
    //Flatten left subtree 
    i = merge(node.left, array, i); 
    //Get data from the current node 
    array[i] = node.value; 
    //Flatten right subtree 
    i = merge(node.right, array, i + 1); 
    return i; 
} 

Я пытаюсь объединить два бинарных дерева и сохранить свойство BST. Подход, используемый ими, заключается в том, чтобы сгладить деревья и сохранить их в массивах. Функция выше выравнивает мое первое дерево и сохраняет его в массиве [].

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

Answer 1

Как вы это делаете, если вы хотите объединить 2 дерева двоичного поиска, лучший способ: 1) Сгладить деревья в отсортированные списки. 2) Объединить списки. 3) Преобразование объединенного списка в BST.

Вы можете реализовать функцию, которую вы ищете легко таким образом:

BinarySearchTree* arrayToTree(int arr[], int start, int end) { 
    if (start > end) return NULL; 
    int mid = start + (end - start)/2; 
    BinarySearchTree *node = new BinarySearchTree(arr[mid]); 
    node->left = arrayToTree(arr, start, mid-1); 
    node->right = arrayToTree(arr, mid+1, end); 
    return node; 
} 

BinarySearchTree* arrayToTree(int arr[], int n) { 
    return arrayToTree(arr, 0, n-1); 
}