1

请考虑以下代码

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接口的 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)

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

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

请告知我做错了什么，因为自我调试还没有帮助。

4

1 回答 1

2

似乎缺少父更新-不确定这是否是唯一的问题...

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

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

你可能想把它变成一个静态内部类并添加一个指向树的显式指针（如果你需要它——一些访问 root 的 Node 方法看起来应该是 BSTtree 方法）。

于 2014-10-25T15:36:13.783 回答