java - 在 Java 中返回多态二叉搜索树的大小？

Question

我正在尝试为多态二叉搜索树编写一个 size() 方法。IE。具有类 EmptyTree 和 NonEmptyTree 的 BST，它们都实现了“树”接口(interface)。 EmptyTree 用于表示空树或子树而不是 null(就像在常规 BST 中一样)

public interface Tree<K extends Comparable<K>, V> {
    public int size();
    public NonEmptyTree<K, V> add(K key, V value);

    //bunch of other methods
}

我已经让 EmptyTree 和 NonEmptyTree 都实现了 Tree 接口(interface)的 size() 方法，如下所示:

public int size() { //in EmptyTree class
   return 0;
}

public int size() { //in NonEmptyTree class
   return 1 + left.size() + right.size();
}

但是，当我尝试在测试中运行它时:

Tree<Integer, String> treeThree = EmptyTree.getInstance(); //EmptyTree is a singleton class
   treeThree = treeThree.add(3, "3"); 
   treeThree = treeThree.add(2, "2"); 
   treeThree = treeThree.add(1, "1"); 
   treeThree = treeThree.add(4, "4");
   assertEquals(4, treeThree.size());

它说 treeThree 的大小是 3，而不是应该的 4。

虽然它对这些人来说效果很好:

        Tree<Integer, String> empty = EmptyTree.getInstance();
        assertEquals(0, empty.size());

        Tree<Integer, String> treeOne = EmptyTree.getInstance();
        treeOne = treeOne.add(2, "2"); treeOne = treeOne.add(1, "1"); treeOne = treeOne.add(3, "3");
        assertEquals(3, treeOne.size());

        Tree<Integer, String> treeTwo = EmptyTree.getInstance();
        treeTwo = treeTwo.add(3, "3"); treeTwo = treeTwo.add(2, "2");
        assertEquals(2, treeTwo.size());

EmptyTree添加方法:

public NonEmptyTree<K, V> add(K key, V value) {  
    return new NonEmptyTree(key, value);
}

NonEmptyTree 添加方法:

public NonEmptyTree<K, V> add(K key, V value) {
      if(this.key.compareTo(key) == 0) {
          this.value = value;
          return this;
      }
      else {
          if(key.compareTo(this.key) < 0) { 
              if(this.left.lookup(key) == null) {
                  this.left = new NonEmptyTree<K,V>(key, value);
                  return this;
              }
              else
                  return this.left.add(key, value);
          }
          else if(key.compareTo(this.key) > 0) { 
              if(this.right.lookup(key) == null) {
                  this.right = new NonEmptyTree<K,V>(key, value);
                  return this;
              }
              else
                  return this.right.add(key, value);
          }
      }
      return this;
  }

空树查找:

public V lookup(K key) {
    return null;
  }

NonEmptyTree 查找:

public V lookup(K key) {
      if(key.compareTo(this.key) == 0)
          return this.value;
      else {
          if(key.compareTo(this.key) < 0)
              return this.left.lookup(key);
          if(key.compareTo(this.key) > 0) 
              return this.right.lookup(key);
      }

    return null;
  }

Answer 1

正如 j_random_hacker 先生在评论中所说，您不需要在 add 方法中调用 look up 方法。这将替换包含 EmptyTree 作为子树的整个子树。像这样更改您的添加方法，

public NonEmptyTree<K, V> add(K key, V value) {
      if(this.key.compareTo(key) == 0) {
          this.value = value;
      }
      else {
          if(key.compareTo(this.key) < 0) { 
                  this.left = this.left.add(key, value);
          }
          else { 
                  this.right = this.right.add(key, value);
          }
      }
      return this;
  }