树的路径长度的递归定义

Question

计算树的路径长度的一种方便方法是对于所有k，求k与第k层节点数的乘积之和。

树的路径长度是树所有节点的层数之和。路径长度可以有一个简单的递归定义，如下所示。

具有N个节点的树的路径长度是其根节点子树的路径长度之和加上N-1。

我无法理解上述递归定义。请用简单的例子解释一下。

- venkysmarty

---

空树或只有两个节点的树的路径长度是多少？只有这样，递归定义才算完成。我不太明白这个路径长度是什么或者它有什么用处，但如果你考虑一个有N个顶点的树有N-1条边的话，可能会有所帮助。 - biziclop

@bixiclop：我在上面添加了一些信息。希望这有助于回答问题。 - venkysmarty

Answer 1

理解递归

路径长度可以有一个简单的递归定义：

具有N个节点的树的路径长度是其根节点的子树的路径长度之和加上N-1。

首先，您需要了解什么是路径长度：它是所有节点与根节点之间距离的总和。

有了这个想法，很容易看出没有孩子的根节点的路径长度为0：没有任何节点与根节点的距离。

假设我们已经知道某些树的路径长度。如果我们要创建一个新节点 R 并将所有现有树连接到它，思考一下到根节点的距离如何改变。

以前，距离是从树（现在是子树）的根节点开始测量的。现在，需要多走一步才能到达根节点，即所有距离增加一。

因此，我们添加 N - 1，因为根节点有 N - 1 个后代，现在所有后代都比原来多走一步，即 1*(N-1) = N-1

---

您可以通过几种方式轻松地计算路径长度，可以计算边缘数或节点数。

计算节点数

             A        Level 0
           /   \      
          B     C     Level 1
         / \   / \
        D   E F   G   Level 2

我们从路径长度为0开始：

• 节点 A 是根，总是位于级别0。它不贡献路径长度。（您无需跟随任何路径即可到达它，因此为0）
  • 0 + (0) = 0
• 在级别1上，您有两个节点：B和C：
  • 0 + (1 + 1) = 2
• 在级别2上，您有四个节点：D, E, F和G：
  • 2 + (2 + 2 + 2 + 2) = 10

计算边数

             A        
           /   \      Level 1
          B     C     
         / \   / \    Level 2
        D   E F   G

• 0，我们的初始总和
• + 1*2在第1层，有2条边
• + 2*4在第2层，有4条边

将定义转化为数学表达式

计算树的路径长度的一种方便的方法是对于所有k，求级别k上节点数量和k的乘积之和。

令L_i表示第i层上的节点集合，h表示高度，即从节点到根的最大距离：

- phant0m

Answer 2

             A
           /   \
          B     C
         / \   / \
        D   E F   G

这里，N = 树中节点的总数 = 7

（叶节点的路径长度为零。）

根据递归定义：

Path length of tree = Path length with Root A
                    = Path length with Root B + Path length with Root C + (7-1)

                    = (Path length with Root D + Path length with Root E + (3-1))
                    + (Path length with Root F + Path length with Root G + (3-1))
                    + (7-1)

                    = ((0 + 0 + 2) + (0 + 0 + 2)) + 6
                    = 10

它的实现方式可以如下：

int Recurse(Node root, int totalNodes)
{
    if (totalNodes == 1)
        return 0;
    int noOfNodes1 = CountNodes(root.left);
    int noOfNodes2 = CountNodes(root.right);
    return ( Recurse(root.left, noOfNodes1)
           + Recurse(root.right, noOfNodes2) + totalNodes - 1);
}

- Azodious

---

不，它是10。你犯的错误是只有一个节点的树的路径长度为0，而不是1。 - verdesmarald

你的意思是说叶节点在第零层吗？如果是的话，那么它可能是10。 - Azodious

仍然不正确：不应该有任何“1”。只有一个节点的树的路径长度为0。从那里到您的子树B是：0 +（3-1）= 2。 - phant0m

是的，以<叶节点>为起点的子树路径长度为(1-1) = 0。 - verdesmarald

请注意，实现方式效率极低，因为您不必要地多次计算子树的大小。解决方案是修改树节点以跟踪该节点所根的子树中有多少个节点，或同时计算子树大小和子树路径长度。 - verdesmarald