Question

Question 1:

Processing Compound Data: Binary Trees

A binary tree is a tuple with the following recursive structure  

("btree", [val, left_tree, right_tree])

where first part of the tuple is a string "btree" and second part of the tuple is a list in which val is the value at the root and left_tree and right_tree are the binary trees for the left and right children or

("btree",[]) for the empty tree.  

(A)

Implement a binary tree ADT.

Type Name Description

Create the following tree in python. Use this tree to test the above functions of the tree ADT.

(B)

Implement the functions preorder,inorder and postorder.

Function preorder takes a tree as an argument and returns a list with the root value being the first element in the list followed by the elements of the left tree and then right tree. Function inorder takes a tree as an argument and returns a list with the elements of the left tree, followed by the root value and then right tree.

Function postorder takes a tree as an argument and returns a list with the elements of the left tree, followed by the elements of the right tree and then root value.

For example

preorder(t1) => [7, 5, 11, 9]

inorder(t1) => [5, 7, 9, 11]

postorder(t1) =>[5, 9, 11, 7]

Answer 1

Python program to for tree traversals :

  

# A class that represents an individual node in a

# Binary Tree

class Node:

def __init__(self,key):

self.left = None

self.right = None

self.val = key

  

  

# A function to do inorder tree traversal

def printInorder(root):

  

if root:

  

# First recur on left child

printInorder(root.left)

  

# then print the data of node

print(root.val),

  

# now recur on right child

printInorder(root.right)

  

  

  

# A function to do postorder tree traversal

def printPostorder(root):

  

if root:

  

# First recur on left child

printPostorder(root.left)

  

# the recur on right child

printPostorder(root.right)

  

# now print the data of node

print(root.val),

  

  

# A function to do preorder tree traversal

def printPreorder(root):

  

if root:

  

# First print the data of node

print(root.val),

  

# Then recur on left child

printPreorder(root.left)

  

# Finally recur on right child

printPreorder(root.right)

  

  

#Drivercode

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

print ("Preorder traversal of binary tree is")

printPreorder(root)

  

print ("\nInorder traversal of binary tree is")

printInorder(root)

  

print ("\nPostorder traversal of binary tree is")

printPostorder(root)