Friday, 3 February 2017

Chapter 25 Exercise 4, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

25.4 (Implement preorder traversal without using recursion) Implement the
preorder method in BST using a stack instead of recursion. Write a test pro-
gram that prompts the user to enter 10 integers, stores them in a BST, and
invokes the preorder method to display the elements.

import java.util.LinkedList;
import java.util.ArrayList;

public class Exercise04 {

public static void main(String[] args) {
BST<Integer> tree = new BST<>(new Integer[] {60, 55, 100, 45, 57, 67, 107, 101, 59});
tree.preorder();
System.out.println();
tree.preorder2();
}

static class BST<E extends Comparable<E>> extends AbstractTree<E> {
protected TreeNode<E> root;
protected int size = 0;

public void preorder2() {
if(root == null) {
return;
}

while (!stack.isEmpty()) {
TreeNode<E> node = stack.getFirst();
if (!list.contains(node.left)) {
}
if ((node.left != null) && (!list.contains(node.left))) {
stack.push(node.left);
} else {
stack.removeFirst();
if (node.right != null) {
}
}
}
for (TreeNode<E> treeNode : list) {
System.out.print(treeNode.element + " ");
}
}

public void inorder2() {
if(root == null) {
return;
}

while (!stack.isEmpty()) {
TreeNode<E> node = stack.getFirst();
if ((node.left != null) && (!list.contains(node.left))) {
stack.push(node.left);
} else {
stack.removeFirst();
if (node.right != null) {
}
}
}
for (TreeNode<E> treeNode : list) {
System.out.print(treeNode.element + " ");
}
}

/** Displays the nodes in a breadth-first traversal */
if(root == null) {
return;
}
ArrayList<TreeNode<E>> list = new ArrayList<>();
while(!list.isEmpty()) {
ArrayList<TreeNode<E>> tmpList = new ArrayList<>();
for (TreeNode<E> treeNode : list) {
if(treeNode!= null) {
System.out.print(treeNode.element + " ");
}
list = tmpList;
}
}
}

public boolean isFullBST() {
return size == Math.round(Math.pow(2, height()) - 1);
}

/** Returns the height of this binary tree, i.e., the
* number of the nodes in the longest path of the root to a leaf */
public int height() {
return height(root);
}

public int height(TreeNode<E> node) {
if(node == null) {
return 0;
} else {
return 1 + Math.max(height(node.left), height(node.right));
}
}

/** 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]);
}

@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) {
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);
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;
}
}

static 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() {
return null;
}
}

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();

public java.util.Iterator<E> iterator();
}
}