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).
Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.