Skip to main content
Lesson 34 - Binary Trees
ZIPPDF (letter)
Lesson MenuPrevious
  
L.A.34.1 - BSTree page 7 of 7

Background:

In previous lessons you stored a data file, (file20.txt), in different data structures: an array of structures, linked list, and doubly-linked list. In the linked-list lab, 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. You can build the binary tree in this first session, but the rest of the algorithms will be left as program stubs.


Instructions:

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

    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) Search the tree
    (4) Delete from the tree
    (5) Count the nodes in the tree
  3. Start with the source code for the ordered linked-list lab from Lesson 31. The readData method will require small changes. The algorithms inside of all the routines will change, but the basic structure of the program will not.

  4. Complete the code for the insert method. A precondition of the insert routine; the data file will contain no duplicate id values.

  5. Stub the rest of the menu choices.

  6. You may compile and run this program, but you cannot verify if your insert algorithm worked until you learn the material in Lesson 35. Use a data file as provided by your instructor.

  7. Turn in one final assignment when all the menu choices are completed in Lesson 36.


Lesson MenuPrevious
Contact
 ©ICT 2003, All Rights Reserved.