Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Name : Kyle Blanchard
- // Due : 12/19/2014
- // Class : CSCI-401
- // Assignment : Add new methods in BST
- // Contact : Kwblanchard@student.stcc.edu
- //package chapter25;
- public 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]);
- }
- @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 successfully
- }
- protected TreeNode<E> createNewNode(E e) {
- return new TreeNode<>(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>> {
- public E element;
- public TreeNode<E> left;
- public 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> 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 list 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 child
- 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 deleted successfully
- }
- @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<>();
- 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;
- }
- // gets the height of the tree
- public int Height() {
- return height(root);
- }
- private int height(TreeNode<E> x) {
- if (x == null)
- return 0;
- else
- return 1 + Math.max(height(x.left), height(x.right));
- }
- // Displays the breadthFirstTraversal of the tree
- public void breadthFirstTraversal() {
- System.out.println(root.element + " " + getNode(root));
- }
- // Gets the node(s) of the tree recursively
- private String getNode(TreeNode<E> x) {
- if (x.left == null && x.right == null) {
- return "";
- } else if (x.left == null) {
- return x.right.element + " " + getNode(x.right);
- } else if (x.right == null) {
- return x.left.element + " " + getNode(x.left);
- } else {
- return x.left.element + " " + x.right.element + " "
- + getNode(x.left) + getNode(x.right);
- }
- }
- // counts the leaves
- public int treeLeavesCount() {
- return leavesCount(root);
- }
- private int leavesCount(TreeNode<E> x) {
- if (x == null)
- return 0;
- else if (x.left == null && x.right == null)
- return 1;
- else
- return leavesCount(x.left) + leavesCount(x.right);
- }
- // counts the nodes
- public int treeNodeCount() {
- return nodeCount(root);
- }
- private int nodeCount(TreeNode<E> x) {
- if (x == null)
- return 0;
- else
- return 1 + nodeCount(x.left) + nodeCount(x.right);
- }
- // uses the number of leaves and nodes to check if the tree is a full binary search tree
- public boolean isFullBST() {
- int leaves = this.treeLeavesCount();
- int nodes = this.treeNodeCount();
- if (nodes == 1)
- return true;
- else {
- if (((nodes / 2) + 1) == leaves)
- return true;
- else
- return false;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement