정렬 된 배열을 이진 검색 트리로 변환 (재귀 묘사)

Question

정렬 된 정수 배열을 이진 검색 트리로 변환하려고합니다. 나는이 일을하는 법을 이해한다고 믿습니다. 아래에 내 의사 코드를 게시했습니다. 내가 볼 수없는 것은 재귀가 실제로 어떻게 작동하는지입니다.

내 배열이 1, 2, 3, 4, 5 인 경우 ... 먼저 내 BST의 루트를 3 개 만듭니다. 그런 다음 3의 왼쪽 자식 노드를 2로 만듭니다. 그런 다음 1의 왼쪽 자식 노드를 2로 만들고 2로 돌아가시겠습니까? 재귀가 전체 프로세스를 통해 어떻게 진행되는지 알지 못합니다 ...

이 질문에 대한 설명이 잘못되어 있으면 미리 감사드립니다. 나는 명백한 코드를 원하지 않지만 누군가가 내가 재귀가 문제를 어떻게 진행 하는지를 도울 수 있다면 정말 고마워 할 것이다. (어떤 노드가 어떤 순서로 호출되는지/호출 스택 함수가 어떻게되는지)

의사 코드 :

단계 1. 정수 배열, 정수 시작 및 정수 끝을 사용하는 함수를 만듭니다. 시작 = 0, 끝 = 정수 배열 크기 - 1

단계 2. (시작 + 끝)/2와 같은 정수 중간을 만듭니다.

단계 3. 시작> 종료인지 테스트합니다.

단계 4. 그렇다면 null을 반환합니다.

5 단계. 중간 색인의 값을 트리의 루트로 설정하십시오.

단계 6. 루트의 왼쪽 노드를 (array, start, middle - 1)을 사용하여 함수와 같게 설정하십시오.

단계 7. 루트의 오른쪽 노드를 (array, middle + 1, end) 함수와 동일하게 설정하십시오. 자바에서

Answer 1

:

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

OUTPUT

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

Answer 2

커먼 리스프 버전 : 정말 당신이 고르지 잎을 치료하는 방법에 달려 있지만

(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 floor (log (7)) = 2 트리 최대 높이 2

 4 

    / \ 

    2  6 
/\ /\ 

1 3 5 7 

minmalBST에 형성되어야한다 (루트, 도착, 0, 6) -> 루트 = 4

minimalBST (root.l 송금, 도착, 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 (루트 3 .left.right.left 2) -> 없음

minimalBST (root.right, 도착, 4, 6) -> root.right = 6

,691,363,210

minimalBST (root.right.left, 도착, 4, 4) -> root.right.left = 5

minimalBST (root.right.left.left, 도착, 4, 3) -> 없음

minimalBST (root.right.right, 도착, 6, 6) - 7

minimalBST> root.left.right는 = (root.right.right.left, 3, 2) -> 없음