实现二进制搜索树的add方法

Question

我和我的搭档正在为数据结构实现二进制搜索树

public class BinarySearchTree<Type extends Comparable<? super Type>> implements SortedSet<Type>
{


BinaryNode<Type> thisRoot;

/**
 * Constructor for this BinarySearchTree
 */
public BinarySearchTree()
{
    thisRoot = null;
}

/**
 * Adds the specified item to this BinarySearchTree, if it is
 * not already contained in this BinarySearchTree.
 * 
 * @param Type item
 * 
 * @return boolean
 */
public boolean add(Type item) {

    // If the specified item is null, throw an exception.
    if(item == null)
        throw new NullPointerException();

    // Otherwise, add the item.
    return addItem(item, thisRoot);

}

private boolean addItem(Type item, BinaryNode<Type> thisRoot)
{
    // Base case - check if thisRoot is null.  If it is null,
    // we have reached the base case where the item is not contained
    // in this BinarySearchTree.  Insert the item.
    if(thisRoot == null)
    {   
        thisRoot = new BinaryNode<Type>(item);
        return true;
    }

    // Reduction step - recursively call the helper method until the
    // specified item is found or added.

    // If the item is less than the data in thisNode, then go to 
    // the left in this BinarySearchTree.
    if(item.compareTo(thisRoot.getData()) < 0)
        return addItem(item, thisRoot.getLeft());

    // If the item is greater than the data in thisNode, then go
    // to the right in this BinarySearchTree.
    else if (item.compareTo(thisRoot.getData()) > 0)
        return addItem(item, thisRoot.getRight());
    else
        // Item is already contained in this BinarySearchTree.
        return false;

}

在我们的测试案例中，我们没有得到我们预期的结果。我们最初创建了一个空的BinarySearchTree，并调用add方法。从这里，我们将一个整数对象（10）传递给该方法。完成此操作后，应该调用递归addItem方法。thisRoot当前应该引用null（因为我们创建了一个空的BinarySearchTree），因此thisRoot现在应该引用新的BinaryNode对象。但是，在方法调用之后，BST中不包含10。thisRoot仍然指向null。如果有人对原因有任何建议或见解，我们将不胜感激。

Answer 1

这是一种相对简单的方法

此外，如果您看到任何未声明的数据类型，请考虑将其添加到完整代码的某个地方。

   public void addNode (int key, String name) {

    // Create a new Node and initialize it

    Node newNode = new Node(key, name);

    if (root == null) {

        root = newNode;

    } else {

       Node focusNode = root;
        Node parent;

        while (true) {



            parent = focusNode;

            // Check if the new node should go on
            // the left side of the parent node

            if (key < focusNode.key) {

                // Switch focus to the left child

                focusNode = focusNode.leftChild;


                if (focusNode == null) {


                    parent.leftChild = newNode;
                    return; 

                }

            } else {  the right

                focusNode = focusNode.rightChild;



                if (focusNode == null) {



                    parent.rightChild = newNode;
                    return; 

Answer 2

在addItem方法中，thisRoot只是一个局部变量（绑定到该方法的第二个参数）。重置它不会改变任何东西，除了方法内部。您必须分配新的二进制节点

（如果我含糊其辞，那是因为我不想给出答案。）