Week Beginning 12/02/01

Mr. T Lysaght

(You can download this BinarySearchTree.java file from the course homepage at:

http://www.cs.may.ie/~tlysaght/CS211/Cs211Lectures.html. Save the file to the same

directory as the TreeNode.java, TreeException.java and BinaryTreeBasis.java

class files.)

1. Add the following methods to the class BinarySearchTree.java.

• A method inorder() which performs an inorder traversal of a binary search tree.
• A method postorder() which performs an postorder traversal of a binary search tree.
• A method preorder() which performs an postorder traversal of a binary search tree.

1. Using the class BinarySearchTree insert construct a binary search tree with the following data:

Integers: 40, 30, 55, 35, 20, 65, 58, 26, 50

2. Delete the following items from the binary search tree:

• The leaf node: 26
• A node with left child only: 65
• A node with two children: 35
• A node with two children and grandchildren: 40

• Call the method to print the tree after each deletion.

1. Empty the tree and reconstruct the original tree with the following values:

Integers: 40, 30, 55, 35, 20, 65, 58, 26, 50

Print the tree using inorder traversal, postorder traversal and preorder traversal.

 

 

 

2. Add methods to the class BinarySearchTree which computes the height of a binary search tree.

• Use methods Height(TreeNode tNode) , int HeightHelper(TreeNode tNode, int height) to traverse the tree, and a method int Max to compute the maximum of the left and right subtrees.

• Note that the height of a binary tree is 1 + the maximum of the heights of the left and right subtrees.