TreeNode.java public class TreeNode<E> { protected E element; protected TreeNode
ID: 3670718 • Letter: T
Question
TreeNode.java
public class TreeNode<E> {
protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E e){
element = e;
}
}
AbstructTree.java
public abstract class AbstractTree<E> implements Tree<E> {
@Override /** Inorder traversal from the root*/
public void inorder() {
}
@Override /** Postorder traversal from the root */
public void postorder() {
}
@Override /** Preorder traversal from the root */
public void preorder() {
}
@Override /** Return true if the tree is empty */
public boolean isEmpty() {
return getSize() == 0;
}
//
//@Override /** Return an iterator for the tree */
public java.util.Iterator<E> iterator() {
// implement iterator
return null;
}
}
Tree.java
public interface Tree<E> extends Iterable<E> {
/** Return true if the element is in the tree */
public boolean search(E e);
/** Insert element o into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(E e);
/** Delete the specified element from the tree
* Return true if the element is deleted successfully */
public boolean delete(E e);
/** Inorder traversal from the root*/
public void inorder();
/** Postorder traversal from the root */
public void postorder();
/** Preorder traversal from the root */
public void preorder();
/** Get the number of nodes in the tree */
public int getSize();
/** Return true if the tree is empty */
public boolean isEmpty();
//
// /** Return an iterator to traverse elements in the tree */
public java.util.Iterator<E> iterator();
}
BST.java
public class BST<E extends Comparable<E>>
extends AbstractTree<E> implements Cloneable {
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary tree */
public BST() {
}
/** Create a binary tree from an array of objects */
public BST(E[] objects) {
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}
/** Returns true if the element is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else // element matches current.element
return true; // Element is found
}
return false;
}
/** Insert element o into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(E e) {
if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted
}
protected TreeNode<E> createNewNode(E e) {
return new TreeNode<E>(e);
}
/** Inorder traversal from the root*/
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
/** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
/** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
if (root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
/** Inner class tree node */
public static class TreeNode<E extends Comparable<E>> {
E element;
TreeNode<E> left;
TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
/** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode<E> getRoot() {
return root;
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list =
new java.util.ArrayList<TreeNode<E>>();
TreeNode<E> current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
break;
}
return list; // Return an array of nodes
}
/** Delete an element from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left children
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element inserted
}
/** Obtain an iterator. Use inorder. */
public java.util.Iterator iterator() {
return inorderIterator();
}
/** Obtain an inorder iterator */
public java.util.Iterator inorderIterator() {
return new InorderIterator();
}
// Inner class InorderIterator
class InorderIterator implements java.util.Iterator {
// Store the elements in a list
private java.util.ArrayList<E> list =
new java.util.ArrayList<E>();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root*/
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode<E> root) {
if (root == null)return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
/** Next element for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
/** Get the current element and move cursor to the next */
public Object next() {
return list.get(current++);
}
/** Remove the current element and refresh the list */
public void remove() {
delete(list.get(current)); // Delete the current element
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
/** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
public Object clone() {
BST<E> tree1 = new BST<E>();
copy(root, tree1);
return tree1;
}
private void copy(TreeNode<E> root, BST<E> tree) {
if (root != null) {
tree.insert(root.element);
copy(root.left, tree);
copy(root.right, tree);
}
}
}
===========================================================
1. Implement the following methods in BST.java
public void breadthFirstTraversal(){
// implement the body
}
public int getNumberOfLeaves(){
// implement the body
return 0;
}
public int getNumberOfNonLeaves(){
// implement the body
return 0;
}
Explanation / Answer
public class A5_TestBST
{
public static void main(String[] args)
{
BST<String> tree = new BST<String>();
tree.insert("George");
tree.insert("Michael");
tree.insert("Tom");
tree.insert("Adam");
tree.insert("Adam");
tree.insert("Adam");
System.out.println("The height of tree is " + tree.height());
// check number of leaf and non-leaf nodes so far
System.out.print(" Number of nodes so far: " + tree.getSize());
System.out.println();
System.out.println("==> Leaves: " + tree.getNumberofLeaves());
System.out.println("--> Non-Leaves: " + tree.getNumberofLeaves());
System.out.println();
// add few more nodes
System.out.println("The height of tree is " + tree.height());
tree.insert("Jones");
System.out.println("The height of tree is " + tree.height());
tree.insert("Peter");
System.out.println("The height of tree is " + tree.height());
tree.insert("Daniel");
System.out.println("The height of tree is " + tree.height());
tree.insert("Red");
System.out.println("The height of tree is " + tree.height());
tree.insert("Green");
System.out.println("The height of tree is " + tree.height());
// Let's check number of leaf and non-leaf nodes again
System.out.print(" Number of nodes so far: " + tree.getSize());
System.out.println();
System.out.println("==> Leaves: " + tree.getNumberofLeaves());
System.out.println("--> Non-Leaves: " + tree.countNonLeaves());
System.out.println();
// Now let's traverse the tree
System.out.print("Inorder(sorted): ");
tree.inorder();
System.out.print(" Postorder : ");
tree.postorder();
System.out.print(" Preorder : ");
tree.preorder();
// Search for an element
System.out.print(" Is Peter in the tree? " + tree.search("Peter"));
// Get a path from the root to Peter
System.out.print(" A path from the root to Peter is: ");
java.util.ArrayList<BST.TreeNode<String>> path = tree.path("Peter");
for (int i = 0; path != null && i < path.size(); i++)
System.out.print(path.get(i).element + " ");
// Try another way to create a tree
Integer[] numbers = {2, 4, 3, 1, 8, 5, 6, 7};
BST<Integer> intTree = new BST<Integer>(numbers);
System.out.print(" Inordertraversal of intTree: ");
intTree.inorder();
}
}
interface Tree<E> extends Iterable<E> {
/** Return true if the element is in the tree */
public boolean search(E e);
/** Insert element o into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(E e);
/** Delete the specified element from the tree
* Return true if the element is deleted successfully */
public boolean delete(E e);
/** Inorder traversal from the root*/
public void inorder();
/** Postorder traversal from the root */
public void postorder();
/** Preorder traversal from the root */
public void preorder();
/** Get the number of nodes in the tree */
public int getSize();
/** Return true if the tree is empty */
public boolean isEmpty();
//
// BLOCKCOMMENT* Return an iterator to traverse elements in the tree */
// public java.util.Iterator<E> iterator();
}
abstract class AbstractTree<E> implements Tree<E> {
@Override /** Inorder traversal from the root*/
public void inorder() {
}
@Override /** Postorder traversal from the root */
public void postorder() {
}
@Override /** Preorder traversal from the root */
public void preorder() {
}
@Override /** Return true if the tree is empty */
public boolean isEmpty() {
return getSize() == 0;
}
//
// @Override BLOCKCOMMENT* Return an iterator for the tree */
// public java.util.Iterator<E> iterator() {
// return null;
// }
}
class BST<E extends Comparable<E>>
extends AbstractTree<E> {
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary tree */
public BST() {
}
/** Create a binary tree from an array of objects */
public BST(E[] objects) {
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}
//====================================================================
// Return the depth of a BST. Depth is the number of the nodes in
// the longest path of the tree. //
// Add code for method public int height() here
//====================================================================
public int height()
{
return height(root);
}
public int height(TreeNode<E> root)
{
if (root == null)
return -1;
else
return Math.max(height(root.left), height(root.right)) + 1;
}
//====================================================================
// Return the number of leaf nodes in a BST.
//
// Add code for method public int getNumberOfLeaves() here
//====================================================================
public int getNumberofLeaves()
{
return getNumberofLeaves(root);
}
public int getNumberofLeaves(TreeNode<E> root)
{
if (root == null)
{
return 0;
}
if (root.left == null && root.right == null)
{
return 1;
}
else
{
return getNumberofLeaves(root.left) + getNumberofLeaves(root.right);
}
}
//====================================================================
// Return the number of non- leaf nodes in a BST.
//
// Add code for method public int getNumberOfNonLeaves() here
//====================================================================
public int countNonLeaves()
{
return countNonLeaves(root);
}
public int countNonLeaves(TreeNode<E> root)
{
if (root.left == null && root.right == null)
return 0;
else if (root.left == null)
return 1 + countNonLeaves(root.right);
else if (root.right == null)
return 1 + countNonLeaves(root.left);
else
return 1 + countNonLeaves(root.left) + countNonLeaves(root.right);
}
@Override /** Returns true if the element is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else // element matches current.element
return true; // Element is found
}
return false;
}
@Override /** Insert element o into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(E e) {
if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted
}
protected TreeNode<E> createNewNode(E e) {
return new TreeNode<E>(e);
}
@Override /** Inorder traversal from the root*/
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
@Override /** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
@Override /** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
if (root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
/** This inner class is static, because it does not access
any instance members defined in its outer class */
public static class TreeNode<E extends Comparable<E>> {
protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
@Override /** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode<E> getRoot() {
return root;
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list =
new java.util.ArrayList<TreeNode<E>>();
TreeNode<E> current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
break;
}
return list; // Return an array of nodes
}
@Override /** Delete an element from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed at by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left children
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element inserted
}
@Override /** Obtain an iterator. Use inorder. */
public java.util.Iterator<E> iterator() {
return new InorderIterator();
}
// Inner class InorderIterator
private class InorderIterator implements java.util.Iterator<E> {
// Store the elements in a list
private java.util.ArrayList<E> list =
new java.util.ArrayList<E>();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root*/
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode<E> root) {
if (root == null)return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
@Override /** More elements for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
@Override /** Get the current element and move to the next */
public E next() {
return list.get(current++);
}
@Override /** Remove the current element */
public void remove() {
delete(list.get(current)); // Delete the current element
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
/** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
}
output
The height of tree is 2
Number of nodes so far: 4
==> Leaves: 2
--> Non-Leaves: 2
The height of tree is 2
The height of tree is 2
The height of tree is 3
The height of tree is 3
The height of tree is 4
The height of tree is 4
Number of nodes so far: 9
==> Leaves: 3
--> Non-Leaves: 6
Inorder(sorted): Adam Daniel George Green Jones Michael Peter Red Tom
Postorder : Daniel Adam Green Jones Red Peter Tom Michael George
Preorder : George Adam Daniel Michael Jones Green Tom Peter Red
Is Peter in the tree? true
A path from the root to Peter is: George Michael Tom Peter
Inordertraversal of intTree: 1 2 3 4 5 6 7 8 sh-4.3$
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.