Construct height-balanced binary trees
题目
In a height-balanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one.
Write a predicate hbal_tree/2 to construct height-balanced binary trees for a given height. The predicate should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree. Example: ?- hbal_tree(3,T). T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil))) ; T = t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil)) ; etc......No
用单元测试描述为：
from python99.btree.p406 import hbal_tree
def test_hbal_tree():
E = 'E'
assert hbal_tree(2) == [
[E, [E, None, None], [E, None, None]],
[E, [E, None, None], None],
[E, None, [E, None, None]]
]
assert hbal_tree(3) == [
['E',
['E', ['E', None, None], ['E', None, None]],
['E', ['E', None, None], ['E', None, None]]
],
['E',
['E', ['E', None, None], ['E', None, None]],
['E', ['E', None, None], None]],
['E',
['E', ['E', None, None], ['E', None, None]],
['E', None, ['E', None, None]]],
['E',
['E', ['E', None, None], None],
['E', ['E', None, None], ['E', None, None]]],
['E', ['E', ['E', None, None], None],
['E', ['E', None, None], None]],
['E', ['E', ['E', None, None], None],
['E', None, ['E', None, None]]],
['E',
['E', None, ['E', None, None]],
['E', ['E', None, None], ['E', None, None]]],
['E', ['E', None, ['E', None, None]],
['E', ['E', None, None], None]],
['E', ['E', None, ['E', None, None]],
['E', None, ['E', None, None]]],
['E', ['E', ['E', None, None], ['E', None, None]],
['E', None, None]],
['E', ['E', ['E', None, None], None], ['E', None, None]],
['E', ['E', None, ['E', None, None]], ['E', None, None]],
['E', ['E', None, None], [
'E', ['E', None, None], ['E', None, None]]],
['E', ['E', None, None], ['E', ['E', None, None], None]],
['E', ['E', None, None], ['E', None, ['E', None, None]]]]
解题思路
二叉树是一个递归结构，可以用递归的方式构造。首先，构造根节点；然后构造左右子树；最后，罗列左右子树的所有组合方式，即符合要求的所有树结构。
举个例子，要求构造高度为2的平衡二叉树。
- 构造根节点，佔用了一层高度；
- 分别构造左右子树。左右子树最高为1，最低为0。
- 构造高度为1的平衡二叉树，只有一种可能
[E, None, None] - 构造高度为0的不衡二叉树，只有一种可能
None - 罗列左右子树的所有组合方式：
[E, None, None], [E, None, None],[E, None, None], None,None, [E, None, None]。和根节点组合即为所有符合条件的树。
代码实现
def hbal_tree(n):
E = 'E'
if n == 0:
return [None]
if n == 1:
return [[E, None, None]]
n_one_subtree = hbal_tree(n-1)
n_two_subtree = hbal_tree(n-2)
tree_a = [[E, left, right]
for left in n_one_subtree for right in n_one_subtree]
tree_b = [[E, left, right]
for left in n_one_subtree for right in n_two_subtree]
tree_c = [[E, left, right]
for left in n_two_subtree for right in n_one_subtree]
return tree_a + tree_b + tree_c