CS计算机代考程序代写 Java package edu.psu.ist311.bst;

程序代写 CS代考 / Java代写代考

package edu.psu.ist311.bst;

import java.util.Comparator;

/**
* A basic binary search tree class (BST).
*

* Conceptually, this object, binary-tree(T) — pronounced: “binary tree of T”,
* is recursively defined as a triple containing:
*

    *

  1. data : T (i.e.: data ‘of type’ T)

    2. *

  2. left, right : binary-tree(T)

    3. *

*

* initially: this.left = empty_tree and this.right = empty_tree and let
* data-set(tr) denote the set of all data elements stored in the tree tr and
* its subtrees.
*

* constraints: this tree is conformal with binary search tree
* ordering property. Assume we have a predicate, is-ordered(e, tr), which
* produces {@code true} if and only if the element e : T is properly ordered
* w.r.t. the binary-tree(T), tr, passed; {@code false} otherwise.
*
* @param The type of the elements stored inside the tree
*/
public interface ISearchTree {

T data();

/**
* Returns the {@link Comparator} used to impose a total ordering on the
* type of this tree’s internal data (i.e.: type {@code T})
*

* Note: it is up to the client to ensure their comparator is a total
* ordering over domain {@code T}.
*/
Comparator orderer();

ISearchTree left();

ISearchTree right();

/**
* Returns the root of {@code this} search tree with {@code e} added to the
* appropriate subtree.
*

* note: when implementing this recursive version of add,
* do not use the “search” method from the slides.
*
* 

     *     requires e not-in data-set(this)
     *     ensures if old(this) = empty_tree then
     *                      this = (e, empty-tree, empty-tree)
     *                    else [element is added to the tree] and
     *                      is-ordered(e, this) -- i.e.: the output tree
     *                              is ordered w.r.t. element e

* @throws IllegalArgumentException if a duplicate key is added.
*/
ISearchTree add(T e);

/**
* @see #add(T) for the contract. Same exceptions apply.
*/
ISearchTree addIter(T e);

/**
* Returns {@code true} if key {@code e} is contained in this search tree;
* {@code false} otherwise.
* 

ensures true iff e is-in data-set(this); false otherwise

*/
boolean contains(T e);

void setLeft(ISearchTree l);

void setRight(ISearchTree r);

// traversals

/**
* Returns a string containing the preorder/enterorder traversal of this
* search tree.
*/
String dumpPreorder();

/**
* Returns a string containing the postorder/exitorder traversal of this
* search tree.
*/
String dumpPostorder();

/**
* Returns a string containing a pre-order traversal of this tree. Hint,
* this should just call and return the result of {@link #dumpPreorder()}.
* 

     * ensures toString = [the string containing the preorder traversal
     *         of this tree].

*/
String toString();

}

Related Posts