package plp.collection; public class STree { /* Because we are programming in a functionnal style, the data may be declared as final. But because they are private, it is not necessary and it would not allow to use only one real constructor. */ private Object data; private STree left; private STree right; public static final STree EMPTY = new STree(); private STree() { data = null; left = null; right = null; } public STree(Object data) { this(EMPTY, data, EMPTY); } public STree(STree left, Object data) { this(left, data, EMPTY); } public STree(Object data, STree right) { this(EMPTY, data, right); } public STree(STree left, Object data, STree right) { this.data = data; if (left == null || right == null) { throw new NullPointerException(); } this.left = left; this.right = right; } public boolean isEmpty() { return this == EMPTY; } private void checkNonEmpty() throws EmptyTreeException { if (isEmpty()) { throw new EmptyTreeException(); } } public STree left() throws EmptyTreeException { checkNonEmpty(); return left; } public STree right() throws EmptyTreeException { checkNonEmpty(); return right; } public Object data() throws EmptyTreeException { checkNonEmpty(); return data; } public boolean isLeaf() { return !isEmpty() && left.isEmpty() && right.isEmpty(); } public boolean hasLeftSubtree() { return !isEmpty() && !left.isEmpty(); } public boolean hasRightSubtree() { return !isEmpty() && !right.isEmpty(); } public int size() { return isEmpty()? 0 : left.size() + right.size() + 1; } public int height() { return isEmpty()? 0 : 1 + Math.max(left.height(), right.height()); } public SList depthFirstSearch() { return isEmpty() ? SList.EMPTY : left.depthFirstSearch().append(new SList(data, right.depthFirstSearch())); } public Object [] depthFirstSearchToArray() { Object [] array = new Object[size()]; depthFirstSearchToArrayAux(array, 0); return array; } private int depthFirstSearchToArrayAux(Object [] array, int index) { if (isEmpty()) { return index; } index = left.depthFirstSearchToArrayAux(array, index); array[index++] = data; return right.depthFirstSearchToArrayAux(array, index); } }