Week 9

Post date: Mar 03, 2019 4:56:36 AM

Chapter 6: Binary Trees:

• Trees,

• Binary Trees,

• Binary Search Trees (BST),

• Implementing Binary Trees,

• Searching a Binary Search Tree

Lab 7 – Binary Search Trees

Objectives: Learn How to Implement and Use Binary Search Trees (BST)

Examples:

• The given java file, BST.java implements a generic BST class with BSTNode as an inner class. Most of the operations are as discussed in the lectures. Moreover, the class is made to be Iterable so that it can be traversed from another class.

• The class, TestIntegerBST shows how to use methods of BST.

Tasks:

1.

1. For the tree in the above figure, manually find the breadth-first, preorder, inorder and postorder traversals.

2. Now Run the TestIntegerBST class using the tree in the above figure and compare the results with what you get manually (in (a) above).

Note: You need to insert the elements in the following (breadth-first) order:

[10, 2, 15, 4, 12, 20].

2. (a) Define the following additional methods inside the BST class:

i). protected boolean isLeaf(BSTNode<T> p): returns true if the node is a leaf

ii). public int getCount(): returns the number of non-empty nodes in the tree

iii). public int leavesCount(): returns the number of leaves in the tree

iv). public void printNonLeaves(): prints nodes of the tree that are not leaves.

v). public void printLeaves(): prints all nodes of the tree that are leaves.

vi). public void printOddNodes(): prints all nodes of the tree that are odd.

vii).public void printOddLeaves(): prints all nodes of the tree that are odd leaves.

Note: Each method needs to call a protected recursive overloaded version that takes the starting node as parameter and does the actual job.

1. Update the TestIntegerBST by adding options to test your methods. Note: No need to test the isLeaf() method. It is needed only in the implementation of leavesCount() and possibly printNoneLeaves().

3. (a) Update the Student class to implement Comparable<T> based on ID number.

(b) Save TestIntegerBST as TestStudentBST and update it to work with Student objects.