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

Question

我正在尝试为多态二叉搜索树编写一个size（）方法。也就是说，BST具有EmptyTree和NoneptyTree类，这两个类都实现了“树”接口。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和NoneptyTree从树接口实现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());

它说树的大小是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);
}

非空树添加方法：

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;
  }

非空树查找：

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方法中调用查找方法。这将替换包含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;
  }