java - 处理二叉搜索树中的相同数据

Question

我正在自学数据结构，目前正在研究二叉搜索树。我很好奇如果你有相同的数据你会如何对树进行排序。例如，假设我的数据由 [4,6,2,8,4,5,7,3] 组成。

1. 我设置4为根元素
2. 在其右侧添加 6
3. 将 2 放在 4 的左边
4. 将 8 放在 6 的右侧

然后我到了 4，从 4=4 开始我该把它放在哪里？向左还是向右？

选项#1

选项#2

其中之一是正确的还是都错误？如果它们都错了，你能告诉我应该如何对它们进行排序吗？谢谢!

Answer 1

通常二叉树不允许数据重复。如果您进行自定义实现，则可以存储一定数量的元素。 Java 中的 TreeSet 就是一个示例 - 它仅包含唯一元素。

实际上你列出的案例破坏了树的整个结构。搜索操作现在看起来很奇怪，并且无法使用 O(ln n) 执行。在最坏的情况下，这将需要 O(n)，因此您将失去此数据结构的所有优势。