0

我在徘徊我做错了什么，有人可以帮助我吗？我正在尝试使用 DDL（双向链表）数据结构制作通用 BST。问题是我的 ADT 已初始化，因为我的isEmpty方法有效，但我的public addNewElementwhich sueprivate insert不起作用。欢迎任何帮助和建议。

界面：

public interface SortedSetBST <type> extends Iterable<type>{
            void addNewElement(Comparable<type> newElement);

    }

ADT：

package adt;

import java.util.Iterator;
import java.util.Iterator;

import interfaces.SortedSetBST;
import exceptions.*;

public class BinarySearchTree <type> implements SortedSetBST<type> {
    BinaryNode <type> root;
    int size;

    @Override
    public void addNewElement(Comparable  <type>  newElement) {
         insert(newElement, root);  
    }

protected BinaryNode  <type> insert( Comparable <type> x, BinaryNode <type>  t ) {
   if( t == null )
       t = new BinaryNode( x );
   else if( x.compareTo( t.element ) < 0 )
       t.left = insert( x, t.left );
   else if( x.compareTo( t.element ) > 0 )
       t.right = insert( x, t.right );
   else
       throw new DuplicateItemException( x.toString( ) );  // Duplicate
   return t;
}
class BinaryNode<type> {
    type element;      // The data in the node
    BinaryNode<type> left;         // Left child
    BinaryNode<type> right;        // Right child

    // Constructors
    BinaryNode( type theElement ) {
        element = theElement;
        left = right = null;
    }   
}

类应用

public class App {
    public static void main(String [] args){
        System.out.println("   Main:");
        BinarySearchTree <String> db = new BinarySearchTree<String>();

        if(db.isEmpty() == true){
            System.out.println(".db empty!");
        }
        db.addNewElement("unu");
        db.addNewElement("doi");
        db.addNewElement("trei");
        System.out.println(db.getSize());
    }
}

输出：

   Main:
.db empty!
0
4

1 回答 1

1

这很清楚。

在“插入”中，您正在检查 t 是否为空。如果是这种情况，您可以使用 BinaryNode 的实例初始化参数t ，并认为在第一次传入“null”时也会更新 root 。但是“null”在 Java 中是“null”，而不是您可能认为的 C 样式地址！

然后您返回此参数，但返回值在“addNewElement”中丢失。

如何正确执行此操作：

if( t == null ) {
   if (root == null){
      root = new BinaryNode(x);
      return root;
   } else {
      t = new BinaryNode( x );
   }
}
于 2012-10-30T21:19:15.730 回答