Java深拷贝-错误的引用分配

Question

请考虑以下代码

public class Pair implements Cloneable, Comparable<Para> {

    ...

    public Pair(String key, double value) throws Exception {
        if (value <= 0) throw new IllegalArgumentException();

        this.key = key;
        this.value = value;
    }

    ...

    @Override
    public Pair clone() throws CloneNotSupportedException {
        return (Pair) super.clone();
    }
}

和

public class BSTtree implements Dictionary, Cloneable {

    ...

    private class Node implements Cloneable, Comparable<Node> {
        Para elem;
        Node left = null;
        Node right = null;
        Node parent = null;

        Node () {
            this.elem = null;
        }

        Node (Pair elem) {
            this.elem = elem;
        }

        ...

        @Override
        public Node clone() throws CloneNotSupportedException {
            Node cloned = new Node();

            cloned.elem = elem.clone();
            if (left != null) cloned.left = left.clone();
            if (right != null) cloned.right = right.clone();

            return cloned;
        }
    }

    ...

    @Override
    public BSTtree clone() throws CloneNotSupportedException {
        BSTtree cloned = new BSTtree();
        cloned.root = root.clone();

        return cloned;
    }
}

我正在尝试实现我自己的具有 Cloneable 接口(interface)的 BST 树。我遇到的问题是

BSTtree alfa = new BSTtree();
...
BSTtree beta = alfa.clone();

我认为没有正确设置对树alfa和beta的引用。我为什么这么认为？看看下面的内容

alfa.printTree(); //(VOID  1,00), (a  1,00), (b  2,00), (c  3,00), (e  5,00)
beta.printTree(); //(VOID  1,00), (a  1,00), (b  2,00), (c  3,00), (e  5,00)

beta.remove("a");

alfa.printTree(); //(VOID  1,00), (b  2,00), (c  3,00), (e  5,00)
beta.printTree(); //(VOID  1,00), (a  1,00), (b  2,00), (c  3,00), (e  5,00)

alfa.remove("e");

alfa.printTree(); //(VOID  1,00), (b  2,00), (c  3,00), (e  5,00)
beta.printTree(); //(VOID  1,00), (a  1,00), (b  2,00), (c  3,00), (e  5,00)

因此，您可以在克隆后看到，从 beta 中删除的任何操作实际上都是从 alfa 中删除的，而从 alfa 中删除根本不会删除。当然，在调用 clone() 之前，alfa 上的每个操作都工作正常。

这是为了学习，主要任务是实现一个有效的 clone() 方法，所以我不想使用任何其他方式来执行深复制。

请告诉我我做错了什么，因为 self 调试还没有帮助解决这个问题。

Answer 1

父更新似乎丢失了——不确定这是否是唯一的问题...

    @Override
    public Node clone() throws CloneNotSupportedException {
        Node cloned = new Node();

        cloned.elem = elem.clone();
        if (left != null) {
           cloned.left = left.clone();
           cloned.left.parent = cloned;
        }
        if (right != null) {
           cloned.right = right.clone();
           cloned.right.parent = cloned;
        }

        return cloned;
    }

附注我认为另一个问题是 Node 是一个非静态内部类。因此它总是有一个隐式指针指向它在其中创建的树。在 Node.clone 中调用 new Node() 的地方，这是在原始树的范围内，因此它仍然指向原始树，但它需要是新树的内部类。在内部类声明中添加 static 会突出问题。

您可能希望将其转换为静态内部类，并添加一个指向树的显式指针(如果您需要的话——一些访问 root 的 Node 方法看起来实际上应该是 BSTtree 方法)。