Преобразование отсортированного массива в двоичное дерево поиска (изображение рекурсии)

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

Итак, если мой массив равен 1, 2, 3, 4, 5... Сначала я делаю 3 корнем своего BST. Затем я делаю 2 левым дочерним узлом 3. Затем я делаю 1 левым дочерним узлом 2 и возвращаюсь к 2? Я не понимаю, как рекурсия проходит через весь процесс...

Заранее спасибо, и извините, если этот вопрос плохо объяснен. Мне не нужен явный код, но я был бы очень признателен, если бы кто-нибудь помог мне понять, как рекурсия проходит через проблему (т.е. какие узлы посещаются в каком порядке/как работает стек вызовов)

Псевдокод:

Шаг 1. Создайте функцию, которая принимает массив целых чисел, начало и конец целого числа. Start = 0, end = целочисленный размер массива - 1.

Шаг 2. Создайте целое число середины, равное (начало + конец)/2.

Шаг 3. Проверьте, начинается ли > конец.

Шаг 4. Если да, верните ноль.

Шаг 5. В противном случае сделайте значение в среднем индексе корнем вашего дерева.

Шаг 6. Установите левый узел корня равным функции с (массив, начало, середина - 1).

Шаг 7. Установите правый узел корня равным функции с (массив, середина + 1, конец).


arrays recursion add binary-search-tree sorted
person user2946943    schedule 02.11.2013    source источник

Ответы (4)


arrow_upward
1
arrow_downward

В Java:

public static BST sortedArrayToBST(int[] arr){
    BST bst = new BST();
    sortedArrayToBST(arr, 0, arr.length-1, bst);
    return bst;
}

private static void sortedArrayToBST(int[] arr, int start, int end, BST bst) {

    if( start == end){
        bst.insert(new Node(arr[start]));
        return;
    }
    else if(start > end) {
        return;
    }
    int middle = (start+end)/2;
    bst.insert(new Node(arr[middle]));
    sortedArrayToBST(arr, start, middle - 1, bst);
    sortedArrayToBST(arr, middle+1, end, bst);
}

ТЕСТ:

    int[] arr = {1,2,3,4,5,6,7,8,9};
    BST bst = sortedArrayToBST(arr);
    bst.printInOrder();

ВЫВОД

1,2,3,4,5,6,7,8,9,

person Nir Alfasi    schedule 02.11.2013

arrow_upward
0
arrow_downward

Общая версия Лиспа:

(defun sorted-array->tree (array)
  (loop
     :with olength := (length array)
     :with length := (ceiling olength 2)
     :with result := (make-array length)
     :for i :from 0 :below length
     :for j :from 0 :by 2
     :for k :from 1 :by 2 :do
     (setf (aref result i)
           (if (< k olength)
               (list (aref array j) (aref array k))
               (list (aref array j))))
     :finally
     (return (if (= 1 length)
                 (aref result 0)
                 (sorted-array->tree result)))))

(sorted-array->tree #(1 2 3 4 5 6 7 8 9))

;; ((((1 2) (3 4)) ((5 6) (7 8))) (((9))))

Хотя это действительно будет зависеть от того, как вы хотите обрабатывать неровные листья.

person Community    schedule 02.11.2013

arrow_upward
0
arrow_downward 

minimalBST(root, arr, 0, len(arr) - 1)
def minimalBST(root, arr, start, end):

    if start > end
        return
        mid = (start + end) // 2 
        root = CreateNode(arr[mid])
        minimalBST(root.left, arr, start, mid - 1)
        minimalBST(root.right, arr, mid + 1, end)

-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

arr = [1,2,3,4,5,6,7], так как len(arr) = 7 floor(log(7)) = 2 Дерево должно быть сформировано с максимальной высотой 2

      4

    /   \

   2     6  
  / \   / \

 1   3 5   7

minmalBST (корень, обр., 0, 6) -> корень = 4

минимальный BST (root.left, обр, 0, 2) -> root.left = 2

минимальный BST (root.left.left, обр., 0, 0) -> root.left.left = 1

минимальный BST (root.left.left.left, обр, 0, -1) -> Нет

минимальный BST (root.left.right, обр., 2, 2) -> root.left.right = 2

минимальный BST (root.left.right.left, 3, 2) -> Нет

минимальный BST (root.right, обр., 4, 6) -> root.right = 6

минимальный BST (root.right.left, arr, 4, 4) -> root.right.left = 5

минимальный BST (root.right.left.left, обр, 4, 3) -> Нет

минимальный BST (root.right.right, обр, 6, 6) -> root.left.right = 7

минимальный BST (root.right.right.left, 3, 2) -> Нет

person ashutosh benni    schedule 18.12.2016

arrow_upward

arrow_downward

person    schedule
comment
Не могли бы вы добавить некоторые пояснения или комментарии к своему ответу на ОП? - person Joe Kennedy; 17.07.2014