将排序后的数组转换为二叉搜索树（递归） [英] Convert Sorted Array to Binary Search Tree (Picturing the Recursion)

问题描述

我想将排序后的整数数组转换为二进制搜索树。我相信我知道该怎么做。我在下面张贴了我的伪代码。我无法想象的是递归实际上是如何工作的。

I want to convert a sorted integer array into a binary search tree. I believe I understand how to do this. I have posted my pseudo-code below. What I cannot picture is how the recursion actually works.

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

So if my array is 1, 2, 3, 4, 5... I first make 3 the root of my BST. Then I make 2 the left-child node of 3. Then do I make 1 the left-child node of 2, and come back to 2? I don't get how the recursion steps through the whole process...

在此先感谢您，如果对此问题的解释不充分，我们深表歉意。我不需要显式的代码，但是如果有人可以帮助我解决递归如何解决问题（即按什么顺序访问了哪些节点/调用堆栈如何运行），我将不胜感激。

Thanks in advance, and apologies if this question is poorly explained. I don't want explicit code, but I would really appreciate if someone could help me go over how the recursion runs through the problem (i.e. what nodes get visited in what order/how the call stack functions)

伪代码：

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

Step 1. Create a function that takes in the integer array, an integer start, and an integer end. Start = 0, end = integer array size - 1.

步骤2。创建一个等于（开始+结束）/ 2的整数中间值。

Step 2. Create an integer middle which equals (start + end)/2.

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

Step 3. Test to see if start > end.

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

Step 4. If so, return null.

第5步。否则，将值放在中间索引树的根。

Step 5. Else, make the value at the middle index the root of your tree.

步骤6。使用（array，start，middle-1）将根的左节点设置为等于函数。

Step 6. Set the left node of the root equal to the function with (array, start, middle - 1).

第7步。用（array，middle + 1，end）设置根的右节点等于函数。

Step 7. Set the right node of the root equal to the function with (array, middle + 1, end).

推荐答案

在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，

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

这篇关于将排序后的数组转换为二叉搜索树（递归）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！