Binary Tree ExampleCIT 594, Spring
2005 |

Your Binary Tree Assignment asks you to implement an API (Application Programmer's Interface) for a Binary Tree ADT (Abstract Data Type). Here is what you are giving the application programmer to work with:

**Constructors:**

**public BinaryTree(T value)**-
**public BinaryTree<T>(T value, BinaryTree<T> leftChild, BinaryTree<T> rightChild)**

**Methods:**

**public T getValue()**`public void setValue(T value)`

**public BinaryTree<T> getLeftChild()****public void setLeftChild(BinaryTree<T> newLeftChild)**

**public BinaryTree<T> getRightChild()****public void setRightChild(BinaryTree<T> newRightChild)**

**public boolean isLeaf()****public boolean equals(Object object)**

Notice that the

that could be
thrown by a couple of these methods is a **IllegalArgumentException**`RuntimeException`

, which
means that the user does not need to wrap every call to these methods with```
try...catch
```

.

Suppose I wanted to use your BinaryTree class to sort an array of numbers.
I can do this by putting the numbers into a *sorted binary tree*--a tree
in which each node contains a number, all the numbers in the left subtree of
a node are smaller than the number in the node, and all the numbers in the right
subtree of a node are larger than or equal to the number in the node. Like this:

Here's what I need to do:

- Create a root node containing some number (I don't care which one) from the array.
- For each remaining number, insert it into the binary tree, keeping the tree sorted. (This is a recursive search to find the right place to put the number.)
- Traverse the binary tree in
**inorder**(left subtree, root, right subtree), copying each number back into the array.

Notice that the tree in the picture above happens to be nicely balanced. It's a lot of work to keep a tree balanced, and I have no reason to do so. So I won't.

Here's my code:

import java.util.Arrays; import java.util.Random; /** * A simple demonstration of the use of the BinaryTree API. * @author David Matuszek */ public class BinaryTreeSort {

/** * Creates and executes an instance of this class. * @param args Unused. */ public static void main(String[] args) { new BinaryTreeSort().sortDemo(); }

/** * Demonstrates the use of a binary tree to perform a sort. */ private void sortDemo() { int[] array; array = makeRandomArray(); System.out.println("Random array: " + Arrays.toString(array)); sort(array); System.out.println("Sorted array: " + Arrays.toString(array)); }

/** * Sorts an array. * @param array The array to be sorted. */ private void sort(int[] array) { // Create root of tree with first number in array BinaryTree<Integer> tree = new BinaryTree<Integer>(array[0]); // Put the rest of the numbers into the binary tree for (int i = 1; i < array.length; i++) { insertNumberIntoTree(array[i], tree); } // Get the numbers back out (sorted) copyTreeIntoArray(tree, array); }

/** * Do an inorder walk of the tree to get the numbers * out in sorted order. * @param tree The sorted tree of numbers. * @param array The location in which to put the numbers. */ private void copyTreeIntoArray(BinaryTree<Integer> tree, int[] array) { // This is just a facade method, so that the user does not // have to supply an extra zero argument copyTreeIntoArray(tree, array, 0); }

/** * Copies a binary tree into an array, in inorder. * @param tree The tree to copy. * @param array The array to get the values. * @param i The next location in the array to receive a value. */ private int copyTreeIntoArray(BinaryTree<Integer> tree, int[] array, int i) { // Note: The hard part was setting "i" to the correct value if (tree == null) return i; i = copyTreeIntoArray(tree.getLeftChild(), array, i); array[i] = tree.getValue(); i = copyTreeIntoArray(tree.getRightChild(), array, i + 1); return i; }

/** * Puts the given number into the tree in the proper place * to keep the tree sorted. * @param n The number to put int the sorted binary tree. * @param tree The binary tree to receive the number. */ private void insertNumberIntoTree(int n, BinaryTree<Integer> tree) { // Smaller numbers go to the left if (n < tree.getValue()) { if (tree.getLeftChild() == null) { // base case tree.setLeftChild(new BinaryTree<Integer>(n)); } else { // recursive case insertNumberIntoTree(n, tree.getLeftChild()); } } // Larger and equal numbers go to the right else if (tree.getRightChild() == null) { // base case tree.setRightChild(new BinaryTree<Integer>(n)); } else { // recursive case insertNumberIntoTree(n, tree.getRightChild()); } }

/** * Creates a random array of 12 two-digit numbers. * @return The array of random numbers. */ private int[] makeRandomArray() { Random rand = new Random(); int[] result = new int[12]; for (int i = 0; i < result.length; i++) { result[i] = rand.nextInt(89) + 10; } return result; }

}