二進制搜索樹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(); 

然後遍歷列表，做你想做的。