gpt4 book ai didi

c - 输入值创建二叉搜索树

转载 作者:太空宇宙 更新时间:2023-11-04 01:40:07 25 4
gpt4 key购买 nike

在二叉搜索树上,如果我输入“2,1,3,4,5”,树会是这样的

              2
/\
1 3
\
4
\
5

但是输入像“5,2,1,3,7,6,8”。

                      5
/ \
2 7
/\ /\
1 3 6 8

所以我的问题是,如何产生输入以便获得上面的平衡树结构。 (我不想使用 AVL 树)。我们是否有技巧以正确的方式对数字进行排序或重新排列并将它们作为输入生成。我正在寻找输入,以便树可以创建高达 10 的高度。

最佳答案

保证平衡树的一种非常简单的方法是对输入进行排序,然后递归地插入值,如下所示:

  1. 插入整个数组的中间。
  2. 使用此过程递归地插入数组的左半部分和右半部分。

例如,对于删除了 5 的值 1 - 8,您会将值排序为

1 2 3 5 6 7 8

然后您将插入 5,然后递归地将此过程应用于两半。在 1 2 3 上,您将插入 2,然后递归地插入 1 和 3。这给出了到目前为止的顺序

 5 2 1 3

现在,您递归地处理另一半,6 7 8,它插入 7,然后递归地插入 6 和 8。总的来说,这产生了顺序

5 2 1 3 7 6 8

这正是您之前在帖子中提出的顺序。

这个过程在 O(n lg n) 时间内运行。我不确定这是最佳答案,所以如果有人想发布更好的答案,我很乐意看到。

关于c - 输入值创建二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6950669/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com