algorithm - 树的路径长度的递归定义

Question

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

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

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

我无法遵循上述递归定义。请用简单的例子解释。

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表示高度，即从节点到根的最大距离：

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);
}