带父节点的二叉树C++拷贝构造函数实现及段错误问题求助

看起来你遇到的段错误，核心原因是处理父指针时的循环递归/空指针访问，或者错误地直接复用了原树的父节点指针。下面我会一步步给你拆解问题，然后给出正确的实现方案。

问题根源分析 #

你之前的实现大概率犯了这两个错误之一：

• 直接把原节点的parent指针赋值给新节点，导致新树和原树共享父节点，后续操作可能访问已释放的内存或者非法地址；
• 尝试递归拷贝父节点，引发无限递归（比如原节点的父节点又指向它的祖先，递归会一直循环下去，最终栈溢出触发段错误）。

正确的思路应该是从根节点向下递归拷贝，在拷贝子节点时直接把父指针设置为新创建的上层节点，完全不反向处理父节点的拷贝。

完整实现代码 #

首先补充Node类的拷贝构造函数声明：

class Node { 
public: 
    int value;
    Node(); 
    Node(int v); 
    // 拷贝构造函数声明
    Node(const Node& other);
    // 记得添加析构函数避免内存泄漏
    ~Node();

    Node * left; 
    Node * right; 
    Node * parent; 
}; 

然后实现辅助递归函数和拷贝构造函数：

// 辅助递归函数：拷贝单个节点，并设置其父子关系
Node* copyNode(const Node* original, Node* parentNode) {
    if (!original) { // 处理空指针，避免访问非法内存
        return nullptr;
    }
    // 创建新节点，拷贝原节点的值
    Node* newNode = new Node(original->value);
    // 设置新节点的父指针为传入的上层节点
    newNode->parent = parentNode;
    // 递归拷贝左子树，左子树的父节点就是当前新节点
    newNode->left = copyNode(original->left, newNode);
    // 递归拷贝右子树，同理
    newNode->right = copyNode(original->right, newNode);
    return newNode;
}

// 拷贝构造函数实现
Node::Node(const Node& other) {
    // 拷贝当前节点的值
    value = other.value;
    // 根节点的父指针默认是nullptr
    parent = nullptr;
    // 递归拷贝左子树，把当前节点作为左子树的父节点传入
    left = copyNode(other.left, this);
    // 递归拷贝右子树，同理
    right = copyNode(other.right, this);
}

// 析构函数：递归释放子节点内存，避免泄漏
Node::~Node() {
    if (left) {
        delete left;
        left = nullptr;
    }
    if (right) {
        delete right;
        right = nullptr;
    }
    // 父节点不需要手动释放，因为它由上层节点管理
}

关键细节说明 #

1. 辅助函数的作用：
   辅助函数额外接收一个parentNode参数，用来在创建子节点时直接指定它的父节点，完美避免了反向递归父节点的问题，同时保证新树的父子关系完全独立于原树。

2. 空指针处理：
   每次递归前先判断原节点是否为nullptr，这能有效避免访问空指针导致的段错误。

3. 避免循环引用：
   我们只从根节点向下递归拷贝左右子树，完全不处理父节点的反向拷贝，从根源上杜绝了循环递归的可能。

4. 内存管理：
   一定要实现析构函数递归释放子节点的内存，否则会造成严重的内存泄漏。

测试示例 #

你可以用下面的代码测试拷贝功能：

int main() {
    // 创建原树
    Node* root = new Node(1);
    root->left = new Node(2);
    root->left->parent = root;
    root->right = new Node(3);
    root->right->parent = root;

    // 拷贝构造新树
    Node* copiedRoot = new Node(*root);

    // 验证拷贝结果：修改原树节点值，新树不受影响
    root->value = 100;
    cout << "原树根节点值：" << root->value << endl; // 输出100
    cout << "拷贝树根节点值：" << copiedRoot->value << endl; // 输出1

    // 验证父子关系
    cout << "拷贝树左子节点的父节点值：" << copiedRoot->left->parent->value << endl; // 输出1

    // 释放内存
    delete root;
    delete copiedRoot;
    return 0;
}

内容的提问来源于stack exchange，提问作者abc-cba