Chapter 4 Trees and Graphs - 4.3
Problem 4.3 Given a sorted (increasing) array, write an algorithm to create a binary tree with minimal height.
Seems that we should construct a complete binary tree.
from queue import *class binary_tree_node: def __init__(self, value = None): self.value = value self.left = None self.right = Nonedef construct_min_btree(array, start, end): if start > end: return mid = (start + end)/2 n = binary_tree_node(array[mid]) n.left = construct_min_btree(array, start, mid - 1) n.right = construct_min_btree(array, mid + 1, end) return n# Test caseif __name__ == "__main__": array = [i for i in range(0, 8)] root = construct_min_btree(array, 0, 7) # Print the binary tree in level-order q = queue() q.enqueue(root) current_level = 0 num_in_current_level = 2**current_level while not q.is_empty(): n = q.dequeue() print n.value, if n.left != None: q.enqueue(n.left) if n.right != None: q.enqueue(n.right) num_in_current_level -= 1 # End of a level if num_in_current_level == 0: current_level += 1 num_in_current_level = 2**current_level print "\n"
