ICOM 4035 – Data Structures

Fall 2007

Laboratory 7: Trees and Binary Search Trees

1.    Objectives

1. Introduce the tree as a data structure.
2. Compare trees to lists, stacks and queues.
3. Practice operations on trees.

2.    Overview

Just until now you have seen several data structures and their characteristics. Among these the linked list, the stack and the queue. As seen the linked list allows dynamic expansion of the storage size easily in contrast to an array list which is implemented using dynamic arrays. However the linked list had the issue of access, due to the fact that one only has access to the first element of the list and some times the last and in order to get the element in the middle one had to run the list until finding it.

The other two data structures, the stack and the queue, were similar to the linked list but didn’t allow extracting the element from the middle of the list. Again these were useful for applications with special behaviors.

As an alternative to solve these issues of accessing elements faster than a linked list can but without loosing the ability to add new elements in an efficient way comes the use of Trees. This data structure uses hierarchical organization to access data.

Example of a Tree

The first node is known as the root of the tree and it has pointer references to other nodes known as descendants. Locally each node can be seen as the root or parent of a sub-tree. At the end there will be some nodes without any children, these are referred as leaves. A tree also has its height which is the maximum number of connections from a leaf up to the root.

There is a special type of tree called the BinarySearchTree which has all nodes sorted according to a specific key value. In this type of tree we have that a parent node can have at most two children, the one at the left having a key value smaller than the parent and the one at the right having a key value larger than the parent.

3.    Practice

Download lab7.tar.gz and implement the missing methods inside of LinkedBinaryTree.java (addRoot(), insertLeft(), insertRight() and remove()). Then finish the recursive method HelloPrint inside of lab7.java. Implement this method in a way that the output is “Hello World!”. Note that is kind like the pre-order iteration but with minor details.

Hint: Draw the LinkedBinaryTree