二进制搜索树Instantiaition

Question

我已创建二进制搜索树通过使用树接口和递归（我知道使用节点类我可以实现相同）提供的方法添加和检查元素是否在二进制搜索树或不。

我面临的问题是在实例化&显示BST的元素。

这里是我的代码

树接口：

package bst; 

public interface Tree<D extends Comparable>{ 

    public boolean isempty(); 
    public int cardinality(); 
    public boolean member(D elt); 
    public NonEmptyBst<D> add(D elt); 

} 

EmptyBst类：

package bst; 

public class EmptyBst<D extends Comparable> implements Tree<D>{ 
    public EmptyBst(){ 
     D data=null; 
    } 

    @Override 
    public boolean isempty() { 
     // TODO Auto-generated method stub 
     return true; 
    } 

    @Override 
    public int cardinality() { 
     // TODO Auto-generated method stub 
     return 0; 
    } 

    @Override 
    public boolean member(D elt) { 
     // TODO Auto-generated method stub 
     return false; 
    } 

    @Override 
    public NonEmptyBst<D>add(D elt) { 
     // TODO Auto-generated method stub 
     return new NonEmptyBst<D>(elt); 
    } 

} 

NonEmptyBst类

package bst; 

public class NonEmptyBst<D extends Comparable> implements Tree<D> { 
    D data; 
    D root; 
    Tree<D> left; 
    Tree <D>right; 

    public NonEmptyBst(D elt){ 
     data=elt; 
     root=elt; 
     left=new EmptyBst<D>(); 
     right=new EmptyBst<D>(); 

    } 
    NonEmptyBst(){ 
     D dataThis=this.data; 
    } 
    public NonEmptyBst(D elt,Tree<D>leftTree,Tree<D>rightTree){ 
     data=elt; 
     left=leftTree; 
     right=rightTree; 
    } 
    @Override 
    public boolean isempty() { 
     // TODO Auto-generated method stub 
     return false; 
    } 
    @Override 
    public int cardinality() { 
     // TODO Auto-generated method stub 
     return 1+left.cardinality()+right.cardinality(); 
    } 



    public boolean member(D elt) { 
     if (data == elt) { 
      return true; 
     } else { 
      if (elt.compareTo(data) < 0) { 
       return left.member(elt); 
      } else { 
       return right.member(elt); 
      } 
     } 
    } 

    public NonEmptyBst<D> add(D elt) { 
     if (data == elt) { 
      return this; 
     } else { 
      if (elt.compareTo(data) < 0) { 
       return new NonEmptyBst(data, left.add(elt), right); 
      } else { 
       return new NonEmptyBst(data, left, right.add(elt)); 
      } 
     } 
    } 
} 

BinarySearchTree类

package bst; 
import bst.Tree; 
import bst.EmptyBst; 
import bst.NonEmptyBst; 

public class BinarySearchTree { 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     NonEmptyBst abcd=new NonEmptyBst("abc"); 
     NonEmptyBst ab=new NonEmptyBst(67); 

     abcd.add("cry me a river"); 
     abcd.add("geeehfvmfvf"); 
     abcd.add("I'm Sexy and i know it"); 
     abcd.add("zzzzsd"); 
     abcd.add("zzzzsd"); 
     abcd.add("zzzfdsf"); 
     abcd.add("zzfedfrsd"); 
     abcd.add("tgrgdzsd"); 
     abcd.add("gtrgrtgtrgtrzzzzsd"); 
     abcd.add("zzzzsd"); 
     abcd.add("zdddzzzsd"); 
     abcd.add("zzzzsd"); 
     abcd.add("zzzzsd"); 

    } 
} 

** 我如何在所有节点访问的数据，然后打印出来？我现在面临的具体问题是在获得一个例外，即ClassCastException当我访问在“叶节点”即使我在Initalize new NonEmptyBst<D>我NonEmptyBst<D>(D elt)constructor我最终空指针异常

Exception in thread "main" java.lang.NullPointerException 
    at java.lang.String.compareTo(Unknown Source) 
    at java.lang.String.compareTo(Unknown Source) 
    at bst.NonEmptyBst.add(NonEmptyBst.java:51) 
    at bst.NonEmptyBst.add(NonEmptyBst.java:54) 
    at bst.BinarySearchTree.main(BinarySearchTree.java:11) 

Answer 1

我不太确定我是否需要EmptyBst，除非您尝试遵循Null对象的设计模式。

具体而言，如果data == null && left == null && right == null可以容易地检查“空”树。另外，这里不需要data，因为它是一个局部变量并且从未被引用。

public EmptyBst(){ 
    D data=null; 
} 

，并有D data和D root之间的差异？

我认为你需要调整你的add方法来捕获递归的结果。

public NonEmptyBst<D> add(D elt) { 
    if (data == elt) { 
     return this; 
    } else { 
     if (elt.compareTo(data) < 0) { 
      this.left = this.left.add(elt); 
     } else { 
      this.right = this.right.add(elt); 
     } 
    } 

    return this; 
} 

Answer 2

您需要递归访问它。由于我没有你的节点实现，我会写一个普通的例子：

// Return a list with all the nodes 
public List<Node> preOrder() { 
    List<Node> l = new ArrayList<Node>(); 
    l.add(this.value); // Add the data of the root 
    if(this.left != null) // Add elements to the left 
     l.addAll(this.left.preOrder()); 
    if(this.right != null) // Add elements to the right 
     l.addAll(this.right.preOrder()); 
    return l; 
} 

，那么只需在调用它：

List<Node> nodes = myTree.preOrder(); 

然后遍历列表，做你想做的。