Check whether a given term represents a multiway tree
题目
Write a predicate istree/1 which succeeds if and only if its argument is a Prolog term representing a multiway tree. Example: ?- istree(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])). Yes
用单元测试描述为
from python99.mtree.p501 import istree
def test_istree():
assert istree(('a', [])) == True
assert istree(('a', [('b', []), ('c', []), ('d', [])])) == True
assert istree(('a', 'b', [])) == False
解题思路
在Python中，可以用以下形式存储多路树：
(E,F)
其中，
E是根节点的值F是一个可空列表，其中每一个元素都是一个多路树
根据多路树的定义和我们所採用的存储形式，可以使用递归方法检测一个对象是否为多路树。
- 若值不为二元组，则其不是多路树
- 若二元组第二个元素不为列表，则其不是多路树
- 若第二个元素为空列表，则其为多路树
- 若列表中的每一个元素都是多路树（对每一个元素套用1至4步），则其为多路树，否则不是多路树
代码实现：
from functools import reduce
from operator import and_
def istree(t):
if type(t) is not tuple:
return False
if len(t) != 2:
return False
if type(t[1]) is not list:
return False
return reduce(and_, [istree(e) for e in t[1]], True)
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对所有子树判断结果做与计算。如点所有的子树都是多路树，即所有结果都是Tree，则reduce累积的结果就是True。这𥚃用True做initializer，确保在子树列表为空的情况依旧可以得正确的结果。