Collect the internal nodes of a binary tree in a list
题目
An internal node of a binary tree has either one or two non-empty successors. Write a predicate internals/2 to collect them in a list.
% internals(T,S) :- S is the list of internal nodes of the binary tree T.
内部节点即除了叶子节点以外所有的节点。
单元测试描述为：
from python99.btree.p410 import internals
def test_internals():
E = 'E'
assert internals([E, [E, None, [E, None, None]],
[E, None, None]]) == [E, E]
assert internals([E, [E, None, None], [E, None, None]]) == [E]
解题思路
递归遍历二叉树，如遇到内部节点（非叶子、非空）则返回节点值，遇到其它的则返回空列表。
举个例子，给定二叉树[E, [E, None, [E, None, None]], [E, None, None]]。
- 根节点有非空的子树，其是内部节点
- 遍历左子树。左子节点有非空子树，所以其是内部节点
- 遍历左子树。左子节点为空，所以其是非内部节点
- 遍历右子树。右子节点左右子树都为空，所以其是非内部节点（叶子）
- 遍历右子树。右子节点左右子树都为空，所以其是非内部节点（叶子）
- 遍历左子树。左子节点有非空子树，所以其是内部节点
代码实现：
def internals(t):
if t is None:
return []
if t[1] is None and t[2] is None:
return []
return [t[0]] + internals(t[1]) + internals(t[2])