Construct the bottom-up order sequence of the tree nodes
题目
Write a predicate bottom_up(Tree,Seq) which constructs the bottom-up sequence of the nodes of the multiway tree Tree. Seq should be a Prolog list.
What happens if you run your predicate backwords?
解题思路
Bottom-up 相当于二叉树的后序遍历，先访问子树再访问根节点。
举个例子，给定如下多路树。
- 先访问子树
- 访问第一棵子树
(f,[(g,[])])- 先访问子树
- 第一棵子树
(g,[])- 没有子树
- 访问根节点
g
- 第一棵子树
- 访问根节点
f
- 先访问子树
- 访问第二棵子树
(c,[])- 没有子树
- 访问根节点
c
- 访问第三棵子树
- 先访问子树
- 第一棵子树
(d,[])- 没有子树
- 访问根节点
d
- 第二棵子树
(e,[])- 没有子树
- 访问根节点
e
- 第一棵子树
- 访问根节点
b
- 先访问子树
- 访问第一棵子树
- 访问根节点
a
代码实现：
def bottom_up_t(tree):
e = tree[0]
subtrees = tree[1]
return reduce(concat, [bottom_up_t(subtree) for subtree in subtrees], '') + e
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实现字符串拼接。
反过来，从botoom up序列是不能重构唯一的多路树。最简单的重构选项是重构一个两层的多路树。
举个例子，从序列gfcdeba可以重构出以下两层多路树：
代码实现：
def bottom_up_s(s):
e = s[-1]
remain = s[:-1]
return (e, [(x, []) for x in remain])
最后，将两个方法拼起来。使用Python内建的type检测输入值类型，若输入值类型为tuple即多路树则调用bottom_up_t，否则调用bottom_up_s。