Binary Trees - Building Java Programs: A Back to Basics Approach - page 1005

that each data value is printed at just the right point in time relative to the rest of
the data.
This observation highlights one of the useful properties of a binary search tree.
Once it is constructed, we can traverse the values in sorted order by performing an
inorder traversal of the tree.
Building a Binary Search Tree
We can borrow many elements of the IntTree class that we wrote in the previous
section to produce a new IntSearchTree class. The primary traversal in which we
will be interested is the inorder traversal, so we can include it in our new class and
rename it with the simpler name print .
For this new class, it is best to use the concept of a data invariant, as introduced
in Chapter 8. We can guarantee that the binary search tree property is true for every
node in our tree by making sure that we never violate this invariant relationship.
That will simplify our code because we won't have to test to make sure that our
tree is a binary search tree.
We imagine that a client program will involve code like the following:
1 // This program tests the IntSearchTree class by constructing a
2 // binary search tree of integers and printing its contents as
3 // well as its structure.
4
5 import java.util.*;
6
7 public class IntSearchTreeClient {
8 public static void main(String[] args) {
9 Scanner console = new Scanner(System.in);
10 IntSearchTree numbers = new IntSearchTree();
11 System.out.print("Next int (0 to quit)? ");
12 int number = console.nextInt();
13 while (number != 0) {
14 numbers.add(number);
15 System.out.print("Next int (0 to quit)? ");
16 number = console.nextInt();
17 }
18 System.out.println();
19
20 System.out.println("Tree Structure:");
21 numbers.printSideways();
22 System.out.println("Sorted list:");
23 numbers.print();
24 }
25 }