從Array C++

我想寫遞歸遍歷一個數組去，將值插入到一棵樹，同時保持樹平衡功能初始化一個平衡二叉搜索樹。假設數組已經排序並且我們知道它的大小。我的理解是什麼，我需要做的是來自各地的數組的中間開始，將該值插入根，然後採取左，右兩半的中間，並將這些成左節點和根的權利，等等直到數組被填充。遞歸是首先想到的，我編碼的內容是有意義的，但似乎並沒有按照我的意圖工作。我有從Array C++

問題是未插入第一個和最後一個值，而我在每片葉子的左側和右側獲得垃圾值的節點，而不是他們的是NULL。

節點是簡單的（由教師提供）的結構：

/* 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); } 
};

這是我寫的函數：用於構造

// --------------------------------------------------------------------------- 
// 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; 
    } 
}

我似乎無法以任何方式對isEqual檢查做出不同的解釋，以便說明問題第一個和最後一個元素，我真的不知道爲什麼額外的節點正在創建垃圾值（最有可能的數組邊界之外的值）。感謝您的任何幫助，您可以提供。這是一項任務，所以我不想給出答案，但正確的方向點是非常感謝！

來源

2014-02-09 floatfil

你的點子使用遞歸是好的，但它更容易實現，如果你使用不同的接口爲您的遞歸函數。

我們來編寫一個函數，它接受元件的陣列，並返回這些元素的二進制樹的根的節點。所以這是簽名：

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

因爲這個函數是遞歸的，所以我們先考慮一下基本情況。您可能會認爲基本情況是count == 1，但實際上基本情況是count == 0。那麼有沒有元素，所以我們需要返回一個空樹：

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

來源

2014-02-09 21:33:45

什麼數組元素將是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

來源

2014-02-09 21:32:56

回答

相關問題