001package components.binarytree;
002
003/**
004 * {@code BinaryTreeKernel} enhanced with secondary methods.
005 *
006 * @param <T>
007 *            type of {@code BinaryTree} labels
008 */
009public interface BinaryTree<T> extends BinaryTreeKernel<T> {
010
011    /**
012     * Reports the root of {@code this}.
013     *
014     * @return the root entry of {@code this}
015     * @aliases reference returned by {@code root}
016     * @requires this /= empty_tree
017     * @ensures <pre>
018     * there exists left, right: binary tree of T
019     *     (this = compose(root, left, right))
020     * </pre>
021     */
022    T root();
023
024    /**
025     * Replaces the root of {@code this} with {@code x}, and returns the old
026     * root.
027     *
028     * @param x
029     *            the new root
030     * @return the old root
031     * @aliases reference {@code x}
032     * @updates this
033     * @requires this /= empty_tree
034     * @ensures <pre>
035     * there exists left, right: binary tree of T
036     *     (#this = compose(replaceRoot, left, right)  and
037     *      this = compose(x, left, right))
038     * </pre>
039     */
040    T replaceRoot(T x);
041
042    /**
043     * Reports the height of {@code this}.
044     *
045     * @return the height
046     * @ensures height = ht(this)
047     */
048    int height();
049
050    /**
051     * Assembles in {@code this} a tree that has the same in-order traversal as
052     * a tree with root label {@code root} and subtrees {@code left} and
053     * {@code right}; the declaration notwithstanding, the <i>dynamic</i> type
054     * of {@code left} and {@code right} must be the same as the <i>dynamic</i>
055     * type of {@code this}.
056     *
057     * @param root
058     *            the root label
059     * @param left
060     *            the left subtree
061     * @param right
062     *            the right subtree
063     * @aliases reference {@code root}
064     * @updates this
065     * @clears left, right
066     * @ensures IN_ORDER(this) = IN_ORDER(compose(root, #left, #right))
067     */
068    void inOrderAssemble(T root, BinaryTree<T> left, BinaryTree<T> right);
069
070}