Determine the internal path length of a tree

题目

We define the internal path length of a multiway tree as the total sum of the path lengths from the root to all nodes of the tree. By this definition, the tree in the figure of problem 5.03 has an internal path length of 9.

Write a predicate ipl(Tree,IPL) for the flow pattern (+,-).

用单元测试描述为：

from python99.mtree.p504 import ipl def test_ipl(): assert ipl(('a', [('f', [('g', [])]), ('c', []), ('b', [('d', []), ('e', [])])])) == 9

解题思路

多路树的内部路径长度被定义为从根节点到每一个节点的縂合。 从最简单的个例开始分析。如下最一个只有一个节点的多路树，其内部路径为0。

接着合併两棵只有一个节点的多路树，如下图，两棵子树中每一个节点到根节点之间的路径长度都加1了，而根节点的路径长度为0。而内部路径长度等于所有节点路径长度的縂合，所以，合併后的内部路径长度为(0+1)+(0+1)+0=2。

至此，可以归纳出：

  1. 多路树的节点集合等于所有子树节点的合集加上根节点
  2. 节点到根节点的路径长度等于节点到子树根节点的路径长度再加一
  3. 根节点到自身的路径长度为0

基于上述规则，就可以设计出递归算法：

  1. 求出子树中所有的节点及它们到各自子树根节点的路径长度
  2. 对所有子树节点到各自子树根节点的路径长度加一即为其到根节的路径长度。根节点到根节点的路径长度为0。合起来就得到了多路树中所有节点及路径长度集合
  3. 将多路树中所有节点的路径长度累加起来即为内部路径长度

举个例子，给定多路树(a,[(f,[(g,[])]),(c,[]),(b,[(d,[]),(e,[])])])：

  • 逐一求子树中所有节点及到子树根节点的路径长度
    • 第一棵子树(f,[(g,[])])
      • 逐一求子树中所有节点及到子树根节点的路径长度
        • 第一棵子树(g,[])
          • 没有子树，所以子树所有节点集合为空
          • 对所有子树节点路径长度加1，因为所有子树节点集合是空集，所以加完1后还是空集
          • 再加上根节点g，路径长度为0，得到所有节点及路径长度集合[(g,0)]
      • 合併所有子树节点及路径长度集合，得到[(g,0)]。对所有子树节点的路径长度加1，得到节点及路径长度集合[(g,1)]
      • 再加上根节点f，路径长度为0，得到本树的所有节点及路径长度集合[(g,1),(f,0)]
    • 第二棵子树(c,[])
      • 没有子树，所以所有子树节点集合为空
      • 对所有子树节点路径长度加1，因为所有子树节点集合为空，所以加完1后还是空集
      • 再加上根节点c，路径长度为0，得到本树的所有节点及路径长度集合[(c,0)]
    • 第三棵子树(b,[(d,[]),(e,[])])
      • 逐一求子树中所有节点及到子树根节点的路径长度
        • 第一棵子树(d,[])
          • 没有子树，所以子树所有节点集合为空
          • 对所有子树节点路径加1，因为所有子树节点集合为空，所以加完1后还是空集
          • 再加上根节点d及路径长度0，得到所有节点及路径长度集合[(d,0)]
        • 第二棵子树(e,[])
          • 没有子树，所以子树所有节点集合为空
          • 对所有子树节点路径长度加1，因为所有子树节点集合为空，所以加完1后还是空集
          • 再加上根节点e及路径长度0，得到所有节点及路径长度集合[(e,0)]
      • 合併所有子树节点及路径长度集合，得到[(d,0),(e,0)]。对所有子树节点的路径长度加1，得到节点集合[(d,1),(e,1)]
      • 再加上根节点b及路径长度0，得到节点集合[(b,0),(d,1),(e,1)]
  • 合併所有子树节点及路径长度集合，得到[(g,1),(f,0),(c,0),(b,0),(d,1),(e,1)]
  • 对所有节点的路径长度加1，得到[(g,2),(f,1),(c,1),(b,1),(d,2),(e,2)]
  • 再加上根节点a及路径长度0，得到节点及路径长度集合[(a,0),(g,2),(f,1),(c,1),(b,1),(d,2),(e,2)]
  • 最后再合计所有节点的路径长度，即为内部路径长度

代码实现：

from functools import reduce from operator import concat, add def ipl(tree): return reduce(add, [x[1] for x in pl(tree)], 0) def pl(tree): nodesOfSubtrees = reduce(concat, [pl(subtree) for subtree in tree[1]], []) return reduce(concat, [[(x[0], x[1]+1)] for x in nodesOfSubtrees], [(tree[0], 0)])

reduce是Python标准库提供的一个函数式的工具，其声明为：

reduce(function, iterable, initializer)

其功能是将function累积地、从左往右作用于iterable中的每一个元素。

reduce相当于如下代码：

def reduce(function, iterable, initializer=None):
    it = iter(iterable)
    if initializer is None:
        value = next(it)
    else:
        value = initializer
    for element in it:
        value = function(value, element)
    return value

这𥚃使用reduce实现节点及路径长度集合合併和路径长度累加。

results matching ""

    No results matching ""