将排序数组插入二进制搜索树
我想实现一种将排序数组插入二叉搜索树的算法，但我不希望最终得到一棵只向一侧生长的树。
你有什么想法吗？
谢谢你。
共有3个答案
按伪随机顺序插入它们，如下所示：
#include <stdio.h>
int array[] = {1,2,3,4,5,6,7,8,9,10};
#define COUNT 10
#define STEP 7 /* must be relatively prime wrt COUNT */
#define START 5 /* not important */
int main(void)
{
unsigned idx;
idx=START;
while(1) {
printf("[%u] = %u\n", idx, array[idx] );
// do_insert(array[idx] );
idx = (idx + STEP ) % COUNT;
if (idx == START) break;
}
return 0;
}
public class SortedArrayToBST {
public TreeNode sortedArrayToBST(int[] num) {
if (num == null) {
return null;
}
return buildBST(num, 0, num.length - 1);
}
private TreeNode buildBST(int[] num, int start, int end) {
if (start > end) {
return null;
}
int mid = start + (end - start) / 2;
TreeNode root = new TreeNode(num[mid]);
TreeNode left = buildBST(num, start, mid - 1);
TreeNode right = buildBST(num, mid + 1, end);
root.left = left;
root.right = right;
return root;
}
}
这应该给你一个平衡的树（在 O（n） 中）：
- 为数组中的中间元素构造一个节点并返回它
（这将是基本情况下的根）。 - 从数组左半部分的 1. 开始重复，将返回值分配给根的左侧子项。
- 从数组右半部分的 1. 开始重复，将返回值分配给根的右侧子级。
Java代码：
TreeNode sortedArrayToBST(int arr[], int start, int end) {
if (start > end) return null;
// same as (start+end)/2, avoids overflow.
int mid = start + (end - start) / 2;
TreeNode node = new TreeNode(arr[mid]);
node.left = sortedArrayToBST(arr, start, mid-1);
node.right = sortedArrayToBST(arr, mid+1, end);
return node;
}
TreeNode sortedArrayToBST(int arr[]) {
return sortedArrayToBST(arr, 0, arr.length-1);
}
从这里得到的代码。
-
一个痛苦而愚蠢的问题，我几乎羞于不敢问。在过去的4个小时里，我一直在寻找，测试了不同的算法，在纸上尝试了不少，但仍然无法正常工作。 我将为您提供项目实现的详细信息，但基本问题是：“如何处理在预排序二叉树中插入节点。 通过预排序BST，我的意思是所有节点都应该以这样的方式插入，即使用预排序遍历（例如用于打印）遍历树时，应该按升序打印节点。 我只需要一个简单的算法。我尝试了这里给出的一个简单的插入算法
-
问题内容： 我在将这两种算法结合在一起时遇到麻烦。我被要求修改以返回将元素插入数组的索引。然后有人要求我实现一个使用my 对随机生成的数组进行排序的。 我按照预期的方式工作，每当我单独测试它时都返回正确的索引。我写信是为了了解它是如何工作的，并使其也能工作。一旦将两者结合在一起，它就会崩溃。我知道我在一起实施起来不正确，但是我不确定问题出在哪里。 这是我得到的： 我在运行它时得到的返回值是。有什么
-
我想把一个排序的整数数组转换成一个二叉搜索树。我相信我知道该怎么做。我已经在下面发布了我的伪代码。我无法想象的是递归实际上是如何工作的。 如果我的数组是1,2,3,4,5。。。我首先将3作为我的BST的根，然后将2作为3的左子节点。那么我要把1设为2的左子节点，然后返回到2吗？我不明白递归是如何贯穿整个过程的。。。 提前感谢，如果这个问题解释得不好，请道歉。我不想要显式的代码，但如果有人能帮我解释
-
我想输出给定值数组的二叉搜索树。它遵循二叉搜索树原理。图表向左旋转 这是所需的输出： 我该怎么修
-
问题内容： 我被要求对数组进行排序和搜索。对数组进行排序很简单，我的代码也起作用了，但是每当我尝试调用二进制搜索方法时，它就可以对数组中的第一个元素起作用，但是结果是“ -1” 我的完整代码如下： 问题答案： 您搞砸了二进制搜索间隔
-
我正在研究“将排序数组转换为具有最小高度的二叉搜索树”，它问： 给定一个排序（递增顺序）数组，将其转换为最小高度的二叉树。 我无法找到为什么我的递归没有像我预期的那样停止。当7通过时，它应该停止，并且不会再次打印出7。我还发现了一个类似的答案，看起来使用了和我相同的策略，但效果很好。（我不认为我的问题与上面列出的问题重复，但我仍然想感谢您为我链接这些问题。他们给了我更多解决问题的想法。） 我的代码