0

对于给定的 BST，我很难计算深度的总和 [根的所有子节点的单个深度的总和]。我有树的节点总数，我正在尝试计算树的平均深度，需要我有这个深度总和。

递归和我相处得不太好..我发现这个问题非常困难。如果可能的话，我希望看到一个递归解决方案。

笔记：

我创建了访问器 Node.getLeft() 和 Node.getRight()

4

5 回答 5

4

您只需要在遍历树时保留一个深度计数器（如果需要，请查找树遍历）并在每次到达节点时添加计数器的值。然后只需除以节点数。

这看起来像家庭作业，所以我没有提供更详细的解决方案。

于 2009-12-09T20:09:26.817 回答
2

想想如果我在一张纸上向您展示了一张 BST 的图片，您将如何手动完成此操作。当您在一个节点上时，您需要跟踪哪些信息？如何找到给定节点的高度？

从这里开始，尝试将其翻译成伪代码，甚至直接翻译成 Java。如果您遇到问题，请随时发表评论，以便用户可以帮助您。

于 2009-12-09T20:08:33.493 回答
0

由于这是作业，我不想只是给你一个答案。相反，这是一种计算单链表长度的递归方法。希望这将以您可以理解的方式演示递归，并且您可以从那里推断以解决您的 BST 问题。

public final class LL {
    public final int value;
    public LL next;

    public LL(final int value) {
        this.value = value;
    }

    public void add(final int value) {
        if (null == next) {
            next = new LL(value);
        } else {
            next.add(value);
        }
    }

    /**
     * Calculate the length of the linked list with this node as its head (includes this node in the count).
     *
     * @return the length.
     */
    public int length() {
        if (null == next) {
            return 1;
        }
        return 1 + next.length();
    }

    public static void main(final String... args) {
        final LL head = new LL(1);
        head.add(2);
        head.add(3);
        System.out.println(head.length());
        System.out.println(head.next.length());
    }
}
于 2009-12-09T20:57:54.723 回答
0

我们需要访问所有叶节点并找出它们的深度。这表明：

给你的节点访问函数一个额外的参数。它不仅需要知道它要去哪里，还需要知道它有多深。每次调用它时，它都会被调用更深，因此您的节点访问者只需增加从调用者那里获得的深度数。

现在可能会发生以下两种情况之一：

  • 您找到的节点要么是叶节点，即它没有任何子节点；在这种情况下，您的访问者需要将其深度返回给调用者。是的，它只是返回它从调用者那里得到的数字，+ 1。

  • 或者它不是叶节点。在这种情况下，它将有 1 个或 2 个孩子。我们需要将这些深度报告从我们的孩子那里传回给调用者，所以只需返回孩子们返回的深度总和。

通过递归的魔力，返回给根的访问者的数字将是所有孩子的深度之和。

要获得平均深度，您需要将其除以叶节点的数量；我将留给第二次遍历来计算。可以一次性完成，但会稍微复杂一些。

于 2009-12-09T20:26:08.860 回答
0

这是作业吗？如果是这样标记问题。

您可以创建一个方法：

  • 有一个节点引用和一个深度作为参数
  • 增量深度
  • 如果节点不是子节点，则递归调用左右并相应地更新总和
  • 否则返回总和 + 深度

一旦你有了这个除以树中孩子的数量来获得平均深度。

于 2009-12-09T20:10:24.303 回答