1

だから私は、私が取り組んでいるこの現在の問題に困惑しました。基本的に、配列ベースのバイナリ検索ツリーに要素を追加する必要があります。私のテキストによると、compareTo メソッドに似ています。どの方向に向かうべきかさえわかりません.OOPに関しては完全な初心者なので、助けていただければ幸いです。

package lab9;

public class BinarySearchTreeArray<E> {

    Entry<E> [] tree;
    Entry<E> root;
    int size;

    public BinarySearchTreeArray()
    {
        tree = null;
        size = 0;
    }

    public int size()
    {
        return size;
    }

    public boolean contains(Object obj)
    {
        Entry<E> temp = root;
        int comp;

        if (obj == null)
            throw new NullPointerException();

        while (obj != null)
        {
            comp = ((Comparable)obj).compareTo (temp.element);
            if (comp == 0)
                return true;
            else if (comp < 0)
                temp = temp.left;
            else
                temp = temp.right;
        }//while
        return false;
    }//contains method

    /*
     * From the text:
     * The definition of the add (E element) method is only a little more
     * complicated than the definition of contains (Object obj).  Basically,
     * the add method starts at the root and branches down the tree 
     * searching for the element; if the search fails, the element is
     * inserted as a leaf.
     */

    public void add(E e)
    {
        Entry<E> node = new Entry<E>(e);

        if (tree[parent] == null)
        {
             tree[0] = node;
             size++;
        }
        else
        {
            tree[1] = node;
            size++;
        }
    }//add method

/****************************************************************/
    protected static class Entry<E>
    {
        private E element;
        private Entry<E> parent, left, right;

        public Entry(E e){this.element = element; left = right = null;}
        public Entry<E> getLeft(){return left;}
        public Entry<E> getRight(){return right;}
    }
/****************************************************************/

    public static void main(String[] args) {

        BinarySearchTreeArray<String> bsta1 = new BinarySearchTreeArray<String>();
        BinarySearchTreeArray<Integer> bsta2 = new BinarySearchTreeArray<Integer>();

        bsta1.add("dog");
        bsta1.add("tutle");
        bsta1.add("cat");
        bsta1.add("ferrit");
        bsta1.add("shark");
        bsta1.add("whale");
        bsta1.add("porpoise");

        bsta2.add(3);
        bsta2.add(18);
        bsta2.add(4);
        bsta2.add(99);
        bsta2.add(50);
        bsta2.add(23);
        bsta2.add(5);
        bsta2.add(101);
        bsta2.add(77);
        bsta2.add(87);
    }
}
4

1 に答える 1

3

このadd方法は確かにあなたの方法に似ていますcontains。構造体/オブジェクトで表される典型的なバイナリ ツリーでは、ポインターを使用して左右のサブツリーにアクセスします (temp.left および temp.right の例のように)。しかし、配列にツリーがあるため、その配列にインデックスでアクセスする必要があるため、問題は次のとおりです。左/右のサブツリーに対応するインデックスにアクセスする方法は?

そのために、次の式left = parent * 2とを使用できますright = parent * 2 + 1。add整数の配列として表されるツリーに要素を追加するメソッドの一例を提供します。ここ-1で、Java では値がないか null を表します。

public void add(E e)
{
    Entry<E> node = new Entry<E>(e);
    index = 0;
    int comp;
    boolean not_add = true;
    while(not_add)
    {
      if (tree[index] == null) //if this node is empty
      {
          tree[index] = node;
          size++;
          not_add  = true;
      }
     
      comp = ((Comparable)e).compareTo (tree[index].element);
      
      if(comp == 0) not_add = true; // Same value
      else if (comp < 0) index = index * 2;  // should be insert on the left
      else index = index * 2 + 1; // should be insert on the right
     }
}
于 2012-10-27T16:16:05.953 に答える