为什么要将点存储在二叉树中？
这个问题涵盖了一个软件算法
我正在解决亚马逊软件问题中的一个面试问题，特别是< br >“给定一组点(x，y)和一个整数“n”，返回n个接近原点的点”
下面是这个问题的高级伪代码示例答案，来自示例答案
步骤1：设计一个名为point的类，它有三个字段-int x，int y，int distance
第2步：对于所有给定的点，找到它们与原点之间的距离
第一步：将值存储在二叉树中
我同意步骤1和2，因为在面向对象设计方面，让一个数据软件包Point封装掉x、y和distance.Ensapsulation
有人可以解释从3到5的设计决策吗？
下面是我将如何执行步骤3到5的步骤步骤3：将所有点存储在一个数组中
步骤4：根据距离对数组进行排序（我在这里使用一些内置排序，如数组。排序
第5步：将数组按升序排序，打印出前n个值
为什么该响应的作者使用更复杂的数据结构，二叉树，而不是我使用的更简单的数组？我知道什么是二叉树-具有两个指针的节点的分层数据结构。在他的算法中，你需要使用BST吗？
共有3个答案
这篇文章中描述的方法比这样一个问题所需要的更复杂。正如您所提到的，简单的按距离排序就足够了。然而，为了帮助解释您对示例答案作者试图获得的内容的困惑，可以考虑k最近邻问题，该问题可以通过k-d树来解决，k-d树是一种将空间分区应用于k-d数据集的结构。对于二维空间，这确实是一棵二叉树。这个树本来就是排序的，不需要任何“堆排序”
需要注意的是，构建k-d树需要O（n logn），并且只有在需要对结构进行重复的最近邻搜索时才值得花费。如果只需执行一次搜索即可从原点查找k个最近邻居，则可以使用朴素的O（n）搜索。
如何构建一个 k-d 树，直接来自 Wiki：
向k-d树添加新点的方式与向任何其他搜索树添加元素的方式相同。首先，遍历树，从根开始，根据要插入的点是在拆分平面的“左”侧还是“右”侧，移动到左或右子级。到达子节点应位于的节点后，添加新点作为叶节点的左或右子节点，再次取决于节点拆分平面的哪一侧包含新节点。
以这种方式添加点会导致树变得不平衡，从而降低树的性能。树性能下降的速度取决于添加的树点的空间分布，以及与树大小相关的添加点的数量。如果树变得太不平衡，可能需要重新平衡以恢复依赖于树平衡的查询的性能，例如最近邻搜索。
一旦建立了树，你可以在O(k log n)时间内找到k个到某个点(在你的例子中是原点)的最近邻。
直接从维基：
在k-d树中搜索最近邻居的过程如下:
- 从根节点开始，算法递归地沿树向下移动，与插入搜索点的方式相同（即，它向左或向右移动，取决于该点是否小于或大于拆分维度中的当前节点）
- 一旦算法到达叶节点，它将该节点保存为“当前最佳”
- 该算法展开树的递归，在每个节点执行以下步骤：
- 如果当前节点比当前最佳节点更近，则它将成为当前最佳节点
- 该算法检查在分割平面的另一侧是否有任何点比当前最佳点更靠近搜索点。在概念上，这是通过将分裂超平面与搜索点周围的超球体相交来实现的，超球体的半径等于当前最近距离。由于超平面都是轴对齐的，这是作为一个简单的比较来实现的，以查看搜索点和当前节点的分割坐标之间的差异是否小于从搜索点到当前最佳点的距离（总坐标）。
- 如果超球穿过平面，则平面的另一侧可能有更近的点，因此算法必须从当前节点向下移动树的另一个分支，以寻找更近的点将遵循与整个搜索相同的递归过程
- 如果超球不与分割平面相交，则算法继续沿着树向上走，并消除该节点另一侧的整个分支
这是一个非常复杂的算法，我讨厌把它描述成一个面试问题！幸运的是，正如你在帖子中指出的，这里的一般情况比需要的要复杂。但我相信这种方法可能接近你的(错误的)样本答案试图描述的内容。
不必使用BST。但是，当需要自排序的结构时，使用BST是一种很好的做法。我不认为有必要同时使用BST和heapsort（不知何故）。您可以只使用BST并检索前n个点。您还可以使用数组，对其排序并使用前n个点。如果要对点类型的数组进行排序，可以实现接口Comparable（点将是该接口的IMElement）并重载默认方法。您不必选择任何数据结构，但通过确定您的需求，您也可以轻松确定最佳结构。
首先，我不会说有点（x，y，距离）是好的设计或封装。距离实际上不是点的一部分，它可以从x和y计算出来。在设计方面，我肯定会有一个函数，即来自Point的静态方法或帮助器类Point。
double distance(Point a, Point b)
那么对于具体的问题，我其实同意你的解决方案，把数据放在一个数组里，对这个数组排序然后先提取N。该示例可能暗示的是，堆排序实际上经常使用数组内的二叉树结构进行排序，如下所述:
堆通常被放置在一个具有完整二叉树布局的数组中。
当然，如果到原点的距离没有存储在Point中，出于性能原因，它必须与数组中相应的Point对象一起放置，或者任何信息将允许从排序的距离（引用、索引）中获取Point对象，例如。
List<Pair<Long, Point>> distancesToOrigin = new ArrayList<>();
要使用比较器排序
-
顺序存储二叉树是指用一个数组存储的二叉树，一般用于完全二叉树，物理上用数组存储逻辑上是一个树结构。 第n个元素的左节点索引2n+1 第n个元素的右节点索引2n+2 第n个元素的父节点为(n-1)/2 n为元素在数组中的索引 class Node(object): def __init__(self, data): self.data = data class Array
-
主要内容：二叉树的性质,满二叉树,完全二叉树,总结通过《 树的存储结构》一节的学习，我们了解了一些树存储结构的基本知识。本节将给大家介绍一类具体的树结构—— 二叉树。 简单地理解，满足以下两个条件的树就是二叉树： 本身是有序树； 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2； 例如，图 1a) 就是一棵二叉树，而图 1b) 则不是。 图 1 二叉树示意图 二叉树的性质 经过前人的总结，二叉树具有以下几个性质： 二叉树中，第 i
-
尽管我们通常为每个四叉树定义一个容量，但我在网上找到的所有伪代码算法似乎都不太关心四叉树中的视觉点数。 当四叉树被分割时，有必要将其包含的点重新分布到其子树中吗？ 我似乎无法正确实现这一点，维基百科四叉树的伪代码类别对此只有一条评论（但没有代码）： 如果我们希望只有最后一个节点保存数据，我们必须将包含在这个四边形数组中的点/数据添加到新的四边形中
-
下面给出了二叉树的实现。 如图中所示，树不是完整的二叉树。如何编写一个函数，将上述二叉树转换为完整的二叉树，只需将字符串数据节点添加到没有子节点的节点，即可生成完整的二叉树。 我将手动在代码中添加节点，以获得如下结果树： 但是，如何编写一个函数，它将采取根节点和返回树，这是完整的二叉树。
-
上一节讲了 二叉树的顺序存储，通过学习你会发现，其实二叉树并不适合用数组存储，因为并不是每个二叉树都是完全二叉树，普通二叉树使用 顺序表存储或多或多会存在空间浪费的现象。 本节我们学习二叉树的 链式存储结构。 图 1 普通二叉树示意图 如图 1 所示，此为一棵普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用 链表存储即可。因此，图 1 对应的链式存储结构如图 2
-
二叉树的存储结构有两种，分别为顺序存储和链式存储。本节先介绍 二叉树的顺序存储结构。 二叉树的顺序存储，指的是使用 顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。 因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。 有读者会说，满二叉树也可以使用顺序存储。要知道，满二叉树也是完全二叉树，因为它满足完全二叉树