Explore a complete Java implementation of a Binary Search Tree (BST), including methods like inOrder, preOrder, postOrder, reverseOrder, getNumLeaves, getHeight, getWidth, getNumNodes, getNumLevels, and isFull. This code lab also provides a ready-to-run BinarySearchTreeRunner with sample data to demonstrate BST properties and traversals. Ideal for students learning data structures and recursion in Java.
This lab was designed to teach you more about Binary Trees. Lab
Description : Write a binary search tree class. For the base lab, you
must write the following methods :: preOrder, postOrder, inOrder,
revOrder, getNumLeaves, getNumLevels, getWidth, getHeight, getNum Nodes,
toString, is Full. The following method groups are extra credit. Each
group will net you an extra ten points on your base 100 point lab grade. You
can complete any or all of the options in any order you prefer. Complete
as many of these options as you can. Group 1 :: write a method to search
the tree for a value and return true or false Group 2 :: write getLargest
and getSmallest methods to return the smallest and largest tree values
Group 3 :: write a level order traversal using the Java LinkedList as a
Queue Group 4 :: write a method to remove a node from the tree - must be
recursive Group 5 :: write a method to display the tree like a tree-level
order traversal might be useful Sample Output : IN ORDER 70 80 85 90 98
100 120 ROOT 90 80 100 70 85 98 120 PRE ORDER 90 80 70 85 100 98 120 POST
ORDER 70 85 80 98 120 100 90 height = 2 width = 5 numLevels = 3 numLeaves
= 4 numNodes = 7 isFullTree = true REVERSE ORDER 120 100 98 90 85 80 70
Tree height is 2 Tree width is 5 Number of leaves is 4 Number of nodes is
7 Number of levels is 3 Tree as a string 70 80 85 90 98 The tree is full.
100 120 © A+ Computer Science --Binary Trees - www.apluscompsci.com BONUS
SECTION The tree contains 100! The does not contain 114! The smallest
tree node 70 The largest tree node 120 Tree before removing any nodes -
using level order traversal. 90 80 100 70 85 98 120 Tree after removing
90. 98 80 100 70 85 120 Tree after removing 70. 98 80 100 85 120 Tree
after removing 85. 98 80 100 120 Tree after removing 98. 100 80 120 Tree
after removing 80. 100 120 Tree after removing 120. 100 Tree after
removing 100.
.
Answer
import
static java.lang.System.*;
import
java.util.LinkedList;
public
class BinarySearchTree {
private TreeNode root;
private
class TreeNode
{
private Comparable treeNodeValue;
private TreeNode leftTreeNode;
private TreeNode rightTreeNode;
public TreeNode( )
{
treeNodeValue = null;
leftTreeNode = null;
rightTreeNode = null;
}
public TreeNode(Comparable value)
{
treeNodeValue = value;
leftTreeNode = null;
rightTreeNode = null;
}
public TreeNode(Comparable value,
TreeNode left, TreeNode right)
{
treeNodeValue = value;
leftTreeNode = left;
rightTreeNode = right;
}
public Comparable getValue()
{
return treeNodeValue;
}
public TreeNode getLeft()
{
return leftTreeNode;
}
public TreeNode getRight()
{
return rightTreeNode;
}
public void setValue(Comparable value)
{
treeNodeValue = value;
}
public void setLeft(TreeNode left)
{
leftTreeNode = left;
}
public void setRight(TreeNode right)
{
rightTreeNode = right;
}
}//clss
public BinarySearchTree() {
root = null;
}
public void add(Comparable val) {
root = add(val, root);
}
@SuppressWarnings("unchecked")
private TreeNode add(Comparable val,
TreeNode tree) {
if (tree == null){
tree = new TreeNode(val);
}
Comparable treeValue = tree.getValue();
int dirTest = val.compareTo(treeValue);
if (dirTest < 0){
tree.setLeft(add(val,
tree.getLeft()));
}
else if (dirTest > 0){
tree.setRight(add(val,
tree.getRight()));
}
return tree;
}
public void inOrder() {
inOrder(root);
System.out.println("\n\n");
}
public void preOrder() {
preOrder(root);
System.out.println("\n\n");
}
public void postOrder() {
postOrder(root);
System.out.println("\n\n");
}
public void revOrder() {
revOrder(root);
System.out.println("\n\n");
}
private void inOrder(TreeNode tree) {
if (tree != null) {
inOrder(tree.getLeft());
System.out.print(tree.getValue() +
" ");
inOrder(tree.getRight());
}
}
private void preOrder(TreeNode tree) {
if (tree != null) {
System.out.print(tree.getValue() +
" ");
preOrder(tree.getLeft());
preOrder(tree.getRight());
}
}
private void postOrder(TreeNode tree) {
if (tree != null) {
postOrder(tree.getLeft());
postOrder(tree.getRight());
System.out.print(tree.getValue() +
" ");
}
}
private void revOrder(TreeNode tree) {
if (tree != null) {
revOrder(tree.getRight());
System.out.print(tree.getValue() +
" ");
revOrder(tree.getLeft());
}
}
public int getNumLevels() {
return getNumLevels(root);
}
private int getNumLevels(TreeNode tree) {
if (tree == null){
return 0;
}
else if (getNumLevels(tree.getLeft())
> getNumLevels(tree.getRight())){
return 1 +
getNumLevels(tree.getLeft());
}
else{
return 1 +
getNumLevels(tree.getRight());
}
}
public int getWidth() {
return getWidth(root);
}
private int getWidth(TreeNode tree) {
if (tree == null){
return 0;
}
if (tree == root){
return 1 + getWidth(tree.getLeft())
+ getWidth(tree.getRight());
}
if (getWidth(tree.getLeft()) >
getWidth(tree.getRight())){
return 1 +
getWidth(tree.getLeft());
}
else{
return 1 +
getWidth(tree.getRight());
}
}
public int getNumLeaves() {
return getNumLeaves(root);
}
private int getNumLeaves(TreeNode tree) {
if (tree == null){
return 0;
}
if (tree.getLeft() == null &&
tree.getRight() == null){
return 1;
}
return getNumLeaves(tree.getRight()) +
getNumLeaves(tree.getLeft());
}
public int getNumNodes() {
return getNumNodes(root);
}
private int getNumNodes(TreeNode tree) {
if (tree == null){
return 0;
}
return 1 + getNumNodes(tree.getRight())
+ getNumNodes(tree.getLeft());
}
public int getHeight() {
return getHeight(root);
}
private int getHeight(TreeNode tree) {
if (tree == null){
return -1;
}
else if (getHeight(tree.getLeft()) >
getHeight(tree.getRight())){
return 1 +
getHeight(tree.getLeft());
}
else{
return 1 +
getHeight(tree.getRight());
}
}
public boolean isFull() {
return isFull(root);
}
private boolean isFull(TreeNode tree) {
if (tree == null){
return false;
}
if (tree.getLeft() == null &&
tree.getRight() == null){
return true;
}
if (tree.getLeft() != null &&
tree.getRight() != null){
return isFull(tree.getLeft())
&& isFull(tree.getRight());
}
return false;
}
public String toString() {
return toString(root);
}
private String toString(TreeNode tree) {
if (tree == null){
return "";
}
return toString(tree.getLeft()) +
tree.getValue() + " " + toString(tree.getRight());
}
}
BinarySearchTreeRunner.java
public
class BinarySearchTreeRunner {
public static void main(String args[]) {
BinarySearchTree t = new
BinarySearchTree();
t.add(90);
t.add(80);
t.add(70);
t.add(85);
t.add(100);
t.add(98);
t.add(120);
System.out.println("in
order");
t.inOrder();
System.out.println("pre
order");
t.preOrder();
System.out.println("post
order");
t.postOrder();
System.out.println("rev
order");
t.revOrder();
System.out.println("height "
+ t.getHeight());
System.out.println("width " +
t.getWidth());
System.out.println("leaves "
+ t.getNumLeaves());
System.out.println("nodes " +
t.getNumNodes());
System.out.println("levels "
+ t.getNumLevels());
System.out.println("string "
+ t.toString());
System.out.println("full " +
t.isFull());
}
}