Skip to main content
ICT
Lesson AB30 - Binary Search Trees
 
Main Previous Next
Title Page >  
Summary >  
Lesson A1 >  
Lesson A2 >  
Lesson A3 >  
Lesson A4 >  
Lesson A5 >  
Lesson A6 >  
Lesson A7 >  
Lesson A8 >  
Lesson A9 >  
Lesson A10 >  
Lesson A11 >  
Lesson A12 >  
Lesson A13 >  
Lesson A14 >  
Lesson A15 >  
Lesson A16 >  
Lesson A17 >  
Lesson A18 >  
Lesson A19 >  
Lesson A20 >  
Lesson A21 >  
Lesson A22 >  
Lesson AB23 >  
Lesson AB24 >  
Lesson AB25 >  
Lesson AB26 >  
Lesson AB27 >  
Lesson AB28 >  
Lesson AB29 >  
Lesson AB30 >  
Lesson AB31 >  
Lesson AB32 >  
Lesson AB33 >  
Vocabulary >  
 

LAB ASSIGNMENT AB30.1 page 13 of 15

Binary Search Tree

Background:

In previous lessons, you stored a data file (file20.txt) in different data structures: an array, a linked list, and a doubly-linked list. In the linked-list labs in Lesson AB29, we built the data structure, printed it out, searched for values, and deleted values. We will solve the same fundamental tasks using a binary tree as the data structure.

Instructions:

  1. You may assume the following type definitions apply in this lab assignment.

    public class TreeNode{
      private Object value;
      private TreeNode left;
      private TreeNode right;

      public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight){
        value = initValue; left = initLeft; right = initRight;
      }

      public Object getValue() {
        return value;
      }

      public TreeNode getLeft() {
        return left;
      }

      public TreeNode getRight() {
        return right;
      }

      public void setValue(Object theNewValue) {
        value = theNewValue;
      }

      public void setLeft(TreeNode theNewLeft) {
        left = theNewLeft;
      }

      public void setRight(TreeNode theNewRight) {
        right = theNewRight;
      }
    }

  2. Build a main menu with the following choices.

    (1) Read a file from disk, build the binary tree
    (2) Print the tree in order
    (3) Count the nodes in the tree

  3. Implement a Binary Search Tree class with the following methods:

    1. public BinarySearchTree()
    2. public void insert(Comparable next)
    3. private TreeNode insertHelper(TreeNode root, Comparable next)
    4. public void printInOrder()
    5. private void printInorderHelper(TreeNode root)
    6. public int countNodes()
    7. private int countNodesHelper(TreeNode root)

 

Main Previous Next
Contact
 © ICT 2006, All Rights Reserved.