CSC311: Data Structures

Fall 2007

Programming Project 2

Due November 8, Thursday, 2007

Binary Tree Implementation

Description:

Chapter 7 discusses the definition and properties of trees and binary trees (Sections 7.1.2, 7.1.3, 7.3.1, and 7.3.2), and their implementations using a linked structure (Sections 7.1.3 and 7.3.4). The text also discusses the representation of binary trees using array list (Section 7.3.5). In this project, you will implement a binary tree in Java using array list. You will also implement three traversal algorithms of binary trees (Section 7.3.6). 

Task:

Write a Java program to implement a binary tree using array list.

• The ADT (interface) of a binary tree is given in Sections 7.1.3 and 7.3.2.

• The array-list representation of a binary tree is given in Section 7.3.5.

• Three binary tree traversal algorithms, pre-order, in-order, and post-order traversals, are given in Section 7.3.6.  

• Your program should have the following classes and interfaces:

  • The Tree interface, page 271

  • The BinaryTree interface, page 284

  • The Position interface, page 234

  • The BTPosition interface, page 288

  • The BTNode class, page 288

  • The ArrayListBinaryTree class, similar to the LinkedBinaryTree class in pages 290-294

  • The class that implements the pre-order, in-order, and post-order binary tree traversals, refer to pages 299 and 300.

Submission:

• The project will due on November 8, 2007.

• Only electronic submission will be accepted.

• Your submission should include Java source code with necessary documentation for the implemented operations.