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

Question

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

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

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

Pseudo-code :

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

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

Шаг 3. Проверьте, чтобы начать> конец.

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

Шаг 5. Еще раз, сделайте значение в среднем индексе корня вашего дерева.

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

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

Answer 1

В 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); 
} 

TEST:

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,

Answer 2

Common Lisp версия:

(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)))) 

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

Answer 3

public class ArrayToBst { 

    private static int[] arr = { 1, 2, 3, 4, 5, 6, 7 }; 

    public static void main(String[] args) { 

     Node talakorootpreservegareko = getBst(arr, 0, 6); 
     inOrder(talakorootpreservegareko); 

    } 

    public static Node getBst(int[] arr, int start, int stop) { 
     if (start > stop) { 
      return null; 
     } else { 
      int mid = (start + stop)/2; 
      Node root = new Node(arr[mid]); 
      System.out.println(root.data); 
      root.left = getBst(arr, start, mid - 1); 
      root.right = getBst(arr, mid + 1, stop); 
      // System.out.print(root.data + " \t"); 
      return root; 
     } 
    } 

    public static void inOrder(Node parent) { 
     if (parent != null) { 
      inOrder(parent.left); 
      System.out.print(" data " + parent.data + "\t"); 
      inOrder(parent.right); 
     } 
    } 
} 

Answer 4

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 этаж (log (7)) = 2 Дерево должно быть сформировано с при максимальной высоте 2

 4 

    / \ 

    2  6 
/\ /\ 

1 3 5 7 

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

minimalBST (root.l EFT, обр, 0, 2) -> root.left = 2

minimalBST (root.left.left, обр, 0, 0) -> root.left.left = 1

minimalBST (корень. left.left.left, обр, 0, -1) -> Без

minimalBST (root.left.right, обр, 2, 2) -> root.left.right = 2

minimalBST (корень .left.right.left, 3, 2) -> Без

minimalBST (root.right, обр, 4, 6) -> root.right = 6

minimalBST (root.right.left, обр, 4, 4) -> root.right.left = 5

minimalBST (root.right.left.left, обр, 4, 3) -> Без

minimalBST (root.right.right, обр, 6, 6) -> root.left.right = 7

minimalBST (root.right.right.left, 3, 2) -> Без