SHARE
TWEET

Untitled

a guest Jan 19th, 2020 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package binaryTree;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5.  
  6. /**
  7.  * A partial implementation of sorted binary trees.
  8.  * <p>
  9.  * The three constructors (construct an empty tree ({@link #BinaryTree()}, or a tree with a root value but no subtrees
  10.  * ({@link #BinaryTree(Comparable)}, or a tree with a root value and left and right subtrees
  11.  * ({@link #BinaryTree(Comparable, BinaryTree, BinaryTree)}), as well as the {@link #isEmpty()} method are already implemented.
  12.  * <p>
  13.  * For the remaining methods specified in the {@link BTree} interface ({@link #insert(Comparable)}, {@link #getValue()},
  14.  * {@link #setValue(Comparable)}, {@link #getLeft()}, {@link #setLeft(BTree)}, {@link #getRight()}, {@link #setRight(BTree)},
  15.  * {@link #contains(Comparable)}, and {@link #traverse()}) only a "stub" is provided.  For the logbook exercise you
  16.  * should implement these methods.
  17.  * <p>
  18.  * Don't forget to test your implementation!
  19.  *
  20.  * @param <T> the type of value stored in the tree.
  21.  * @author Hugh Osborne.
  22.  * @version December 2019.
  23.  */
  24. public class BinaryTree<T extends Comparable<? super T>> implements BTree<T> {
  25.  
  26.     /**
  27.      * The root node of this tree.
  28.      */
  29.     private TreeNode<T> root;
  30.  
  31.     /**
  32.      * Construct an empty tree.
  33.      */
  34.     public BinaryTree() {
  35.         root = null;
  36.     }
  37.  
  38.     /**
  39.      * Construct a singleton tree.
  40.      * A singleton tree contains a value in the root, but the left and right subtrees are
  41.      * empty.
  42.      *
  43.      * @param value the value to be stored in the tree.
  44.      */
  45.     public BinaryTree(T value) {
  46.         root = new TreeNode<>(value);
  47.     }
  48.  
  49.     /**
  50.      * Construct a tree with a root value, and left and right subtrees.
  51.      *
  52.      * @param value the value to be stored in the root of the tree.
  53.      * @param left  the tree's left subtree.
  54.      * @param right the tree's right subtree.
  55.      */
  56.     public BinaryTree(T value, BinaryTree<T> left, BinaryTree<T> right) {
  57.         root = new TreeNode<>(value, left, right);
  58.     }
  59.  
  60.     /**
  61.      * Check if the tree is empty.
  62.      *
  63.      * @return true iff the tree is empty.
  64.      */
  65.     public boolean isEmpty() {
  66.         return root == null;
  67.     }
  68.  
  69.     /**
  70.      * Insert a new value in the binary tree at a position determined by the current contents
  71.      * of the tree, and by the ordering on the type T.
  72.      *
  73.      * @param value the value to be inserted into the tree.
  74.      */
  75.     public void insert(T value) throws BinaryTreeAccessError {
  76.         // implement insert(T value) here
  77.         if (isEmpty()) {
  78.             root = new TreeNode<>(value);
  79.         } else if (value.compareTo(getValue()) < 0) {
  80.             getLeft().insert(value);
  81.         } else {
  82.             getRight().insert(value);
  83.         }
  84. //        System.out.println(root);
  85.     }
  86.  
  87.     @Override
  88.     public String toString() {
  89.         return "BinaryTree{" +
  90.                 "root=" + root +
  91.                 '}';
  92.     }
  93.  
  94.     /**
  95.      * Get the value stored at the root of the tree.
  96.      *
  97.      * @return the value stored at the root of the tree.
  98.      */
  99.     public T getValue() throws BinaryTreeAccessError {
  100.         // Note: it might make sense to define getValue() to throw a (custom) exception if an attempt
  101.         // is made to access a value from an empty tree.
  102.         // However, since a tree is empty iff its root node is null, it is also acceptable to rely
  103.         // on Java's NullPointerException.
  104.         // This comment also applies to the other get and set methods defined in this interface.
  105.         // placeholder return value below - replace with implementation of getValue()
  106.  
  107.         if (isEmpty()) {
  108.             throw new BinaryTreeAccessError("Cannot access root. Empty tree");
  109.         }
  110.         return root.getValue();
  111.     }
  112.  
  113.  
  114.     /**
  115.      * Change the value stored at the root of the tree.
  116.      *
  117.      * @param value the new value to be stored at the root of the tree.
  118.      */
  119.     public void setValue(T value) throws BinaryTreeAccessError {
  120.         // implement setValue(T value) here
  121.         if (isEmpty()) {
  122.             throw new BinaryTreeAccessError("BinaryTree doesn't exists. Cannot access root");
  123.         }
  124.         root.setValue(value);
  125.  
  126.     }
  127.  
  128.  
  129.     /**
  130.      * Get the left subtree of this tree.
  131.      *
  132.      * @return This tree's left subtree.
  133.      */
  134.     public BTree<T> getLeft() throws BinaryTreeAccessError {
  135.         if (isEmpty()) {
  136.             throw new BinaryTreeAccessError("Left tree is empty");
  137.         }
  138.         return root.getLeft();
  139.     }
  140.  
  141.     /**
  142.      * Change the left subtree of this tree.
  143.      *
  144.      * @param tree the new left subtree.
  145.      */
  146.     public void setLeft(BTree<T> tree) throws BinaryTreeAccessError {
  147.         // implement setLeft(BTree<T> tree) here
  148.  
  149. //        BinaryTree node = (BinaryTree) root.getLeft();
  150. //        node.setLeft(tree);
  151. //        if (isEmpty()) {
  152. //            throw new BinaryTreeAccessError("a");
  153. //        }
  154.         if (tree.getValue().compareTo(getValue()) > 0) {
  155.             throw new BinaryTreeAccessError("Cannot set left subtree as its root value is greater than the main root.");
  156.         }
  157.         root.setLeft(tree);
  158.     }
  159.  
  160.  
  161.     /**
  162.      * Get the right subtree of this tree.
  163.      *
  164.      * @return this tree's right subtree.
  165.      */
  166.     public BTree<T> getRight() throws BinaryTreeAccessError {
  167.         // placeholder return value below - replace with implementation of getRight()
  168.         if (isEmpty()) {
  169.             throw new BinaryTreeAccessError("Cannot get right subtree. This is empty.");
  170.         }
  171.         return root.getRight();
  172.     }
  173.  
  174.     /**
  175.      * Change the right subtree of this tree.
  176.      *
  177.      * @param tree the new right subtree.
  178.      */
  179.     public void setRight(BTree<T> tree) throws BinaryTreeAccessError {
  180.         // implement setRight(BTree<T> tree) here
  181.         if (tree.getValue().compareTo(getValue()) < 0) {
  182.             throw new BinaryTreeAccessError("Cannot set right subtree as its root value is less than the main root.");
  183.         }
  184.         root.setRight(tree);
  185.     }
  186.  
  187.     /**
  188.      * Check if the tree contains a given value.
  189.      *
  190.      * @param value the value to be checked.
  191.      * @return true iff the value is in the tree.
  192.      */
  193.     public boolean contains(T value) throws BinaryTreeAccessError {
  194.         // placeholder return value below - replace with implementation of contains(T value)
  195.  
  196.  
  197.         return false;
  198.     }
  199.  
  200.  
  201.     /**
  202.      * Traverse the tree, producing a list of all the values contained in the tree.
  203.      *
  204.      * @return a list of all the values in the tree.
  205.      */
  206.     public List<T> traverse() throws BinaryTreeAccessError {
  207.         // placeholder return value below - replace with implementation of traverse()
  208.         List<T> traversal = new ArrayList<T>();
  209.         TreeNode<T> node = root;
  210.         if (node.getValue() != null) {
  211.  
  212.             T leftCHild = getLeft().getValue();
  213.             traversal.add((T) leftCHild);
  214.  
  215.             T parent = node.getValue();
  216.             traversal.add(parent);
  217.  
  218.             T rightCHild = node.getRight().getValue();
  219.             traversal.add(rightCHild);
  220.             System.out.println(traversal);
  221. //            node.setValue(leftCHild);
  222.             node.setValue(rightCHild);
  223.         }
  224.  
  225.         return traversal;
  226.  
  227.     }
  228.  
  229.  
  230.     public void inOrder(TreeNode<T> node, List<T> list) throws BinaryTreeAccessError {
  231.         if (node != null) {
  232.             inOrder((TreeNode<T>) node.getLeft().getValue(), list);
  233.             list.add(node.getValue());
  234.             inOrder((TreeNode<T>) node.getRight().getValue(), list);
  235.         }
  236.     }
  237.  
  238.  
  239. //    public List<T> traverseInOrder(T node) throws BinaryTreeAccessError {
  240. //        List<T> traversal = new ArrayList<T>();
  241. //        if (node != null) {
  242. //            traverseInOrder((TreeNode) node.getLeft(.getValue());
  243. //            traverseInOrder((TreeNode) node.getRight().getValue());
  244. //            traversal.add((T) node);
  245. //        }
  246. //        return traversal;
  247. //    }
  248.  
  249.     public static void main(String[] args) throws BinaryTreeAccessError {
  250.         BinaryTree b = new BinaryTree();
  251.         BinaryTree left = new BinaryTree();
  252. //        left.insert(77);
  253. //        left.insert(99);
  254.  
  255.  
  256.         b.insert(5);
  257.         b.insert(4);
  258.         b.insert(6);
  259.         b.insert(2);
  260.  
  261.         System.out.println("b Tree " + b);
  262.         System.out.println();
  263.         System.out.println(b.contains(877));
  264.  
  265.  
  266. //        b.insert(66);
  267. //        b.insert(78);
  268. //        b.insert(16);
  269. //        b.getValue()
  270.         //
  271.         //   b.setLeft(left);
  272.         // b.setValue(5);
  273.         //  b.getRight();
  274.         // b.setLeft(left);
  275.         // b.setRight(left);
  276.  
  277.  
  278.         //    System.out.println(b);
  279.         // System.out.println("LEft " + b.getLeft());
  280.         System.out.println();
  281.         //  System.out.println("Tree NEW left " + left);
  282.         System.out.println();
  283.         System.out.println("b Tree " + b);
  284.         System.out.println();
  285.  
  286.         b.traverse();
  287.         //    System.out.println("right TRee " + b.getRight());
  288. //        System.out.println(b.contains(1));
  289.     }
  290.  
  291. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top