Trees - Data Structures and Problem Solving Using Java - page 662

1 // BinaryTree class; stores a binary tree.
2 //
3 // CONSTRUCTION: with (a) no parameters or (b) an object to
4 // be placed in the root of a one-element tree.
5 //
6 // *******************PUBLIC OPERATIONS**********************
7 // Various tree traversals, size, height, isEmpty, makeEmpty.
8 // Also, the following tricky method:
9 // void merge( Object root, BinaryTree t1, BinaryTree t2 )
10 // --> Construct a new tree
11 // *******************ERRORS*********************************
12 // Error message printed for illegal merges.
13
14 public class BinaryTree<AnyType>
15 {
16 public BinaryTree( )
17 { root = null; }
18 public BinaryTree( AnyType rootItem )
19 { root = new BinaryNode<AnyType>( rootItem, null, null ); }
20
21 public BinaryNode<AnyType> getRoot( )
22 { return root; }
23 public int size( )
24 { return BinaryNode.size( root ); }
25 public int height( )
26 { return BinaryNode.height( root ); }
27
28 public void printPreOrder( )
29 { if( root != null ) root.printPreOrder( ); }
30 public void printInOrder( )
31 { if( root != null ) root.printInOrder( ); }
32 public void printPostOrder( )
33 { if( root != null ) root.printPostOrder( ); }
34
35 public void makeEmpty( )
36 { root = null; }
37 public boolean isEmpty( )
38 { return root == null; }
39
40 public void merge( AnyType rootItem,
41 BinaryTree<AnyType> t1, BinaryTree<AnyType> t2 )
42 { /* Figure 18.16 */ }
43
44 private BinaryNode<AnyType> root;
45 }

figure 18.13
The BinaryTree class,
except for merge

Two basic constructors are provided. The one at lines 16 and 17 creates an
empty tree, and the one at lines 18 and 19 creates a one-node tree. Routines to
traverse the tree are written at lines 28-33. They apply a BinaryNode method to