Assignment 4

This assignment consists of several small parts. The assignment is an exercise on binary trees and recursion. Here is a source code for a class called T_n. T_n is an implementation of a binary tree that can hold integers. You shall add methods to the class but no other major modifications are allowed.

The methods in parts A-D shall be recursive and may NOT use any help methods, global or static variables, or extra arguments than those stated. An argument of void means no arguments. For Part E you are allowed to implement the method based on methods in Parts A and D.

Part A: Depth of a tree (1p)

The depth of a tree is 1 + the depth of the longest subtree. Write a method int T_n::depth(void) that returns the depth of a binary tree.

Part B: Same shape, isomorphic (1p)

Write a method bool T_n::same_shape(T_n*) that determines if the tree given as parameter has the same shape as the called tree. The data values does not matter.

Part C: Mirror shape (1p)

Write a method bool T_n::mirror_shape(T_n*) that determines if the called tree and the tree given as parameter are mirror shapes of each other.

Part D: Perfectly balanced (2p)

A binary tree is perfectly balanced if the number of nodes in the left and right subtrees differ by at most one. Write a method int T_n::num_nodes(void) that returns the number of nodes in a binary tree. Use that method to write a method bool T_n::perf_bal(void) that determines if a binary tree is perfectly balanced or not.

Part E: Full binary tree (1p)

A binary tree is full if it contains as many nodes as it can without adding an extra level. Write a method bool T_n::is_full() that determines if a binary tree is full. An empty tree is full since it contains as many nodes as it can without adding any extra level.

Part F: Binary search tree (2p)

A binary search tree (BST) is a binary tree in which the nodes are labeled with elements of the set. The important property of a binary search tree is that all elements stored in its left subtree of any node x are less than the element stored at x and all elements stored in its right subtree are greater than the element stored at x. Note that interesting property of a BST is if we list all the nodes of the BST in inorder, then the elements listed at those nodes are listed in sorted order.

Construct a BST by method given in Justin Pearsson's notes. Then, write a method bool T_n::deletenode(int n) that deletes an occurrence of n (if any) from the BST.

Part G: Reconstructing a tree (2p)

You all know about the three tree traversals: inorder, preorder and postorder. It is possible to reconstruct the original tree for some combinations of these traversals.

Write a method T_n* T_n::reconstruct(...) that given two arrays, containing the preorder and inorder respectively, returns the original tree.

For this part you may add help methods if you need and determine how the traversals shall be passed to the function, i.e., what arguments it shall take. Also, you must be able to show whether you got the right tree. You can do this by writing a function is_reconstruct which takes reconstructed tree and the tree you planned to make and guarantees that it is the one. Give two examples where you plan a tree, give its preorder and inorder arrangements and you get back the original tree.

Hints

No methods require more than a few lines of code. The implementation often follows quite directly from the recursive definitions.

Trees are recursive in their nature and the problems above are best solved if the solutions are based on the solutions for the subtrees. Do NOT forget the base cases. They often arise from the corresponding properties for the empty trees.

Deadline

Wednesday, February 27, 2002, 15.00 sharp! Please respect this deadline, if you are not finished with the entire assignment by this time submit everything you have produced and I will mark it based on your presentation. Otherwise you will get 0 (zero) points. Thanks.

Submit

• Well-documented source code.
• Descriptions of your algorithms and definitions used for the different parts.
• You should also provide a user-interface which gives options to the user to construct such trees and check all functionalities presented above.

Don't forget the cover page!

Go back to the assignments page.

Last modified: Fri Feb 15 14:32:09 MET 2002 by Zoran Radovic. This page has been accessed 2394 times.