Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package binaryTree;
- import java.util.ArrayList;
- import java.util.List;
- /**
- * A partial implementation of sorted binary trees.
- * <p>
- * The three constructors (construct an empty tree ({@link #BinaryTree()}, or a tree with a root value but no subtrees
- * ({@link #BinaryTree(Comparable)}, or a tree with a root value and left and right subtrees
- * ({@link #BinaryTree(Comparable, BinaryTree, BinaryTree)}), as well as the {@link #isEmpty()} method are already implemented.
- * <p>
- * For the remaining methods specified in the {@link BTree} interface ({@link #insert(Comparable)}, {@link #getValue()},
- * {@link #setValue(Comparable)}, {@link #getLeft()}, {@link #setLeft(BTree)}, {@link #getRight()}, {@link #setRight(BTree)},
- * {@link #contains(Comparable)}, and {@link #traverse()}) only a "stub" is provided. For the logbook exercise you
- * should implement these methods.
- * <p>
- * Don't forget to test your implementation!
- *
- * @param <T> the type of value stored in the tree.
- * @author Hugh Osborne.
- * @version December 2019.
- */
- public class BinaryTree<T extends Comparable<? super T>> implements BTree<T> {
- /**
- * The root node of this tree.
- */
- private TreeNode<T> root;
- /**
- * Construct an empty tree.
- */
- public BinaryTree() {
- root = null;
- }
- /**
- * Construct a singleton tree.
- * A singleton tree contains a value in the root, but the left and right subtrees are
- * empty.
- *
- * @param value the value to be stored in the tree.
- */
- public BinaryTree(T value) {
- root = new TreeNode<>(value);
- }
- /**
- * Construct a tree with a root value, and left and right subtrees.
- *
- * @param value the value to be stored in the root of the tree.
- * @param left the tree's left subtree.
- * @param right the tree's right subtree.
- */
- public BinaryTree(T value, BinaryTree<T> left, BinaryTree<T> right) {
- root = new TreeNode<>(value, left, right);
- }
- /**
- * Check if the tree is empty.
- *
- * @return true iff the tree is empty.
- */
- public boolean isEmpty() {
- return root == null;
- }
- /**
- * Insert a new value in the binary tree at a position determined by the current contents
- * of the tree, and by the ordering on the type T.
- *
- * @param value the value to be inserted into the tree.
- */
- public void insert(T value) throws BinaryTreeAccessError {
- // implement insert(T value) here
- if (isEmpty()) {
- root = new TreeNode<>(value);
- } else if (value.compareTo(getValue()) < 0) {
- getLeft().insert(value);
- } else {
- getRight().insert(value);
- }
- // System.out.println(root);
- }
- @Override
- public String toString() {
- return "BinaryTree{" +
- "root=" + root +
- '}';
- }
- /**
- * Get the value stored at the root of the tree.
- *
- * @return the value stored at the root of the tree.
- */
- public T getValue() throws BinaryTreeAccessError {
- // Note: it might make sense to define getValue() to throw a (custom) exception if an attempt
- // is made to access a value from an empty tree.
- // However, since a tree is empty iff its root node is null, it is also acceptable to rely
- // on Java's NullPointerException.
- // This comment also applies to the other get and set methods defined in this interface.
- // placeholder return value below - replace with implementation of getValue()
- if (isEmpty()) {
- throw new BinaryTreeAccessError("Cannot access root. Empty tree");
- }
- return root.getValue();
- }
- /**
- * Change the value stored at the root of the tree.
- *
- * @param value the new value to be stored at the root of the tree.
- */
- public void setValue(T value) throws BinaryTreeAccessError {
- // implement setValue(T value) here
- if (isEmpty()) {
- throw new BinaryTreeAccessError("BinaryTree doesn't exists. Cannot access root");
- }
- root.setValue(value);
- }
- /**
- * Get the left subtree of this tree.
- *
- * @return This tree's left subtree.
- */
- public BTree<T> getLeft() throws BinaryTreeAccessError {
- if (isEmpty()) {
- throw new BinaryTreeAccessError("Left tree is empty");
- }
- return root.getLeft();
- }
- /**
- * Change the left subtree of this tree.
- *
- * @param tree the new left subtree.
- */
- public void setLeft(BTree<T> tree) throws BinaryTreeAccessError {
- // implement setLeft(BTree<T> tree) here
- // BinaryTree node = (BinaryTree) root.getLeft();
- // node.setLeft(tree);
- // if (isEmpty()) {
- // throw new BinaryTreeAccessError("a");
- // }
- if (tree.getValue().compareTo(getValue()) > 0) {
- throw new BinaryTreeAccessError("Cannot set left subtree as its root value is greater than the main root.");
- }
- root.setLeft(tree);
- }
- /**
- * Get the right subtree of this tree.
- *
- * @return this tree's right subtree.
- */
- public BTree<T> getRight() throws BinaryTreeAccessError {
- // placeholder return value below - replace with implementation of getRight()
- if (isEmpty()) {
- throw new BinaryTreeAccessError("Cannot get right subtree. This is empty.");
- }
- return root.getRight();
- }
- /**
- * Change the right subtree of this tree.
- *
- * @param tree the new right subtree.
- */
- public void setRight(BTree<T> tree) throws BinaryTreeAccessError {
- // implement setRight(BTree<T> tree) here
- if (tree.getValue().compareTo(getValue()) < 0) {
- throw new BinaryTreeAccessError("Cannot set right subtree as its root value is less than the main root.");
- }
- root.setRight(tree);
- }
- /**
- * Check if the tree contains a given value.
- *
- * @param value the value to be checked.
- * @return true iff the value is in the tree.
- */
- public boolean contains(T value) throws BinaryTreeAccessError {
- // placeholder return value below - replace with implementation of contains(T value)
- return false;
- }
- /**
- * Traverse the tree, producing a list of all the values contained in the tree.
- *
- * @return a list of all the values in the tree.
- */
- public List<T> traverse() throws BinaryTreeAccessError {
- // placeholder return value below - replace with implementation of traverse()
- List<T> traversal = new ArrayList<T>();
- TreeNode<T> node = root;
- if (node.getValue() != null) {
- T leftCHild = getLeft().getValue();
- traversal.add((T) leftCHild);
- T parent = node.getValue();
- traversal.add(parent);
- T rightCHild = node.getRight().getValue();
- traversal.add(rightCHild);
- System.out.println(traversal);
- // node.setValue(leftCHild);
- node.setValue(rightCHild);
- }
- return traversal;
- }
- public void inOrder(TreeNode<T> node, List<T> list) throws BinaryTreeAccessError {
- if (node != null) {
- inOrder((TreeNode<T>) node.getLeft().getValue(), list);
- list.add(node.getValue());
- inOrder((TreeNode<T>) node.getRight().getValue(), list);
- }
- }
- // public List<T> traverseInOrder(T node) throws BinaryTreeAccessError {
- // List<T> traversal = new ArrayList<T>();
- // if (node != null) {
- // traverseInOrder((TreeNode) node.getLeft(.getValue());
- // traverseInOrder((TreeNode) node.getRight().getValue());
- // traversal.add((T) node);
- // }
- // return traversal;
- // }
- public static void main(String[] args) throws BinaryTreeAccessError {
- BinaryTree b = new BinaryTree();
- BinaryTree left = new BinaryTree();
- // left.insert(77);
- // left.insert(99);
- b.insert(5);
- b.insert(4);
- b.insert(6);
- b.insert(2);
- System.out.println("b Tree " + b);
- System.out.println();
- System.out.println(b.contains(877));
- // b.insert(66);
- // b.insert(78);
- // b.insert(16);
- // b.getValue()
- //
- // b.setLeft(left);
- // b.setValue(5);
- // b.getRight();
- // b.setLeft(left);
- // b.setRight(left);
- // System.out.println(b);
- // System.out.println("LEft " + b.getLeft());
- System.out.println();
- // System.out.println("Tree NEW left " + left);
- System.out.println();
- System.out.println("b Tree " + b);
- System.out.println();
- b.traverse();
- // System.out.println("right TRee " + b.getRight());
- // System.out.println(b.contains(1));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement