배열 C++에서 균형 이진 검색 트리 초기화

Question

트리를 균형있게 유지하면서 트리에 값을 삽입하여 배열을 반복적으로 통과하는 함수를 작성하려고합니다. 배열이 정렬되어 있고 크기를 알고 있다고 가정합니다. 내가해야 할 일은 배열 중간에서부터 시작하여 그 값을 루트에 삽입 한 다음 왼쪽 및 오른쪽 반의 가운데를 가져 와서 루트의 왼쪽 및 오른쪽 노드에 삽입하는 식으로 이해하는 것입니다. 배열이 채워질 때까지. 재귀가 가장 먼저 떠오르는 것이고 코딩 한 것은 의미가 있지만 의도 한대로 작동하지 않는 것 같습니다.

문제점 처음 값과 마지막 값이 삽입되지 않고 각 잎의 왼쪽과 오른쪽에 NULL이 아닌 쓰레기 값이있는 노드가 있습니다.

간단한 (강사 제공)하는 노드의 구조 : 생성자

// --------------------------------------------------------------------------- 
// Constructor (from sorted array) 
// 
template<class T> 
BinarySearchTree<T>::BinarySearchTree(T *elements, int n_elements) { 

    int high = n_elements-1; 
    int low = 0; 
    root = new BTNode<T>; 
    BSTreeHelper(low, high, elements, BinaryTree<T>::root); 
} 

도우미 함수 :

template<class T> 
void BinarySearchTree<T>::BSTreeHelper(int low, int high, T* elems, BTNode<T>* root) { 

    int mid = (low+high)/2; // to get the middle value 
    bool isEqual = (low+1 == high || high-1 == low); 

    // if there is a middle value, insert it 
    if (!isEqual) { 
     BTNode<T>* nodePtrL = new BTNode<T>; 
     root->left = nodePtrL; 
     BSTreeHelper(low, mid, elems, nodePtrL); 

     BTNode<T>* nodePtrR = new BTNode<T>; 
     root->right = nodePtrR; 
     BSTreeHelper(mid, high, elems, nodePtrR); 

     root->elem = elems[mid]; 

     cout << "Inserted Element = " << root->elem << endl; 
    } 
} 

/* A lightweight structure implementing a general binary tree node */ 
template <class T> 
struct BTNode { 
    T  elem; // element contained in the node 
    BTNode *left; // pointer to the left child (can be NULL) 
    BTNode *right; // pointer to the right child (can be NULL) 

    // Constructors 
    BTNode() { left = right = NULL; } 
    BTNode(T elem, BTNode* left = NULL, BTNode* right = NULL) { 
    this->elem = elem; 
    this->left = left; 
    this->right = right; 
    } 
    BTNode(const BTNode& src) { 
    this->elem = src.elem; 
    this->left = src.left; 
    this->right = src.right; 
    } 

    // Simple tests 
    bool is_leaf() const { return (left == NULL && right == NULL); } 
}; 

이 I 쓴 함수이고 나는 어떤 식 으로든 isEqual 검사를 다르게하기 위해 머리를 감싸는 것처럼 보일 수 없다. 첫 번째 요소와 마지막 요소, 그리고 왜 여분의 노드가 가비지 값 (어레이의 범위를 벗어날 가능성이 가장 높은 값)으로 생성되는지 알 수 없습니다. 제공 할 수있는 도움에 감사드립니다. 이것은 과제이기 때문에 답을주고 싶지는 않지만 올바른 방향의 요점은 매우 높이 평가됩니다!

Answer 1

당신의 생각은 재귀 좋은 사용, 그러나 당신이 당신의 재귀 함수에 대해 서로 다른 인터페이스를 사용하는 경우 구현하는 것이 훨씬 간단합니다.

요소 배열을 사용하고 해당 요소의 이진 트리 루트 노드를 반환하는 함수를 작성해 보겠습니다. 따라서 이것은 서명입니다 :

template <class T> 
BTNode<T> * 
treeWithElements(T *elements, size_t count) { 

이 함수는 반복적이므로 기본 사례를 먼저 고려해 보겠습니다. 기본 케이스는 count == 1이라고 생각할 수도 있지만 사실 기본 케이스는 count == 0입니다. 다음 요소가 없으므로 빈 나무를 반환해야합니다.

if (count == 0) 
     return NULL; 

이제 우리는 적어도 하나의 요소가 있음을 알게되었습니다. 중간 요소를 트리의 루트로 만들려는 새 노드에 넣을 것입니다.색인은 다음과 같습니다.

노드를 만들려면 먼저 왼쪽 자식과 오른쪽 자식을 만들어야합니다. 왼쪽 아이까지 있지만, 중간 요소를 포함하지 않는 모든 요소가 포함됩니다 :

BTNode<T> *left = treeWithElements(elements, middleIndex); 

가 (. 이것에 대해 생각을 중간 요소의 인덱스는 중간 요소를 선행하는 요소의 수도 있습니다.)

그리고 우리는 올바른 아이를 만들어야합니다.

BTNode<T> *right = treeWithElements(elements + middleIndex + 1, 
     count - (middleIndex + 1)); 

이제 우리는 새로운 노드를 생성하고 반환 할 수 있습니다 : 전부

return new BTNode<T>(elements[middleIndex], left, right); 
} 

을 꽤 간단합니다

template <class T> 
BTNode<T> * 
treeWithElements(T *elements, size_t count) { 
    if (count == 0) 
     return NULL; 
    size_t middleIndex = count/2; 
    BTNode<T> *left = treeWithElements(elements, middleIndex); 
    BTNode<T> *right = treeWithElements(elements + middleIndex + 1, 
     count - (middleIndex + 1)); 
    return new BTNode<T>(elements[middleIndex], left, right); 
} 

그리고 당신의 래퍼 클래스는 중간 요소에 다음과 같은 모든 요소를 ​​포함합니다 생성자가 하나의 행이됩니다.

template<class T> 
BinarySearchTree<T>::BinarySearchTree(T *elements, int n_elements) { 
    root = treeWithElements(elements, n_elements); 
} 

Answer 2

어떤 배열 요소가 BST의 루트일까요? 중간 하나.
어떤 배열 요소가 왼쪽 하위 트리의 루트가됩니까? 왼쪽 하위 배열의 중간입니다.
어떤 배열 요소가 오른쪽 하위 트리의 루트가됩니까? 오른쪽 하위 배열의 가운데.

재귀 패턴을 볼 수 있습니다. 각 호출에서 현재 배열 범위의 가운데 요소를 현재 하위 트리의 루트로 만들고 왼쪽 및 오른쪽 하위 트리에 같은 메서드를 적용합니다.

여기 사이비 코드에 주어진 알고리즘의 :

TreeNode insertSortedArrayToBST(arr[], start, end): 
    if start > end 
     return null 

    mid := (start + end)/2 
    node := new TreeNode(arr[mid]) 

    node.left := insertSortedArrayToBST(arr, start, mid - 1) 
    node.right := insertSortedArrayToBST(arr, mid + 1, end) 

    return node