バイナリ検索ツリーの追加、削除、包含、イテレータが動作しているかどうかをテストしたい

Question

ノードを追加、削除、検索するためのメソッドを持つ単純なバイナリツリーを実装しています。ノードを通過する。私はこのクラス/メソッドをテストするためのテストプログラムを書こうと思っていますが、私は方法を知らないのです。できる場合はお手伝いください。

import java.util.*; 

public class BinarySearchTree<T> extends AbstractSet<T> { 
    private Node<T> root; 
    private int size; 

    private static class Node<T> { 
     private T element; 
     private Node<T> left = null; 
     private Node<T> right = null; 
     private Node<T> parent; 

     private Node(T element, Node<T> parent) { 
      this.element = element; 
      this.parent = parent; 
     } 
    } 

    public BinarySearchTree() { 
     root = null; 
     size = 0; 
    } 

    public BinarySearchTree(BinarySearchTree<T> other) { 
     root = null; 
     size = 0; 
     for (T element: other) 
      add(element); 
    } 

    public int size() { 
     return size; 
    } 

    public Iterator<T> iterator() { 
     return new TreeIterator(); 
    } 

    public boolean add(T element) { 
     if (root == null) { 
      root = new Node<T>(element, null); 
      size++; 
      return true; 
     } else { 
      Node temp = root; 
      int comp; 
      while (true) { 
       comp = ((Comparable)(element)).compareTo(temp.element); 
       if (comp == 0) 
        return false; 
       if (comp<0) { 
        if (temp.left != null) 
         temp = temp.left; 
        else { 
         temp.left = new Node<T>(element, temp); 
         size++; 
         return true; 
        } 
       } else { 
        if (temp.right != null) 
         temp = temp.right; 
        else { 
         temp.right = new Node<T>(element, temp); 
         size++; 
         return true; 
        } 
       } 
      } 
     } 
    } 

    public boolean remove(Object obj) 
    { 
    Node<T> e = getNode(obj); 
    if (e == null) 
     return false; 
    deleteNode(e); 
    return true; 
    } 

    private Node<T> getNode(Object obj) 
    { 
    int comp; 
    Node<T> e = root; 
    while (e != null) { 
     comp = ((Comparable)(obj)).compareTo(e.element); 
     if (comp == 0) 
     return e; 
     else if (comp < 0) 
     e = e.left; 
     else 
     e = e.right; 
    } 
    return null; 
    } 

    public T mapAdd(T obj) 
    { 
    if (root == null) { 
     root = new Node<T>(obj, null); 
     size++; 
     return root.element; 
    } 
    int comp; 
    Node<T> e = root; 
    Node<T> p = null; 
    boolean left = true; 
    while (e != null) { 
     p = e; 
     comp = ((Comparable)(obj)).compareTo(e.element); 
     if (comp == 0) 
     return e.element; 
     else if (comp < 0) { 
     left = true; 
     e = e.left; 
     } else { 
     e = e.right; 
     left = false; 
     } 
    } 
    e = new Node<T>(obj, p); 
    if (left) 
     p.left = e; 
    else 
     p.right = e; 
    size++; 
    return e.element; 
    } 




    public boolean contains(Object obj) 
    { 
    return getNode(obj) != null; 
    } 

    private Node<T> deleteNode(Node<T> p) 
    { 
    size--; 
    if (p.left != null && p.right != null) { 
     Node<T> s = successor(p); 
     p.element = s.element; 
     p = s; 
    } 

    Node<T> replacement; 
    if (p.left != null) 
     replacement = p.left; 
    else 
     replacement = p.right; 

    if (replacement != null) { 
     replacement.parent = p.parent; 
     if (p.parent == null) 
     root = replacement; 
     else if (p == p.parent.left) 
     p.parent.left = replacement; 
     else 
     p.parent.right = replacement; 
    } else if (p.parent == null) { 
     root = null; 
    } else { 
     if (p == p.parent.left) 
     p.parent.left = null; 
     else 
     p.parent.right = null; 
    } 
    return p; 
    } 

    private Node<T> successor(Node<T> e) 
    { 
    if (e == null) { 
     return null; 
    } else if (e.right != null) { 
     Node<T> p = e.right; 
     while (p.left != null) 
     p = p.left; 
     return p; 
    } else { 
     Node<T> p = e.parent; 
     Node<T> child = e; 
     while (p != null && child == p.right) { 
     child = p; 
     p = p.parent; 
     } 
     return p; 
    } 
    } 

    private class TreeIterator implements Iterator<T> 
    { 
    private Node<T> lastReturned = null; 
    private Node<T> next; 

    private TreeIterator() 
    { 
     next = root; 
     if (next != null) 
     while (next.left != null) 
      next = next.left; 
    } 

    public boolean hasNext() 
    { 
     return next != null; 
    } 

    public T next() 
    { 
     if (next == null) 
     throw new NoSuchElementException(); 
     lastReturned = next; 
     next = successor(next); 
     return lastReturned.element; 
    } 

    public void remove() 
    { 
     if (lastReturned == null) 
     throw new IllegalStateException(); 
     if (lastReturned.left != null && lastReturned.right != null) 
     next = lastReturned; 
     deleteNode(lastReturned); 
     lastReturned = null; 
    } 
    } 

}  

Answer 1

クラスが契約に準拠していることをテストする必要があります。だから良い出発点は、その契約を書き留めることです。たとえば、ツリーに要素を追加すると、その要素などに対してtrueを返します。これは、直接テストケースに変換されます。

• 空のツリーを作成すると、
• 空のツリーを作成し、要素を追加し、サイズ== 1をチェックし、containsがtrueを返していることを確認し、イテレータhasNextがtrueを返すかどうかをチェックします。イテレータは次に追加した要素を返します。
• N要素のツリーを作成し、サイズをチェックし、イテレータをチェックして、サイズをN-1に変更し、削除された要素がツリーにないことを確認します。

など

Answer 2

treeが要素含まれないときは、ここに方法containsためのテストを開始するには：tree要素が含まれていない場合に

@Test 
public void containsWhenElementIsPresent() { 
    String element = "StackOverflow"; 
    BinarySearchTree tree = new BinarySearchTree<>(); 
    tree.add(new String(element)); 
    assertThat(tree.contains(element), is(true)); 
} 

そして、ここで1を：

@Test 
public void containsWhenElementIsAbsent() { 
    String element = "StackOverflow"; 
    assertThat(new BinarySearchTree<>().contains(element), is(false)); 
} 

他のすべてのテストでは幸いです。ところで、私はJUnit 4とHamcrestを使いました。

Answer 3

私は実際にあなたの質問はコードなしで良いと思っています。それを実際に動かすことなく（あるいは単体テストを書くことなく）意味をなすことができるのは、大きすぎます。

バイナリツリー（または実際に他のタイプのツリー）の単体テストを書く方法は？

まず、単位テストとは、操作を実行して既知の状態にツリーを初期化し、テストツリーが期待される結果ツリーと同じであることを確認することです。 など。空のツリーから始め、ノード "a"を追加すると、結果は単一のノード "a"を持つツリーであると考えられます。 - 簡単にツリーをロードする方法

1：我々は2つの機能を必要とし、このテストを行うには

。 2 - ツリーを予想結果と簡単に比較する方法。

これを行う一般的で効率的な方法の1つは、ツリーの文字列表現です。私はあなたのコードから、木はバイナリツリーではなくバイナリ検索ツリーであるので、深さ優先検索（DFS）を使用することはツリーの表現を得るための自然な方法であることがわかります。

あなたのテストは今見て：

1. は、各文字は、ノードを表す文字列からツリーをロードします。
2. ロード操作を実行します。
3. DFSを使用してツリーの文字列表現を取得し、 '|'あなたがレベルに戻るたびに。
4. 予想されるツリーの文字列表現と比較します。

など。テスト挿入へ：

テスト1 - 空の木 1.何も（空木） 2.アサートが文字列に「|」である保存された文字列 4へ「」 3.保存ツリーを行いません。

テスト2 - 左葉

1. ロードツリー "B"
2. 挿入 ""
3. 保存ツリー文字列へ
4. アサートは、文字列がに等しい保存 "| B |"。

テスト3 - 文字列の右葉の

1. ロードツリー "BA"
2. 挿入 "C"
3. 保存ツリー
4. アサートが文字列「に等しい保存| BC | | "。

は、この情報がお役に立てば幸いです。