0

我已经实现了一个函数来查找二叉搜索树中节点的深度，但我的实现不处理重复项。我在下面有我的代码，并想就如何在此函数中考虑重复大小写提出一些建议。非常感谢您的帮助。

public int depth(Node n) {
    int result=0;
    if(n == null || n == getRoot())
        return 0;

    return (result = depth(getRoot(), n, result));
}
public int depth(Node temp, Node n, int result) {
    int cmp = n.getData().compareTo(temp.getData());

    if(cmp == 0) {
        int x = result;
        return x;
    }
    else if(cmp < 0) {
            return depth(temp.getLeftChild(), n, ++result);
        }
        else {
            return depth(temp.getRightChild(), n, ++result);
        }                   
}
4

2 回答 2

0

在您显示的代码中，没有办法让一个具有相同值的节点优于另一个节点。你需要有一些区分标准。您可以使用以下方法检索所有重复节点深度的列表，例如：

  1. 找到节点的深度。
  2. 查找从找到的节点出现的左子树的同一节点的深度 - 如果未找到则停止。
  3. 将先前找到的节点的深度（在 1 中）添加到副本的深度
  4. 查找从找到的节点（在 1 中）出现的右子树的同一节点的深度 - 如果未找到则停止。
  5. 将先前找到的节点的深度（在 1 中）添加到副本的深度
  6. 对左右子树重复。

另请参阅此处：BST 中的重复是什么情况？

于 2012-11-15T06:34:40.590 回答
0

好吧，如果有重复，那么具有给定值的节点的深度本身就没有任何意义，因为可能有多个具有该值的节点，因此有多个深度。

您必须确定它的含义，这可能是（不一定是详尽的列表）：

  • 具有该值的最深节点的深度。
  • 具有该值的最浅节点的深度。
  • 使用该值找到的第一个节点的深度。
  • 具有该值的所有节点的平均深度。
  • 具有该值的所有节点的深度范围（最小值/最大值）。
  • 具有该值的所有节点的深度列表。
  • 指示您的查询的错误代码毫无意义。

在特定情况下，其中任何一个都可能有意义。

当然，如果n是指向节点的实际指针，则根本不应该比较节点的值，而应该比较指针。这样，您只会找到一个匹配项，并且匹配的深度是有意义的。

类似下面的伪代码应该做的事情：

def getDepth (Node needle, Node haystack, int value):
    // Gone beyond leaf, it's not in tree

    if haystack == NULL: return -1

    // Pointers equal, you've found it.

    if needle == haystack: return value

    // Data not equal search either left or right subtree.

    if needle.data < haystack.data:
        return getDepth (needle, haystack.left, value + 1)

    if needle.data > haystack.data:
        return getDepth (needle, haystack.right, value + 1)

    // Data equal, need to search BOTH subtrees.

    tryDepth = getDepth (needle, haystack.left, value + 1)
    if trydepth == -1:
        tryDepth = getDepth (needle, haystack.right, value + 1)

    return trydepth

当值相等时您必须搜索两个子树的原因是因为所需的节点可能位于任一子树中。如果值不相等，您就知道它在哪个子树中。因此，对于它们相等的情况，您检查一个子树，如果未找到，则检查另一个。

于 2012-11-15T06:33:26.600 回答