Java二叉搜索树duplicateCheck校验方法始终返回非重复问题求助

1. main方法测试逻辑错误 #

你对t2的初始化逻辑存在冗余操作：调用t1.clone()后t2已经复制了t1的全部节点元素，后续又重复插入了9个相同的KeyedItem元素。如果你的BinarySearchTree实现允许重复Key存在，此时t2的节点总数是t1的2倍，countNodes判断直接返回false；如果你的BST不允许重复Key，插入操作会被忽略，那这个环节不会触发错误，但测试逻辑本身是冗余的。

2. duplicateCheck方法逻辑缺陷 #

现有方法存在两个问题：

• 缺失单节点为空的判断：当其中一个节点为null、另一个不为null时，代码会直接进入countNodes逻辑，若countNodes方法没有处理入参为null的情况，会直接抛出空指针异常，即便countNodes做了null兼容，这个判断也是多余的
• 冗余的节点数统计：递归比对子树的过程已经覆盖了结构和值的校验，提前统计节点数只会额外增加性能消耗，没有实际作用

修复后的代码 #

修复后main方法 #

import java.util.*;

public class MyTree
{
    public static void main(String[] args) throws CloneNotSupportedException
    {
        BinarySearchTree t1 = new BinarySearchTree();
        t1.insert(new KeyedItem("M"));
        t1.insert(new KeyedItem("J"));
        t1.insert(new KeyedItem("D"));
        t1.insert(new KeyedItem("F"));
        t1.insert(new KeyedItem("L"));
        t1.insert(new KeyedItem("W"));
        t1.insert(new KeyedItem("S"));
        t1.insert(new KeyedItem("T"));
        t1.insert(new KeyedItem("Z"));

        // 方式一：直接初始化新树插入相同元素
        BinarySearchTree t2 = new BinarySearchTree();
        t2.insert(new KeyedItem("M"));
        t2.insert(new KeyedItem("J"));
        t2.insert(new KeyedItem("D"));
        t2.insert(new KeyedItem("F"));
        t2.insert(new KeyedItem("L"));
        t2.insert(new KeyedItem("W"));
        t2.insert(new KeyedItem("S"));
        t2.insert(new KeyedItem("T"));
        t2.insert(new KeyedItem("Z"));

        // 方式二：clone后不重复插入即可
        // BinarySearchTree t2 = (BinarySearchTree) t1.clone();

        if (t1.duplicateCheck(t2))
            System.out.println("Duplicates");
        else
            System.out.println("Not Duplicates");
    }
}

修复后duplicateCheck方法 #

public boolean duplicateCheck(BinarySearchTree otherTree)
{
    return duplicateCheck(this.root, otherTree.getRoot());
}

protected boolean duplicateCheck(TreeNode t1, TreeNode t2)
{
    // 两节点均为空，结构一致
    if (t1 == null && t2 == null)
        return true;
    // 单个节点为空，结构不一致
    if (t1 == null || t2 == null)
        return false;

    KeyedItem key1 = (KeyedItem) t1.getItem();
    KeyedItem key2 = (KeyedItem) t2.getItem();
    String s1 = (String) key1.getKey();
    String s2 = (String) key2.getKey();
    // 当前节点值不相等
    if (!s1.equals(s2))
        return false;

    // 递归比对左右子树
    return duplicateCheck(t1.getLeft(), t2.getLeft()) && duplicateCheck(t1.getRight(), t2.getRight());
}

额外说明 #

当前修复后的方法判断的是两棵树的结构和所有节点值完全一致，如果你需要判断的是两棵二叉搜索树存储的元素集合相同、不要求结构一致，只需要分别对两棵树做中序遍历得到有序列表，再比对两个列表内容是否相等即可（二叉搜索树的中序遍历结果为升序序列，元素集合相同的情况下遍历结果一定一致）。

内容的提问来源于stack exchange，提问作者mm1234