2

我想将排序的整数数组转换为二叉搜索树。我相信我明白如何做到这一点。我在下面发布了我的伪代码。我无法想象的是递归实际上是如何工作的。

因此，如果我的数组是 1、2、3、4、5... 我首先将 3 作为 BST 的根。然后我把 2 设为 3 的左子节点，那我是不是把 1 设为 2 的左子节点，然后回到 2 呢？我不明白递归如何贯穿整个过程......

在此先感谢，如果这个问题解释得不好，我们深表歉意。我不想要明确的代码，但如果有人可以帮助我了解递归如何解决问题（即以什么顺序访问哪些节点/调用堆栈如何运行），我将不胜感激

伪代码：

步骤 1. 创建一个接收整数数组、整数开头和整数结尾的函数。开始 = 0，结束 = 整数数组大小 - 1。

步骤 2. 创建一个整数中间，等于 (start + end)/2。

步骤 3. 测试是否开始 > 结束。

第 4 步。如果是，则返回 null。

第 5 步。否则，将中间索引处的值设为树的根。

步骤 6. 将根的左节点设置为等于 (array, start, middle - 1) 的函数。

步骤 7. 将根的右节点设置为等于 (array, middle + 1, end) 的函数。

4

4 回答 4

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

测试：

    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,

于 2013-11-02T06:03:04.337 回答
0 
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);
        }
    }
}
于 2014-07-17T06:11:10.637 回答
0

普通 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))))

尽管这实际上取决于您要如何处理不均匀的叶子。

于 2013-11-02T22:20:44.493 回答
0 
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(root, arr, 0, 6) -> root = 4

最小BST(root.left, arr, 0, 2) -> root.left = 2

最小BST(root.left.left, arr, 0, 0) -> root.left.left = 1

最小BST（root.left.left.left，arr，0，-1）->无

最小BST(root.left.right, arr, 2, 2) -> root.left.right = 2

最小BST(root.left.right.left, 3, 2) -> 无

最小BST(root.right, arr, 4, 6) -> root.right = 6

最小BST(root.right.left, arr, 4, 4) -> root.right.left = 5

最小BST(root.right.left.left, arr, 4, 3) -> 无

最小BST(root.right.right, arr, 6, 6) -> root.left.right = 7

最小BST(root.right.right.left, 3, 2) -> 无

于 2016-12-18T10:56:15.623 回答