In: Computer Science
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]
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)