Java Implementation: Tree and Heap

This assignment consists of two tasks: Task 1 requires creating a Java application that constructs an expression (binary) tree from a postfix expression using stacks, with the binary tree implemented as a doubly linked list created from scratch. The task also includes writing comments to explain the logic of the code. In Task 2, students are asked to implement array-based heap operations such as createHeap(), heapIsEmpty(), heapInsert(newItem), and heapDelete(). A program is required to demonstrate these methods.

CSIS3475-070 Winter 2017
Assignment# 4
Due date: Monday April 3rd, 2017
Total scores: 20
Note: Please submit your assignment on the blackboard course web page. There are
maximum three attempts, latest attempt will be graded. This is individual student work,
please submit your own work.
In case of cheating both copy and copied will get zero and violations of Academic Integrity
policy will be reported to the appropriate Responsible Administrator for adjudication.
For this application, don’t forget to add comments to explain logic of your code. Please
submit your complete Java project, MS word documents will not be accepted and will not
be graded.
Task 1 (10 Points):
Create a Java application to construct an expression (binary) tree from the postfix expression
using Stacks. Note: Construct trees using stacks. For this task, create a binary tree using
doubly linked list. Doubly linked list class should be created from scratch and for stack class,
you can use JCF Stack class. Write a program to demonstrate.
Task 2 (10 Points):
Write a Java program for array-based implementation of a heap. Create following basic
methods:
createHeap() // Creates an empty heap.
heapIsEmpty() // Determines whether a heap is empty.
heapInsert(newItem) // Inserts newItem into a heap.
heapDelete() // Retrieves and then deletes a heap’s root item.
Write a program to demonstrate these methods. For reference, have a look at the array-
based implementation of a heap textbook page 669 – 673.