Consider a rooted binary tree, where each internal (intermediate) node has 2 chi

Question

Consider a rooted binary tree, where each internal (intermediate) node has 2 children. Assume each node, in particular, the leaves, has a symbol or variable associated with it. For the edges from each node to its children, associate a value 1 to one edge, and a value 0 to the other edge. A special case of such trees is the Huffman tree, or Huffman coding tree. Another special case is binary decision trees. One goal is to determine the code or sequence of 0’s and 1’s that result when one traverses a path from the root to each leaf of the tree. Devise an algorithm, pseudo-code or source code to implement the generation of such root-toleaf codes, using each of the following approaches. (Hint: in case of difficulty handling the general case for arbitrary binary trees, try to first devise solutions for concrete examples of the weighted binary trees of depths 1, 2, 3, 4, 5, 6, 7, 8, and then try to tackle the general case). (Hint: use concepts and tools of procedures, functions and recursion to achieve modularity)

a. If, if-else statements, expressions

Explanation / Answer

#following is the python code for the given problem
# we first create a binary tree with 0's at left and 1's at right at child
# and then call recursive function on root of the tree
# rtolpaths function defined below prints the paths from root to the leaf nodes
class Node:
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None

def rtolpaths(root):
   paths = ""
   recur(root,paths,0)
def recur(node,paths,length):
   if(node == None):
       return
   if(node.left == None and node.right == None):
       printarray(paths + str(node.data))
   else:
       recur(node.left,paths + str(node.data),length +1 )
       recur(node.right,paths + str(node.data),length +1)
def printarray(s):
   for i in range(0,len(s)):
       print s[i],
   print ""
#testcase1
#create a binary tree with 0's at left and 1's at right at child
root = Node(1)
root.left = Node(0)
root.right = Node(1)
root.left.left = Node(0)
root.left.right = Node(1)
root.right.left = Node(0)
root.right.right = Node(1)
rtolpaths(root)
# Given Tree
#         1
#       0   1
#     0 1 0 1

#testcase2
# root = Node(1)
# root.left = Node(0)
# root.right = Node(1)
# root.left.left = Node(0)
# root.left.right = Node(1)
# root.right.left = Node(0)
# root.right.right = Node(1)
# root.left.left.left = Node(0)
# root.left.left.right = Node(1)
# root.left.right.left = Node(0)
# root.left.right.right = Node(1)
# rtolpaths(root)
# Given Tree
#           1
#      0        1
#   0     1   0   1
# 0 1 0   1

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.