Binary Tree Search DuplicateException error

Question

Я кодирую двоичный поиск дерева. Я получаю сообщение об ошибке при попытке выбрасывать 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) 
} 

В моем методе вставки, я получаю ошибку Это мой код:

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; 
} 
} 

Answer 1

Если вы хотите, чтобы каждый узел, чтобы иметь уникальный ключ, вам нужно будет проверить все дерево, а не только корень. Так что это будет лучший способ проверить:

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().