通用树（Generic Tree）节点删除函数实现问题求助

首先先修正你现有代码中的一个明显错误：addChildren方法里的parent = this;是错误的，这会把当前节点的父节点设置为自身，正确的写法应该是给传入的子节点设置父节点：

public void addChildren(Node<T> child) {
    child.setParent(this); // 修正此处
    listOfChildren.add(child);
}

接下来，针对你需要的“删除节点时子节点上移一级”的需求，根本不需要DFS或BFS遍历整棵树——因为每个节点都持有父节点引用和子节点列表，直接通过这些引用操作即可，这就是最优实现，时间复杂度是O(k)（k为被删除节点的子节点数量），完全不需要遍历无关节点。

实现方案 #

可以实现两种方法：一种是父节点主动删除指定子节点（完善你现有的removeChildAt），另一种是节点自身主动从树中删除。

1. 完善removeChildAt方法

修改后的方法会在删除子节点时，将该子节点的所有子节点转移到当前节点（即被删节点的父节点）的子列表中：

public void removeChildAt(int index) {
    if (index < 0 || index >= listOfChildren.size()) {
        throw new IndexOutOfBoundsException("索引超出范围");
    }
    Node<T> deletedNode = listOfChildren.remove(index);
    // 将被删节点的所有子节点转移到当前节点（父节点）下
    for (Node<T> child : deletedNode.getListOfChildren()) {
        child.setParent(this); // 更新子节点的父节点为当前节点
        this.listOfChildren.add(child);
    }
    // 清空被删节点的子列表（可选，避免后续意外引用）
    deletedNode.getListOfChildren().clear();
    // 解除被删节点与父节点的关联
    deletedNode.setParent(null);
}

2. 新增deleteSelf方法（节点主动删除自己）

如果需要让节点自己触发删除逻辑，可以添加这个方法，它会找到自己的父节点，然后完成转移子节点和删除自身的操作：

public void deleteSelf() {
    Node<T> parentNode = this.parent;
    if (parentNode == null) {
        throw new IllegalStateException("根节点无法删除");
    }
    // 从父节点的子列表中移除自己
    parentNode.getListOfChildren().remove(this);
    // 将自己的子节点转移到父节点下
    for (Node<T> child : this.getListOfChildren()) {
        child.setParent(parentNode);
        parentNode.getListOfChildren().add(child);
    }
    // 清空自身子列表并解除父节点关联
    this.getListOfChildren().clear();
    this.setParent(null);
}

为什么这是最优方式？ #

• 没有任何冗余遍历：只操作被删除节点、其父节点以及被删节点的直接子节点，完全不涉及树的其他部分。
• 时间复杂度仅为O(k)：k是被删除节点的子节点数量，这是理论上的最优复杂度，因为你必须处理每个子节点的父节点更新。
• 逻辑清晰直接：利用节点已有的parent引用和listOfChildren列表，不需要额外的数据结构或遍历算法。

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