如何实现LinkedBinaryTree克隆：Position正确插入新树的问题

嘿，我来帮你搞定这个二叉树克隆的难题！你现在的问题在于，仅靠中序遍历的节点列表没法重建原树的结构——毕竟同一个中序序列可能对应N种不同的二叉树，而且你还没处理节点间的父子、左右关系。下面给你一套可行的方案：

第一步：修正Node的克隆逻辑 #

super.clone()是浅拷贝，会把原节点的parent、left、right引用也复制过来，这些引用指向的是原树的节点，完全不是我们想要的。所以得在克隆Node时重置这些引用，避免和原树产生关联：

protected static class Node<E> implements Position<E>, Cloneable {
    private E element;
    private Node<E> parent;
    private Node<E> left;
    private Node<E> right;

    // 你的构造器、getter/setter方法这里省略

    @Override
    public Position<E> clone() {
        try {
            Node<E> clonedNode = (Node<E>) super.clone();
            // 重置所有关联引用，避免指向原树节点
            clonedNode.parent = null;
            clonedNode.left = null;
            clonedNode.right = null;
            
            // 重要提醒：如果E是可变对象（比如自定义的类），这里需要做深拷贝
            // 比如：clonedNode.element = deepCopy(this.element);
            // 否则原树和克隆树的element会共享同一个对象，修改一方会影响另一方
            return clonedNode;
        } catch (CloneNotSupportedException e) {
            throw new RuntimeException("克隆节点失败", e);
        }
    }
}

第二步：递归克隆整个树结构 #

我们需要遍历原树的每个节点，克隆后立刻在新树中建立对应的父子、左右关系。可以写一个辅助递归方法来干这件事：

// 辅助方法：递归克隆指定节点及其子树，返回新树中对应的节点
private Node<E> cloneSubtree(Position<E> originalPos, LinkedBinaryTree<E> clonedTree, Node<E> clonedParent) {
    if (originalPos == null) {
        return null;
    }
    Node<E> originalNode = (Node<E>) originalPos;
    // 克隆当前节点
    Node<E> clonedNode = (Node<E>) originalNode.clone();
    // 设置当前克隆节点的父节点
    clonedNode.parent = clonedParent;
    // 递归克隆左子树，并绑定为当前节点的左孩子
    Node<E> clonedLeft = cloneSubtree(originalNode.left, clonedTree, clonedNode);
    clonedNode.left = clonedLeft;
    // 递归克隆右子树，并绑定为当前节点的右孩子
    Node<E> clonedRight = cloneSubtree(originalNode.right, clonedTree, clonedNode);
    clonedNode.right = clonedRight;
    // 如果是根节点，设置新树的根
    if (clonedParent == null) {
        clonedTree.root = clonedNode;
    }
    // 更新新树的节点计数（假设你的LinkedBinaryTree有size成员变量）
    clonedTree.size++;
    return clonedNode;
}

第三步：实现LinkedBinaryTree的clone方法 #

现在只需要调用上面的辅助方法，就能完整克隆整个树了：

@Override
public LinkedBinaryTree<E> clone() throws CloneNotSupportedException {
    LinkedBinaryTree<E> clonedTree = new LinkedBinaryTree<>();
    if (!isEmpty()) {
        // 从根节点开始递归克隆整个树
        cloneSubtree(root(), clonedTree, null);
    }
    return clonedTree;
}

额外注意事项 #

• 如果你的LinkedBinaryTree没有root和size成员变量，需要根据你自己的类结构调整代码（比如用你自己的方法设置根、维护节点数量）。
• 对于可变类型的E，一定要实现深拷贝逻辑，否则克隆树和原树会共享同一个元素对象，导致意料之外的修改。

内容的提问来源于stack exchange，提问作者M.Soyturk