Задание 03 курса ADT and Algorithm
Question 1: Binary Tree Node
10 MARKS

>The goal of this question is to implement binary tree nodes which will then be used for implementing a generic binary tree which, in turn, will be used to implement heaps and binary search trees. As you know, heaps and binary search trees are defined for objects with associated keys that are comparable to each other. For these keys, we will use comparable objects. For testing purposes, keys will be instances of the class MyInteger.

Complete the following class for representing nodes in a binary tree and add this class to your project.

/==============================================================================
public class BinaryTreeNode
{
    // Instance variables (Note: they are all "private")
    private Comparable key           // The key at this node
    private Object element;          // The data at this node
    private BinaryTreeNode left;     // Left child
    private BinaryTreeNode right;    // Right child
    private BinaryTreeNode p;        // The Parent

    // Constructors
    BinaryTreeNode( Comparable theKey, Object theElement, BinaryTreeNode lt,
                    BinaryTreeNode rt, BinaryTreeNode pt  )
    {
        key      = theKey;
        element  = theElement;
        left     = lt;
        right    = rt;
        p        = pt;
    }

    BinaryTreeNode( Comparable theKey, Object theElement)
    {
        key      = theKey;
        element  = theElement;
        left     = null;
        right    = null;
        p        = null;
    }

    // return the key attached to this node
    public Comparable getKey()
    {
    ...
    }

    // set the key attached to this node to be Comparable k
    public void setKey(Comparable k)
    {
    ...
    }

    // return the element attached to this node
    public Object getElement()
    {
    ...
    }

    // set the element attached to this node to be Object o
    public void setElement(Object o)
    {
    ...
    }

    // return left child
    public BinaryTreeNode leftChild()
    {
    ...
    }

    // set left child to be node n
    public void setLeftChild(BinaryTreeNode n)
    {
    ...
    }

    // return right child
    public BinaryTreeNode rightChild()
    {
    ...
    }

    // set right child to be node n
    public void setRightChild(BinaryTreeNode n)
    {
    ...
    }

    // return parent
    public BinaryTreeNode parent()
    {
    ...
    }

    // set parent to be node n
    public void setParent(BinaryTreeNode n)
    {
    ...
    }

}
/==============================================================================

Question 2: Binary Tree

50 MARKS

The goal of this question is to implement generic binary trees consisting of BinaryTreeNode instances.

a) Add an interface “BinaryTree” for generic binary trees which support the following methods:

// make the tree empty
    void makeEmpty( );

    // create a root node with key "k" and element "el"
    void makeRoot (Comparable k, Object el);

    // return the root node
    BinaryTreeNode root();

    // return left child of node "node"
    public BinaryTreeNode leftChild(BinaryTreeNode node);

    // set left child of node "node" to "child"
    public void setLeftChild(BinaryTreeNode node, BinaryTreeNode child);

    // return right child of node "node"
    public BinaryTreeNode rightChild(BinaryTreeNode node)

    // set right child of node "node" to "child"
    public void setRightChild(BinaryTreeNode node, BinaryTreeNode child);

    // return parent of node "node"
    public BinaryTreeNode parent(BinaryTreeNode node)

    // set parent of node "node" to "pt"
    public void setparent(BinaryTreeNode node, BinaryTreeNode pt);

    // return the key attached to node "node"
    public Comparable getKey(BinaryTreeNode node);

    // set the key attached to node "node" to be key "k"
    public void setKey(BinaryTreeNode node, Comparable k);

    // return the element attached to node "node"
    public Object getElement(BinaryTreeNode node);

    // set the element attached to node "node" to be Object "o"
    public void setElement(BinaryTreeNode node, Object o);

    // add a left child node (with key "k" and element "el") to a tree node "theNode"
    void addLeftChild (BinaryTreeNode theNode, Comparable k, Object el);

    // add a right child node (with key "k" and element "el") to a tree node "theNode"
    void addRightChild (BinaryTreeNode theNode, Comparable k, Object el);

    // remove the left child of node "theNode"
    void removeLeftChild (BinaryTreeNode theNode);

    // remove the right child of node "theNode"
    void removeRightChild (BinaryTreeNode theNode);

    // return a string representation of the tree as an inorder traversal
    // with each node, n, indented by height(n) blanks.
    // If the tree is empty, return a string "*** tree is empty ***".
    String toString();

    // return a string representation of the tree as an inorder traversal
    // with each node, n, indented by height(n) blanks. In addition, node "currentPosition"
    // is marked with an asterix ("*").
    // (No asterix if currentPosition =  null or currentPosition is not in the tree.)
    // If the tree is empty, return a string "*** tree is empty ***".
    String toString(BinaryTreeNode currentPosition);

Make sure that you also add the necessary exceptions (Add “throws” statements to the above and create the necessary exception classes). Think about the possible error conditions.

b) Add a class “MyBinaryTree” which implements the interface “BinaryTree”.

c) Add a test program which tests the class “MyBinaryTree”.
The user’s menu should provide at least the following operations for a BinaryTree “T” and a current position BinaryTreeNode “currentPosition”:
- “empty the tree”
- “create a root” (create a root for an empty tree; with given key and element values)
- “set current position to root” (move currentPosition to the root)
- “move left” (move currentPosition to the left child of the current location)
- “move right” (move currentPosition to the right child of the current location)
- “move to parent” (move currentPosition to the parent of the current location)
- “add left child” (add a left child at the current position; with given key and element values)
- “add right child” (add a right child to the current position; with given key and element values)
- “remove left child” (remove the left child at the current position)
- “remove right child” (remove the right child at the current position)

After each operation, the updated tree (with “current position” asterix) should be displayed.

Question 3: Heap

40 MARKS

The goal of this question is to implement heaps as a subclass of binary trees.

a) Add an interface “Heap” for generic heaps which support the following methods:

   // make the heap empty
    void makeEmpty( );

    // insert an element "el" with key "k"
    void insert (Comparable k, Object el);

    // return the key of the smallest element (but don't remove it yet)
    Comparable getMinKey ();

    // return the smallest element (but don't remove it yet)
    Object getMinElement ();

    // remove the smallest element (and it's key) from the heap
    void removeMin ();

Make sure that you also add the necessary exceptions (Add “throws” statements to the above and create the necessary exception classes). Think about the possible error conditions.

b) Add a class “MyHeap” which is a subclass of “MyBinaryTree” and implements the interface “Heap”.

c) Add a test program which tests the class “MyHeap”.
The user’s menu should provide at least the following operations:
- “empty the heap”
- “insert (key and element)”
- “getMin (key and element)”
- “removeMin”

After each operation, the updated heap (in tree representation) should be displayed.

BONUS QUESTION: Binary Search Trees

30 MARKS

The goal of this question is to implement binary search trees as a subclass of binary trees.

a) Add an interface “Dictionary” for generic dictionaries which support the following methods:

    // empty the dictionary
    void makeEmpty( );

    // insert an element "el" with key "k"
    void insert (Comparable k, Object el);

    // remove an element with key "k"
    void remove (Comparable k);

    // find (and return) an element with key "k"
    Object find (Comparable k);

Make sure that you also add the necessary exceptions (Add “throws” statements to the above and create the necessary exception classes). Think about the possible error conditions.

b) Add a class “MyBinarySearchTree” which is a subclass of “MyBinaryTree” and implements the interface “Dictionary”.

c) Add a test program which tests the class “MyBinarySearchTree”.
The user’s menu should provide at least the following operations:
- “make empty”
- “insert (key and element)”
- “remove (key)”
- “find (key)”

After each operation, the updated search tree should be displayed.

BONUS QUESTION: AVL Trees

20 MARKS

The goal of this question is to implement AVL trees as a subclass of binary search trees.

a) Add a class “MyAVLtree” which is a subclass of “MyBinarySearchTree” and re-implements “insert” and “remove” to follow the AVL tree method presented in class such that “insert”, “remove” and “find” all run in time O(log n).

b) Using your test program for the class “MyBinarySearchTree”, show that your AVL tree implementation works correctly. Hand in a printout that demonstartes at least all four cases of rotation for “insert” and “remove”.

interface Comparable

/**
 * Protocol for Comparable objects.
 * @author Mark Allen Weiss
 */
public interface Comparable
{
    /**
     * Compare this object with rhs.
     * @param Rhs the second Comparable.
     * @return 0 if two objects are equal;
     *     less than zero if this object is smaller;
     *     greater than zero if this object is larger.
     */
    int     compares( Comparable rhs );

    /**
     * Compare this object with rhs.
     * @param Rhs the second Comparable.
     * @return true if this object is smaller;
     *     false otherwise.
     */
    boolean lessThan( Comparable rhs );
}

class MyInteger

/**
 * Wrapper class for use with generic data structures.
 * Mimics Integer.
 * @author Mark Allen Weiss
 */
public final class MyInteger implements Comparable
{
    /**
     * Construct the MyInteger object with initial value 0.
     */
    public MyInteger( )
    {
        this( 0 );
    }

    /**
     * Construct the MyInteger object.
     * @param x the initial value.
     */
    public MyInteger( int x )
    {
        value = x;
    }

    /**
     * Gets the stored int value.
     * @return the stored value.
     */
    public int intValue( )
    {
        return value;
    }

    /**
     * Implements the toString method.
     * @return the String representation.
     */
    public String toString( )
    {
        return Integer.toString( value );
    }

    /**
     * Implements the compares method.
     * @param rhs the other MyInteger object.
     * @return 0 if two objects are equal;
     *     less than zero if this object is smaller;
     *     greater than zero if this object is larger.
     * @exception ClassCastException if rhs is not
     *     a MyInteger.
     */
    public int compares( Comparable rhs )
    {
        return value < ((MyInteger)rhs).value ? -1 :
               value == ((MyInteger)rhs).value ? 0 : 1;
    }

    /**
     * Implements the lessThan method.
     * @param rhs the second MyInteger.
     * @return true if this object is smaller;
     *     false otherwise.
     * @exception ClassCastException if rhs is not
     *     a MyInteger.
     */
    public boolean lessThan( Comparable rhs )
    {
        return value < ((MyInteger)rhs).value;
    }

    /**
     * Implements the equals method.
     * @param rhs the second MyInteger.
     * @return true if the objects are equal, false otherwise.
     * @exception ClassCastException if rhs is not
     *     a MyInteger.
     */
    public boolean equals( Object rhs )
    {
        return rhs != null && value == ((MyInteger)rhs).value;
    }

    private int value;
}

Решение:

    29 Май 2009 by freetonik

This website uses IntenseDebate comments, but they are not currently loaded because either your browser doesn't support JavaScript, or they didn't load fast enough.

1 Response to 03: Binary Tree, Heap, AVL, Binary Search

Avatar

bojlahg

Март 9th, 2010 at 17:48

avl деревья ваще сила, а что вам про red black деревья не рассказывали?

Comment Form


Warning: Parameter 1 to id_generic_callback() expected to be a reference, value given in /home/users/f/freetonik/domains/css.freetonik.com/wp-content/plugins/intensedebate/intensedebate.php on line 911

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 8622679 bytes) in /home/users/f/freetonik/domains/css.freetonik.com/wp-includes/functions.php on line 959