java - BinarySearchingTree - dll(generic)，不知何故我的项目无法添加到我的 adt 中

Question

我正在徘徊我做错了什么，有人可以帮助我吗？我正在尝试制作一个通用的 BST，具有 DDL(双向链表)数据结构。问题是我的 ADT 已初始化，因为我的 isEmpty 方法有效，但我的 public addNewElement 起诉 private 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

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