CSCI 3333 Data Structures Homework 6

Exercises:

(1) (20%) Consider the class IntegerStack which provides only three operations: push(int i), pop(), isEmpty(). Give the algorithms for (a) (8%) peep(), which returns the value of top element of the stack without removing it, and (b) (12%) findMax(), which returns the largest integer element without changing the stack(). If the stack is empty, return null.

(2) (15%) Ex 18.6, p683, text.

(3) (15%) For the tree in Figure 18.33 of page 682, provide the inorder, preorder and postorder traversals of the tree.

Program:

(1) (50%) Consider the binary tree implementation from Chapter 18 of the textbook. See http://users.cis.fiu.edu/~weiss/dsj4/code/ to find the source codes. In particular, modify BinaryNode.java and BinaryTree.java.

(a) Add a method averageHeight( ) for the class BinaryTree so that it returns the 'average height' of every node in the tree. Note that the height of an empty tree is -1.

(b) Add a method printInOrderWithIdentation( ) for the class BinaryTree so it will print the element of the tree in order and with indentation.

For example, if the main method of BinaryTree.java is:

static public void main( String [ ] args )
{
BinaryTree t1 = new BinaryTree( 1 );
BinaryTree t3 = new BinaryTree( 3 );
BinaryTree t5 = new BinaryTree( 5 );
BinaryTree t7 = new BinaryTree( 7 );
BinaryTree t2 = new BinaryTree( );
BinaryTree t4 = new BinaryTree( );
BinaryTree t6 = new BinaryTree( );

t2.merge( 2, t1, t3 );
t6.merge( 6, t5, t7 );
t4.merge( 4, t2, t6 );

System.out.println( "t4 should be perfect 1-7; t2 empty" );
System.out.println( "----------------" );
System.out.println( "t4" );
t4.printInOrder( );
System.out.println( "----------------" );
System.out.println( "t2" );
t2.printInOrder( );
System.out.println( "----------------" );
System.out.println( "t4 size: " + t4.size( ) );
System.out.println( "t4 height: " + t4.height( ) );

// newly added for testing.
System.out.println( "Print inorder with identation: t4" );
t4.printInOrderWithIdentation( );
System.out.println( "t4 average height: " + t4.averageHeight( ));

The output should be:

t4 should be perfect 1-7; t2 empty
----------------
t4
1
2
3
4
5
6
7
----------------
t2
----------------
t4 size: 7
t4 height: 2
Print inorder with identation: t4
1
2
3
4
5
6
7
t4 average height: 1.4285715

For this programming assignment, turn in:

• The modified programs, BinaryNode.java and BinaryTree.java.
• A file, change.txt, to list clearly the code added to BinaryNode.java and BinaryTree.java.
• A screen shot of the execution of the BinaryTree.class (with the min method as above).