0

二分木検索をコーディングしています。Duplicate Exception をスローしようとすると、エラーが発生します。この理由がわかりません。私のソース リンクは次のとおりです。 http://pages.cs.wisc.edu/~vernon/cs367/notes/9.BST.html

ソース：

class BinaryTreenode {
// *** fields ***
private Comparable key;
private BinaryTreenode left, right;

// *** methods ***

// constructor
public BinaryTreenode(Comparable k, BinaryTreenode l, BinaryTreenode r) {
   key = k;
   left = l;
   right = r;
}

 // access to fields
public Comparable getKey() {return key;}
public BinaryTreenode getLeft() {return left;}
public BinaryTreenode getRight() {return right;}

// change fields
public void setKey(Comparable k) {key = k;}
public void setLeft(BinaryTreenode l) {left = l;}
public void setRight(BinaryTreenode r) {right = r;}
 }

class BST {
// *** fields ***
private BinaryTreenode root; // ptr to the root of the BST

// *** methods ***
public BST() { root = null; } // constructor
public void insert(Comparable key) throws DuplicateException {...}
  // add key to this BST; error if it is already there
public void delete(Comparable key) {...}
  // remove the node containing key from this BST if it is there;
  // otherwise, do nothing
public boolean lookup(Comparable key) {...}
 // if key is in this BST, return true; otherwise, return false
public void print(PrintWriter p) {...}
 // print the values in this BST in sorted order (to p)
}

私の挿入メソッドで、エラー This is my code: が表示されます。

public class BinaryTreeNode 
{
// ***fields***
private Comparable key;
private BinaryTreeNode left;
private BinaryTreeNode right;

// ***methods***
// constructor
public BinaryTreeNode(Comparable k, BinaryTreeNode l, BinaryTreeNode r)
{
    key = k;
    left = l;
    right = r;
}

public Comparable getKey()
{
    return key;
}

public BinaryTreeNode getLeft()
{
    return left;
}

public BinaryTreeNode getRight()
{
    return right;
}

public void setKey(Comparable k)
{
    key = k;
}

public void setLeft(BinaryTreeNode l)
{
    left = l;
}

public void setRight(BinaryTreeNode r)
{
    right = r;
}

}

class BST
{
// ***fields***
private BinaryTreeNode root;

// ***methods**
// constructor
public BST()
{
    root = null;
}

public void insert(Comparable key) throws DuplicateException
{
    if (root.getKey() != null) throw new DuplicateException;
}
}
4

1 に答える 1

0

すべてのノードに一意のキーを持たせたい場合は、ルートだけでなくツリー全体をチェックする必要があります。したがって、これはチェックするより良い方法です：

public void insert(Comparable key) throws DuplicateException
{
    // Make sure key is not already in tree
    if(this.lookup(key))
        throw new DuplicateException;
    // Find correct position in tree to insert the new node

    // Insert the new node

}

の現在のコードではclass BST、rootは常にnullです。したがって、 を呼び出すとすぐに例外が発生するはずですroot.getKey()。

于 2013-09-12T07:58:51.640 に答える