从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

回答

相关问题