Java 递归深度克隆

Question

晚上好。

我正在尝试实现 AVL 树，但在旋转过程中复制节点时遇到问题：

如果我用浅拷贝来做，就会发生相当可预测的混乱。
如果我用手动深拷贝来做，我只能复制object（节点）的直接属性，而不能复制它的更深层次。澄清一下，如果我有一个有 2 children 的节点，它自己有 1-2 children 并且它的 children 可能有它们自己的 children，...我可以仅复制初始节点及其直接 children，但丢失 grandchildren 和更多后代。

所以，我想知道是否有办法绕过这个限制。
这是 class 的完整代码（主要是对 initialise() 的调用），其他一切都正常运行，所以如果我能够设法在轮换中正确复制节点，我将有一个工作AVL树。

在此先感谢您的帮助。

import java.util.ArrayList;

public class NodeQ
{
static boolean isEmpty=true;
private int h=1;
private double x, y;
private ArrayList<Segment> segmentsStarting=new ArrayList<Segment>();
private NodeQ left=null, right=null;

public NodeQ(double abs, double ord) {x=abs; y=ord;}
public NodeQ(NodeQ Q) {this.x=Q.x; this.y=Q.y; this.segmentsStarting=Q.segmentsStarting;}

public double getX() {return x;}
public double getY() {return y;}
public NodeQ getLeft() {return left;}
public NodeQ getRight() {return right;}
public ArrayList<Segment> getSegmentsStarting() {return segmentsStarting;}
public int getH(){return h;}

public void setX(double abs) {x=abs;}
public void setY(double ord) {y=ord;}
public void setLeft(NodeQ l) {left=l;}
public void setRight(NodeQ r) {right=r;}
public void addSegment(Segment s) {segmentsStarting.add(s);}

public void calcH()
{
    if (this.left!=null)
    {
        if (this.right != null)
        {
            if (this.left.h > this.right.h) this.h = this.left.h + 1;
            else this.h = this.right.h + 1;
        }
        else this.h = this.left.h + 1;
    }
    else if (this.right!=null) this.h=this.right.h+1;
}

public void initialise(Segment segment)
{
    if (NodeQ.isEmpty)
    {
        y=segment.yUpper; 
        x=segment.xUpper;
        addSegment(segment); 
        setLeft(new NodeQ(segment.xLower, segment.yLower));
        h=2;
        NodeQ.isEmpty=false;
    }
    else
    {
        insert(segment.xUpper, segment.yUpper, true, segment);
        insert(segment.xLower, segment.yLower, false, segment);
    }
}

public void deepCopy(NodeQ Q)
{
    this.x=Q.x;
    this.y=Q.y;
    this.segmentsStarting=Q.segmentsStarting;
    if (Q.left==null)this.left=null;
    else this.left=new NodeQ(Q.left);
    if (Q.right==null) this.right=null;
    else this.right=new NodeQ(Q.right);
}

public void insert(double abs, double ord, boolean isUpperEndpoint, Segment s)
{
    if (y>ord || (y==ord && x<abs))
    {
        if (left==null)
        {
            left=new NodeQ(abs, ord); 
            if (isUpperEndpoint) addSegment(s);
        }
        else left.insert(abs, ord, isUpperEndpoint, s); 
    }
    else
    {
        if (right==null)
        {
            right=new NodeQ(abs, ord);
            if (isUpperEndpoint) addSegment(s);
        }
        else right.insert(abs, ord, isUpperEndpoint, s);
    }
    balancing();
}

public void leftRotation()
{
    NodeQ tmp=new NodeQ(-1, -1);
    tmp.deepCopy(this);
    this.deepCopy(this.right);

    if (this.left==null) tmp.right=null;
    else tmp.right=new NodeQ(this.left);
    this.left=new NodeQ(tmp);

    tmp.calcH();
    this.calcH();
}

public void rightRotation()
{
    NodeQ tmp=new NodeQ(-1, -1);
    tmp.deepCopy(this);
    this.deepCopy(this.left);

    if (this.right==null) tmp.left=null;
    else tmp.left=new NodeQ(this.right);
    this.right=new NodeQ(tmp);

    tmp.calcH();
    this.calcH();
}

public int calcBalance()
{
    int bal=0;
    if (left==null)
    {
        if (right!=null) bal=right.h;
    }
    else
    {
        if (right==null) bal=-left.h;
        else bal=right.h-left.h;
    }
    return bal;
}

public void balancing()
{
    int b=calcBalance();
    if (b==2)
    {
        if (right.calcBalance()<0) right.rightRotation();
        leftRotation();
    }
    else if (b==-2)
    {
`       if (left.calcBalance()>0) left.leftRotation();
        rightRotation();
    }
    else calcH();
}
}

Answer 1

深度克隆的一种非常简单的方法是实现可序列化，然后序列化/反序列化对象（例如到 ByteArrayOutputStream）。

Answer 2

你应该简单地避免复制节点；您可以通过分配 left 和 right 指针来平衡子树。

旋转函数应将子树根作为参数，return变换后的子树；旋转树 "in place" 是一个不必要的主要并发症。

Java 递归深度克隆

Java recursive deep cloning

java

deep-copy

avl-tree