/** * An implementation of the BinaryTree interface by means of a linked structure. */ public class LinkedBinaryTree implements BinaryTree { protected Position root; // reference to the root protected int size; // number of nodes /** Creates an empty binary tree. */ public LinkedBinaryTree() { root = null; // start with an empty tree size = 0; } // BinaryTree interface methods /** Returns the number of nodes in the tree. */ public int size() { return size; } /** Returns whether the tree is empty. */ public boolean isEmpty() { return (size==0); } /** Returns whether a node is internal. */ public boolean isInternal(Position v) throws InvalidPositionException { checkPosition(v); // auxiliary method return (hasLeft(v) || hasRight(v)); } /** Returns whether a node is external. */ public boolean isExternal(Position v) throws InvalidPositionException { return !isInternal(v); } /** Returns whether a node is the root. */ public boolean isRoot(Position v) throws InvalidPositionException { checkPosition(v); return (v == root()); } /** Returns whether a node has a left child. */ public boolean hasLeft(Position v) throws InvalidPositionException { BTPosition vv = checkPosition(v); return (vv.getLeft() != null); } /** Returns whether a node has a right child. */ public boolean hasRight(Position v) throws InvalidPositionException { BTPosition vv = checkPosition(v); return (vv.getRight() != null); }