1

我和我的搭档正在为数据结构和算法课程实施二叉搜索树。我们的add方法遇到问题。此代码如下所示：

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。如果有人对为什么会这样有任何建议或见解，我们将不胜感激。

4

2 回答 2

2

在addItem方法内部，thisRoot只是一个局部变量（绑定到方法的第二个参数）。重置它不会改变任何东西，除了在方法内部。您必须将new BinaryNode<Type>(item)构造的 分配给现有节点的左指针或右指针。

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

于 2013-06-22T18:59:53.703 回答
0

这是一种相对简单的方法

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

   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;
于 2019-03-28T18:51:53.100 回答