1. Main.java
Main method to demonstrate binary tree and binary tree node
a. creates an empty BinaryTree
b. creates random integers to insert into the tree
c. prints out the tree’s nodes and order
d. prints out the tree
import java.util.concurrent.ThreadLocalRandom;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// create an empty BinaryTree
BinaryTree<Integer> myTree = new
BinaryTree<Integer>();
// instantiate new scanner
Scanner keyboard = new Scanner(System.in);
// create random integers and insert them into myTree
for (int i=0; i< 5; i++){
// generate random number in range [-15, 50]
System.out.print("Enter item #"+i+": ");
int randValue = keyboard.nextInt();
// insert each number into myTree
myTree.insert(randValue); }
// System.out.println(myTree);
System.out.print("The nodes of tree are (inorder): ");
System.out.println(myTree.inorder());
System.out.print("The breadth order of the tree is: ");
System.out.println(myTree);
}
}
2. BinaryNode.java
Simple BinaryNode method using a generic that extends Comparable
a. uses a generic that extends Comparable .compareTo()
b. each node contains three objects: data, a left child, and a right child
c. alternate constructor creates a new leaf in binary tree and getters return objects
d. insert(E item) method recursively inserts item as a new leaf
e. boolean method checks if the Left or Right child is empty
f. inorder method recursively traverses the nodes
- if there is a nonempty left child, check there first
- if there is a nonempty right child, check there last
public class BinaryNode<E extends Comparable> {
// each node contains three objects
private E Data;
private BinaryNode<E> leftchild;
private BinaryNode<E> rightchild;
// alternate constructor: creates a new leaf in binary tree
public BinaryNode(E item){
Data = item;
leftchild = null;
rightchild = null; }
// getters: return objects
public E getData(){
return Data; }
public BinaryNode<E> getLeft(){
return leftchild; }
public BinaryNode<E> getRight(){
return rightchild; }
// recursively insert item as a new leaf
public void insert(E item){
int compareV = item.compareTo(Data);
// ignore items already in tree
if (compareV ==0) {
return; }
// left child
else if (compareV < 0){
if (leftchild == null){
leftchild = new BinaryNode<E>(item); }
else {
leftchild.insert(item); }}
// right child
else {
if (rightchild == null){
rightchild = new BinaryNode<E>(item);
return; }
else {
rightchild.insert(item); }}
}
// boolean checks whether Left or Right child is empty
public boolean isLeftChildEmpty(){
return leftchild == null; }
public boolean isRightChildEmpty(){
return rightchild == null; }
// recursive inorder traversal of the nodes
public String inorder(){
String Result = " ";
// if there is a nonempty left child, check there first
if (!isLeftChildEmpty()){
Result = Result + leftchild.inorder(); }
// now print value at the node
Result = Result + " " + Data;
// if there is a nonempty right child, check there last
if (!isRightChildEmpty()){
Result = Result + " " + rightchild.inorder(); }
return Result; }
}
3. BinaryTree.java
Simple BinaryTree method using a generic E that extends Comparable
a. uses a generic E to extend Comparable .compareTo()
b. default constructor establishes tree’s root node
c. insert(E item) method inserts an item into the tree as a binary node
- if tree is empty, create a binary node as the root containing an item
- insert item as a node using the order relation
d. inorder method prints the tree in order
- calls recursive
BinaryNode inorder() and returns roots
e. ToString method prints tree in a breadth first order
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree<E extends Comparable> {
private BinaryNode<E> root;
// default constructor
public BinaryTree(){
root = null; }
// insert an item into the tree as a binary node
public void insert(E item) {
// if tree is empty, create a binary node as the root containing an item
if (root == null) {
root = new BinaryNode<E>(item);
return; }
// insert item as a node using the order relation
root.insert(item); }
// print tree in inorder
public String inorder(){
String Result = "";
if (root == null){
return Result; }
// call recursive BinaryNode inorder()
return root.inorder(); }
// print tree in a breadth first order
public String toString(){
Queue<BinaryNode<E>> myQueue = new LinkedList<BinaryNode<E>>();
String Result = " ";
if (root == null) return Result;
myQueue.add(root);
while (!myQueue.isEmpty()){
BinaryNode<E> current = myQueue.remove();
Result = Result + " " + current.getData();
if (!current.isLeftChildEmpty()){
myQueue.add(current.getLeft()); }
if (!current.isRightChildEmpty()){
myQueue.add(current.getRight()); }}
return Result; }
}