java - 如何检查两个二叉搜索树是否具有相同的精确键(忽略值)？

Question

如何实现最后一个方法？我已经实现了这个多态二叉搜索树的大部分开始部分，但不知道如何检查两棵树是否具有相同的键。键可以按任何顺序，但两棵树需要具有相同的大小和相同的键(值并不重要)。如果它与 otherTree 具有相同的键，则此方法 hasSameKeys 返回一个 boolean 值(最底部的方法)。我首先检查树的大小是否相同，但除此之外什么都不知道。我不能使用任何数组或其他 Java 库类，但我可以添加辅助方法(可能是递归的)。有建议吗？

@SuppressWarnings("unchecked")
public class NonEmptyTree<K extends Comparable<K>, V> implements Tree<K, V> {

    public K key;
    public V value;
    public Tree<K,V> leftTree;
    public Tree<K,V> rightTree;


    public NonEmptyTree(K key, V value, Tree<K,V> leftTree, 
            Tree<K,V> rightTree) {
        this.key=key;
        this.value=value;
        this.leftTree=leftTree;
        this.rightTree=rightTree;
    }

    public NonEmptyTree<K, V> addKeyWithValue(K keyToAdd, V valueToAdd) {
       if(keyToAdd.compareTo(key)==0) {
         value = valueToAdd;
       }

       if(keyToAdd.compareTo(key)>0) {
         rightTree = rightTree.addKeyWithValue(keyToAdd, valueToAdd);
       }

       if(keyToAdd.compareTo(key)<0) {
         leftTree = leftTree.addKeyWithValue(keyToAdd, valueToAdd);
       }

       return this;
    }

    public int size() {
       return 1 + leftTree.size() + rightTree.size();
    }

    public V lookup(K lookUpKey) {
       if(lookUpKey.compareTo(key)>0) {
          return this.rightTree.lookup(lookUpKey);
       }
       if(lookUpKey.compareTo(key)<0) {
          return this.leftTree.lookup(lookUpKey);
       }
       if(lookUpKey.compareTo(key)!=0) {
          return null;
       }
       return this.value;
    }

    public K max() throws EmptyTreeException {    
       try{
          K temp = this.rightTree.max();
          return temp;
       }
       catch(EmptyTreeException e) {
          return key;
       }
    }

    public K min() throws EmptyTreeException {    
       try{
            K temp = this.leftTree.min();
            return temp;
       }
       catch(EmptyTreeException e) {
            return key;
       }
    }

    public Tree<K, V> deleteKeyAndValue(K keyToDelete) {
       if(keyToDelete.compareTo(key)>0) {
          rightTree = rightTree.deleteKeyAndValue(keyToDelete);
       }

       if(keyToDelete.compareTo(key)<0) {
          leftTree = leftTree.deleteKeyAndValue(keyToDelete);
       }

       if(keyToDelete.compareTo(key)==0) {
          try{
              value = this.lookup(rightTree.min());
              key = rightTree.min();
          }
          catch(EmptyTreeException e) {
              return this.leftTree;
          }
       }
       return this;
    }

    public boolean haveSameKeys(Tree<K, V> otherTree) { 
        boolean check = true;

        if(this.size()!=otherTree.size()) {
           check = false;
        }
    }

    // Tests haveSameKeys() with two empty trees.
    @Test public void testPublic9() {
       Tree<Byte, Boolean> tree= EmptyTree.getInstance();
       Tree<Byte, Boolean> tree2= EmptyTree.getInstance();

       assertTrue(tree.haveSameKeys(tree2));
       assertTrue(tree2.haveSameKeys(tree));
    }

    // Tests haveSameKeys() with an empty tree and a nonempty tree
    @Test public void testPublic10() {
       Tree<String, Integer> tree= EmptyTree.getInstance();
       Tree<String, Integer> tree2= TestCode.exampleTree1();

       assertFalse(tree.haveSameKeys(tree2));
       assertFalse(tree2.haveSameKeys(tree));
    }

    // Tests haveSameKeys() with two nonempty trees that have the same keys.
    @Test public void testPublic11() {
       Tree<String, Integer> tree= TestCode.exampleTree1();
       Tree<String, Integer> tree2= TestCode.exampleTree1();

       assertTrue(tree.haveSameKeys(tree2));
       assertTrue(tree2.haveSameKeys(tree));
    }

Answer 1

您可以使用递归来检查树中的每个键是否包含在另一棵树中，因为如果不存在这样的键，lookup 将返回 null。

为此，我做了一些假设:

• EmptyTree.haveSameKeys 返回 otherTree.size() == 0
• EmptyTree.hasSameKeys始终返回true
• EmptyTree.lookup 始终返回 null。

I CAN add public methods to the Tree interface that Empty/NonEmpty trees implement though if i please...

因此，您需要将 hasSameKeys 添加到 Tree 接口(interface):

// Checks if every key in 'this' tree is contained in 'otherTree'
public boolean hasSameKeys(Tree<K, V> otherTree) {
    if (otherTree.lookup(this.key) == null) { // if key does not exist
        return false;
    }

    return (leftTree.hasSameKeys(otherTree) && rightTree.hasSameKeys(otherTree));
}

public boolean haveSameKeys(Tree<K, V> otherTree) { // Both trees should have the same keyset
    return hasSameKeys(otherTree) && otherTree.hasSameKeys(this); 
}

返回什么:

• 空树和空树； 真&&真。 => 空树具有相同的键集
• NonEmptyTree 和 EmptyTree； 假&&真。 => 或者反过来。永远。
• NonEmptyTree 和 NonEmptyTree； true => 如果两者具有完全相同的 key 集。