2

给定一棵二叉树，我需要实现一个方法 findAllElements(k) 来查找树中键等于 k ​​的所有元素。

我的想法是你第一次遇到带有键 k 的元素。所有具有相同键的元素都应该在左孩子的右子树或右孩子的左子树中。但有人告诉我可能不是这样？

我只需要找到一种实现算法的方法。所以需要伪代码。

我可能应该添加这个抱歉。但是实现是左子树包含小于或等于根键的键，右子树包含大于或等于根键的键。

4

3 回答 3

1

这取决于您的树实现，二叉树我假设您的意思是二叉搜索树，并且您使用 operator< 来比较键。也就是说，节点的左子树仅包含键小于（<）的节点，而节点的右子树仅包含键不小于（！<）的节点。

例如

  7 
 / \
4   7
   / \
  6   8

如果树中有多个相等的键，请执行此操作

k < current_node_key,  search left subtree
k > current_node_key,  search right subtree
k == current_node_key, record current node , then search right tree
于 2013-02-28T19:06:03.853 回答
0

查看当前节点。如果它的key大于k，则搜索左子树。如果它较低，则搜索右子树。如果相等，则搜索左右子树（并在结果中包括当前节点）。

从根节点开始递归地执行此操作。

于 2013-02-28T18:54:09.350 回答
0

以为我会在与老师交谈后回来解释结果应该是什么。因此，如果您执行一个 findElement(k) 方法，该方法将找到键等于 k ​​的元素，它找到的元素应该是键为 k 的树中最高的元素（让我们将此元素表示为 V）。

然后从这个元素 V 开始，包含 key=k 的其他元素要么在左子子树中（特别是一直到右边），要么在右子子树中（特别是在左边）。所以对于左孩子来说，继续到下一个节点右孩子，直到找到一个 key=k 的元素......现在......以这个节点为根的子树中的每个元素都必须有一个 key=k（这是我一开始没认出的部分）因此可以对这个完整的子树进行任何形式的遍历，以查找并存储该子树中的所有元素（访问其中的每个节点）。必须为右孩子重复这种类型的事情，但要访问每个左孩子，直到找到一个 key=k 的元素。

显然，这只是一个词的描述，对于长度和任何混淆感到抱歉。希望这将帮助其他试图解决类似问题的人。

于 2013-03-01T20:03:47.287 回答