Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
92 lines (78 sloc) 3.37 KB
def generate_tree_postorder(node_lst, root_index):
""" Return the root of the Huffman tree corresponding
to node_lst[root_index].
The function assumes that the list represents a tree in postorder.
@param list[ReadNode] node_lst: a list of ReadNode objects
@param int root_index: index in the node list
@rtype: HuffmanNode
>>> lst = [ReadNode(0, 5, 0, 7), ReadNode(0, 10, 0, 12), \
ReadNode(1, 0, 1, 0)]
>>> generate_tree_postorder(lst, 2)
HuffmanNode(None, HuffmanNode(None, HuffmanNode(5, None, None), \
HuffmanNode(7, None, None)), \
HuffmanNode(None, HuffmanNode(10, None, None), HuffmanNode(12, None, None)))
>>> lst = [ReadNode(0, 4, 0, 5), ReadNode(0, 1, 0, 2), \
ReadNode(0, 3, 0, 6), ReadNode(1, 0, 1, 1), ReadNode(1, 2, 1, 3)]
>>> generate_tree_postorder(lst, 4)
HuffmanNode(None, HuffmanNode(None, HuffmanNode(4, None, None), \
HuffmanNode(5, None, None)), HuffmanNode(None, HuffmanNode(None, \
HuffmanNode(1, None, None), HuffmanNode(2, None, None)), \
HuffmanNode(None, HuffmanNode(3, None, None), HuffmanNode(6, None, None))))
"""
if node_lst[root_index].r_type == 0:
right = HuffmanNode(node_lst[root_index].r_data)
else:
right = generate_tree_postorder(node_lst, root_index - 1)
if node_lst[root_index].l_type == 0:
left = HuffmanNode(node_lst[root_index].l_data)
else:
if node_lst[root_index].r_type == 0:
left = generate_tree_postorder(node_lst, root_index - 1)
else:
left = generate_tree_postorder(node_lst, root_index - 1 -
get_tree_internal_size(right))
return HuffmanNode(left=left, right=right)
def get_tree_internal_size(tree):
""" Return the number of internal nodes in the tree rooted at 'tree'
@param HuffmanNode tree: The tree rooted at the node 'tree'
@rtype int
>>> tree = HuffmanNode(None, HuffmanNode(None, HuffmanNode(10, None, None),\
HuffmanNode(12, None, None)), \
HuffmanNode(None, HuffmanNode(5, None, None), HuffmanNode(7, None, None)))
>>> get_tree_internal_size(tree)
3
"""
size = 0
if tree.is_leaf():
return 0
if tree.right:
size += get_tree_internal_size(tree.right)
if tree.left:
size += get_tree_internal_size(tree.left)
return size + 1
def improve_tree(tree, freq_dict):
""" Improve the tree as much as possible, without changing its shape,
by swapping nodes. The improvements are with respect to freq_dict.
@param HuffmanNode tree: Huffman tree rooted at 'tree'
@param dict(int,int) freq_dict: frequency dictionary
@rtype: NoneType
>>> left = HuffmanNode(None, HuffmanNode(99), HuffmanNode(100))
>>> right = HuffmanNode(None, HuffmanNode(101), \
HuffmanNode(None, HuffmanNode(97), HuffmanNode(98)))
>>> tree = HuffmanNode(None, left, right)
>>> freq = {97: 26, 98: 23, 99: 20, 100: 16, 101: 15}
>>> improve_tree(tree, freq)
>>> avg_length(tree, freq)
2.31
"""
# freq_dict[byte] = freq
# list of (freq, bytes)
freq_and_bytes = []
for byte in freq_dict:
freq_and_bytes.append((freq_dict[byte], byte))
freq_and_bytes.sort(reverse=True)
# list of (depth, nodes)
depth_and_leaves = get_tree_leaves(tree)
depth_and_leaves.sort()
for i in range(len(depth_and_leaves)):
depth_and_leaves[i][1].symbol = freq_and_bytes[i][1]