java - 二叉搜索树中的节点如何存储在java中？以及其他相关问题

Question

我正在尝试实现二叉搜索树。但我不明白它们将如何存储在数组中。这是我存储它的数据结构:

private Comparable[] intHeap;

我仍然不确定如何使用 comparable，请有人解释一下这个数据结构的用法吗？

我如何检查二叉搜索树的最大和最小元素？

如果我有下面的树，它会作为 1,3,4,6,7,8,10,13,14 存储在 intHeap 中吗？

如果有多个节点级别，您如何知道下一步要转到哪个节点？

提前谢谢你。

Answer 1

从数组的声明来看，你正在构建的是一个binary heap。 - 一种专门的基于树的数据结构，通常存储在数组中。与依赖显式引用的树结构不同，堆依赖于一种巧妙的索引方案，该方案将树“打包”成线性数据结构。

Comparable 接口(interface)允许您构建一个可以存储任意类数据的堆，只要它们实现了Comparable 接口(interface)。这很有用，因为您可以构建适用于数字、字符串或您自己类型的对象的可重用代码。

How do you know which node to go to next, if there is multiple node levels?

如果一个节点位于索引 n，它的两个子节点将位于索引 2n + 1 和 2n + 2。如果您位于索引 k 并且您想要跟随左子树，设置k = 2*k+1；如果要跟随右子树，设置k = 2*k+2。继续遵循相同的算法，直到您命中 intHeap 数组中的 null 元素。