Двоичное дерево поиска поиска:

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"); 

    } 
} 

** Как я могу получить доступ к данным на всех узлах, а затем распечатать их? Особая проблема, я облицовкой В Getting исключение именно ClassCastException, когда доступ в «лист» Узлы и даже если я инициализировать 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 Object.

В частности, «пустое» дерево можно легко проверить, если 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(); 

А затем цикл по списку, чтобы делать все, что вы хотите.