Generate-and-test paradigm
Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes. Example: ?- sym_cbal_trees(5,Ts). Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))]
How many such trees are there with 57 nodes? Investigate about how many solutions there are for a given number of nodes? What if the number is even? Write an appropriate predicate.
用单元测试描述为：
from python99.btree.p405 import sym_cbal_trees
def test_sym_cbal_trees():
assert sym_cbal_trees(5) == [
['E', ['E', ['E', None, None], None], ['E', None, ['E', None, None]]],
['E', ['E', None, ['E', None, None]], ['E', ['E', None, None], None]]
]
交换平衡二叉树中任意一个节点的左右子树不会破坏平衡二叉树的约束。所以，通过组合所有节点左右子树交换可以得到限定节点数量下所有平衡二叉树。再过泸出对称的二叉树就得到本题的所要的答案了。
代码实现：
from python99.btree.p402 import cbal_tree
from python99.btree.p403 import symmetric
def sym_cbal_trees(n):
trees = cbal_tree(n)
return [tree for tree in trees if symmetric(tree) is True]