In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.

Write a function cbal-tree to construct completely balanced binary trees for a given number of nodes. The predicate should generate all solutions via backtracking. Put the letter 'x' as information into all nodes of the tree.

# Example:

# * cbal-tree(4,T).

# T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ;

# T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil)) ;

# etc......No

def completely_balanced_trees(node_count):

if node_count == 0:

return [None]

else:

right_count = (node_count - 1) / 2

left_count = (node_count - 1) - right_count

left_trees = completely_balanced_trees(left_count)

right_trees = completely_balanced_trees(right_count)

trees = []

for left in left_trees:

for right in right_trees:

trees.append(("x", left, right))

if left_count != right_count:

trees.append(("x", right, left))

return trees

OK, I'm using tuples for trees again. So sue me.

## No comments:

Post a Comment