如何实现包含父层级的表达式树完整深度复制？

现有表达式树类定义 #

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

传统复制方法的局限 #

传统的copy()方法仅能复制当前节点及其子树，无法保留原节点的父层级关联：

// 注：原代码构造方法参数存在笔误，已修正operator为middle
public Expression copy() {
    Expression leftCopy = (left != null) ? left.copy() : null;
    Expression rightCopy = (right != null) ? right.copy() : null;
    
    return new Expression(leftCopy, middle, rightCopy);
}

该方法生成的副本只能作为独立子树的根节点，无法通过副本节点回溯到原树的上层节点，无法满足完整树结构的复制需求。

需求说明 #

需要实现copyFull()方法，满足：

• 完整复制整个表达式树的所有节点（包括父节点、兄弟节点等全量结构）
• 返回调用该方法的原节点对应的副本实例
• 支持通过副本节点的parent属性回溯到整个树的根节点副本

示例使用场景：

Expression rightRightCopy = originalExpression.right.right.copyFull();
Expression originalExpressionCopy = rightRightCopy.parent.parent; // 可正确获取根节点副本

解决方案实现 #

通过以下步骤完成：

1. 定位原节点所在树的根节点
2. 深度复制整个树，同时维护原节点与副本节点的映射关系
3. 根据映射关系返回当前调用节点的副本

具体代码实现：

import java.util.HashMap;
import java.util.Map;

public class Expression {
    // 原有类成员和方法保持不变...

    public Expression copyFull() {
        // 1. 找到原树的根节点
        Expression originalRoot = this;
        while (originalRoot.parent != null) {
            originalRoot = originalRoot.parent;
        }

        // 2. 复制整个树并建立原节点到副本的映射
        Map<Expression, Expression> nodeMap = new HashMap<>();
        copyEntireTree(originalRoot, nodeMap);

        // 3. 返回当前节点对应的副本
        return nodeMap.get(this);
    }

    // 辅助方法：递归复制整个树，同时填充映射表
    private Expression copyEntireTree(Expression originalNode, Map<Expression, Expression> nodeMap) {
        if (originalNode == null) {
            return null;
        }

        // 先创建当前节点的副本（暂不设置parent，避免递归循环）
        Expression copiedNode = new Expression(null, originalNode.middle, null);
        nodeMap.put(originalNode, copiedNode);

        // 递归复制左右子节点
        Expression copiedLeft = copyEntireTree(originalNode.left, nodeMap);
        Expression copiedRight = copyEntireTree(originalNode.right, nodeMap);

        // 通过set方法自动维护子节点与父节点的关联
        copiedNode.setLeft(copiedLeft);
        copiedNode.setRight(copiedRight);

        return copiedNode;
    }
}

代码说明 #

• 根节点定位：通过遍历parent属性找到整个树的根，确保复制的是完整的树结构
• 节点映射表：用HashMap存储原节点到副本的对应关系，确保每个节点仅复制一次，同时可快速定位当前节点的副本
• 递归复制逻辑：先创建节点副本，再递归复制子节点，最后通过类自带的setLeft/setRight方法自动维护父节点关联，避免手动设置parent导致的循环问题

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