python programming

haufmann tree in python

ELEC-62

1

Information Theory and Coding, Spring 2017

Lab 1

Huffman Tree:
The attached Python code includes the first steps in generating a Huffman tree. You need to finish the
code according to the comments included in the code. The main aspect is writing the code to sort the
list of letters in ascending order of probabilities. The characters of the English language are in the
attached table.

class HuffmanTree(object):
def __init__(self, symbol=’*’, p=0, child0=None, child1
=None):
self.symbol = symbol
self.p = p
self.child0 = []
self.child1 = []
if child0 is not None:
for child in child0:
self.add_child(child0)
if child1 is not None:
for child in child1:
self.add_child(child0)
def __repr__(self):
return self.symbol
def add_child0(self, node):
assert isinstance(node, HuffmanTree)
self.child0.append(node)
def add_child1(self, node):
assert isinstance(node, HuffmanTree)
self.child1.append(node)

# Need to finish the same process for all letters: c, d, …, z
a = HuffmanTree(symbol=’a’, p=8.167)
print ‘p(‘ + a.symbol + ‘) = ‘ + str(a.p)
b = HuffmanTree(symbol=’b’, p=1.492)
print ‘p(‘ + b.symbol + ‘) = ‘ + str(b.p)

# Need to include all letters in your tree below
MyTree = [a, b]
print MyTree

# Need to finish the funcition below that sorts the list MyTree
in ascending order of probabilities.
def sort_mytree(tree=None):
if tree is None:
tree = []
# Write your code here to sort the tree
return tree

# Don’t need to do anything here. The print below is to verify
that your code sorts your tree correctly in ascending order of
probabilities.
MyTree = sort_mytree(MyTree)
print MyTree

1