AP Computer Science

Labs 15 -16

Data Structures – Binary Trees from scratch

Lab 15

In the Labs15_16 project, complete the class, BinarySearchTree, by reading and following the documentation. Write the method, printPostOrder. Complete the application program, Lab 15, to create a new BinarySearchTree, read the string data from the file “treeData.txt”, insert the strings into a binary tree and then print them out in both in order and post order. Remember that uppercase will appear before lowercase when printed in order. For this lab you only have to complete the two insert methods and printPostOrder.

Lab 16

Complete the class, NodeInfo, that has instance variables itsValue, itsLevel (in a binary search tree), and itsRank (its place in alphabetical order). The value will be a string (read from treeData.txt), itsLevel and its rank will be set by a method setLevelandRank. Your toString method should print the word, level and rank. Complete lab 16 to create TreeNodes that contain NodeInfo as their value. You will have to make NodeInfo implement Comparable and if you use compareToIgnoreCase in your definition of compareTo, your data will come out in alphabetical order. Complete the size method. Also complete setLevelandRank and add the instance variable, itsNodeRank. Print out an inorder traversal. It should look like this.

The number of nodes in the tree is 29

array

rank = 0 level = 3

ArrayList

rank = 1 level = 4

binary search tree

rank = 2 level = 2

binary tree

rank = 3 level = 3

data structures

rank = 4 level = 5

element

rank = 5 level = 4

HashMap

rank = 6 level = 1