Question

In: Computer Science

Question 1: Processing Compound Data: Binary Trees A binary tree is a tuple with the following...

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]

Solutions

Expert Solution

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)


Related Solutions

Consider the following type of binary trees: data Tree a = Leaf a | Node (Tree...
Consider the following type of binary trees: data Tree a = Leaf a | Node (Tree a) (Tree a) A tree is balanced if the number of leaves in the left and right subtree of every node differ by at most one. Write a Haskell function balanced that returns whether a tree is balanced or not. balanced :: Tree a -> Bool
Develop a Java application to implement a binary tree data structure. A tree data structure starts...
Develop a Java application to implement a binary tree data structure. A tree data structure starts from the top node, called the root. Each node in the tree has a set of children, which are also nodes of the tree and can have children of their own, and so on. This keeps on going till we get to the bottom of the tree, to the “leaf” nodes. Each node in the tree, except for the root, has a parent. A...
Subject: Homework - Family Trees please give me C codes, thanks FAMILY TREE In a Binary...
Subject: Homework - Family Trees please give me C codes, thanks FAMILY TREE In a Binary Tree, each node has two children at most. To eliminate the restriction by linking the children together to form a list. In this design, each node in the tree needs to contain only two pointers: one to its eldest child and one to its next younger sibling. Using this representation, in each node, the pointer on the left always points down to child; the...
C++ Build a binary tree using a binary tree class member function from the following array...
C++ Build a binary tree using a binary tree class member function from the following array of preorder traversal 3,9,20,15,7 and inorder traversal 9,3,15,20,7. Implement the constructor, destructor and all member functions including print postorder traversal of the binary tree.
Question 2: Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary...
Question 2: Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary Search Tree in ascending or deceasing order. The order type is an input to the method and can be "ascending" or "descending". The ascending input would return the node values of the tree beginning with the smallest and ending with the largest, descending returns the opposite. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify...
Consider an implementation of binary trees with Scheme lists, as in the following example:
Consider an implementation of binary trees with Scheme lists, as in the following example: Before proceeding, it may be useful to define three auxiliary functions (left T), (right T) and (val T) which return the left subtree, the right subtree, and the value in the root of tree T, respectively. (a) Write a recursive function (n-nodes T), which returns the number of nodes in the tree T. The following example illustrates the use of this function: > (n-nodes T)8 (b) Write a recursive function...
Using the following definitions for a binary tree, typedef struct bintreenode {     int data;     struct bintreenode*...
Using the following definitions for a binary tree, typedef struct bintreenode {     int data;     struct bintreenode* left;     struct bintreenode* right; } btreenode; // Used for a node in the queue. typedef struct node {     btreenode* nodePtr;     struct node* next; } node; // Used to represent the queue efficiently. typedef struct queue {     node* front;     node* back; } queue; Implement the following functions: void bfs(btreenode* root) // Prints a breadth first search traversal of the binary search tree rooted at root....
Create a Binary Search Tree for the following data and do In-order, Preorder and Post-order traversal...
Create a Binary Search Tree for the following data and do In-order, Preorder and Post-order traversal of the tree. 50, 60, 25, 40, 30, 70, 35, 10, 55, 65, 5 Write an algorithm to delete a node in Singly Linked List                            [12 Write an algorithm of Binary Search                                                              [10] Write a program in ‘C’ to generate Fibonacci series using recursion            [8]
Question - 1 Using the structural node and methods discussed in Binary Search Tree lectures, create...
Question - 1 Using the structural node and methods discussed in Binary Search Tree lectures, create a method for the Binary Search Tree that takes an unsorted input list and constructs a Binary Search Tree based on its values. Any duplicate value will only appear once on the tree. This method outputs a Binary Search Tree structure (not an enumeration of the tree). Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly...
A binary tree data type is defined in OCaml as follows: type 'a binary_tree = |...
A binary tree data type is defined in OCaml as follows: type 'a binary_tree = | Empty | Node of 'a * 'a binary_tree * 'a binary_tree;; The mirror of a binary tree is defined as the tree obtained by reversing its left and right subtrees at each level. Write an OCaml function is_mirror: 'a binary_tree -> 'a binary_tree -> bool = <fun> to determine if one tree is the mirror of another. Your function must take into account the...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT