深度复制表达式树（包括其父层次结构）的函数？

Question

我想深度复制表达式树。我知道传统的做法在大多数情况下都有效。这是表达式树的基本版本：

public class Expression {
    public Expression left;
    public Expression right;
    public Expression parent;
    public String middle;

    public Expression(Expression left, String middle, Expression right) {
        this.left = left;
        this.right = right;
        this.middle = middle;

        if (left != null) {
            left.parent = this;
        }

        if (right != null) {
            right.parent = this;
        }
    }

    public void setLeft(Expression left) {
        this.left = left;
        if (left != null) {
            left.parent = this;
        }
    }

    public void setRight(Expression right) {
        this.right = right;
        if (right != null) {
             right.parent = this;
        }
    }}

这是传统的深复制方式：

public Expression copy() {
    Expression leftCopy = (left != null) ? left.copy() : null;
    Expression rightCopy = (right != null) ? right.copy() : null;
    
    return new Expression(leftCopy, operator, rightCopy, null);
}

现在效果很好，但我想要另一个深度复制功能，它也可以复制父层次结构。当前的深层复制仅复制表达式并将其设为根，无论它是否实际上是根。现在我将如何制作一个完整的深度复制函数，以确保复制整个结构，包括父层次结构。我相当确定这个新的深度复制功能将利用前一个功能。

Answer 1

要创建还包括父层次结构的表达式树的深层副本，您需要修改复制过程以保留父子关系。您提供的传统深度复制方法以自下而上的方式复制树，但不会在新树中维护父引用。

这是实现此目的的方法：

1. 创建递归复制函数：该函数应递归复制每个节点，保留父子关系。由于

   parent

   字段也是一个

   Expression

   ，因此需要以保持原始树结构的方式进行复制。

2. 处理父引用：要正确复制父引用，您需要将父引用传递给复制函数，并在创建新的

   Expression

   对象时使用它。

这是完整深拷贝功能的可能实现：

public class Expression {
    // ... existing fields and methods ...

    public Expression deepCopy() {
        return deepCopy(this, null);
    }

    private static Expression deepCopy(Expression node, Expression parentCopy) {
        if (node == null) {
            return null;
        }

        Expression leftCopy = deepCopy(node.left, node);
        Expression rightCopy = deepCopy(node.right, node);

        Expression newNode = new Expression(leftCopy, node.middle, rightCopy);
        newNode.parent = parentCopy;

        return newNode;
    }
}

在此实施中：

• deepCopy

  方法已重载。公共版本对于用户来说是一种方便的方法，它调用私有的递归版本，并以

  null

  作为初始父级。
• 私有

  deepCopy

  方法执行实际工作。它递归地复制左子节点和右子节点，然后创建一个新节点。新节点的父节点设置为原始节点父节点的副本，该副本作为参数提供。
• 此方法可确保在树的新副本中正确维护父子关系。

尝试提供详细的答案，希望有帮助:)