树的路径长度的递归定义

Question

计算树的路径长度的一种有效方法是对所有k求和k的乘积和k级的节点数.

树的路径长度是所有树节点的级别的总和.路径长度可以具有如下的简单递归定义.

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

我无法遵循上面的递归定义.请用简单的例子来解释.

Answer 1

理解递归

路径长度可以具有如下的简单递归定义.

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

首先,您必须了解路径长度是什么:它是节点和根之间所有距离的总和.

考虑到这一点,可以看出没有子节点的根节点的路径长度为0是微不足道的:没有与根节点有距离的节点.

我们假设我们已经知道了一些树的路径长度.如果我们要创建一个新节点R,我们将已经连接的所有树连接到该节点,请考虑到根节点的距离如何变化.

以前,距离是根据树的根(现在是子树)来测量的.现在,还有一个步骤要对根节点进行,即所有距离都增加1.

因此,我们补充说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表示高度,即从节点到根节点的最大距离: