C++中如何通过前序遍历复制二叉搜索树？代码报错求助

段错误原因 #

• 空指针解引用：代码中刚用new (nothrow) TNode分配内存，立刻将tempTree赋值为nullptr，后续访问tempTree->element时直接操作空指针，触发段错误。
• 逻辑判断完全错误：用else if(Tree->left != NULL)作为处理当前节点的条件，违背前序遍历“根→左→右”的核心逻辑，会漏掉所有无左子树的节点，同时逻辑顺序混乱。
• 错误销毁节点：函数末尾delete tempTree会直接销毁刚创建的节点，导致新树无法保留任何节点，还可能引发内存释放的未定义行为。
• 未建立树结构：代码完全没有将新创建的节点连接到目标树的root或父节点指针，最终新树始终为空，无法构建正确的二叉树结构。

正确的前序遍历复制实现 #

拷贝构造函数 #

#include <iostream>
using namespace std;

BST::BST(const BST &obj) : root{nullptr}
{
    copy(obj.root);
}

私有copy函数（前序遍历实现） #

方案一：借助insert保证BST合法性（简洁高效）

利用类的insert方法，按前序遍历顺序复制每个节点，确保新树是合法的BST：

void BST::copy(const TNodePtr Tree)
{
    if (Tree == nullptr) {
        return; // 空节点直接终止递归
    }

    // 前序第一步：复制当前节点（插入到新树）
    insert(Tree->element);

    // 前序第二步：递归复制左子树
    copy(Tree->left);

    // 前序第三步：递归复制右子树
    copy(Tree->right);
}

方案二：严格复制源树结构

若需要新树与源树结构完全一致，可通过BST性质查找父节点并连接新节点：

void BST::copy(const TNodePtr Tree)
{
    if (Tree == nullptr) {
        return;
    }

    // 创建当前节点的副本
    TNodePtr newNode = new (nothrow) TNode;
    if (!newNode) {
        cerr << "内存分配失败" << endl;
        return;
    }
    newNode->element = Tree->element;
    newNode->left = nullptr;
    newNode->right = nullptr;

    // 若当前是根节点，直接赋值
    if (!root) {
        root = newNode;
    } else {
        // 根据BST性质查找父节点，连接新节点
        TNodePtr curr = root;
        while (true) {
            if (Tree->element < curr->element) {
                if (!curr->left) {
                    curr->left = newNode;
                    break;
                }
                curr = curr->left;
            } else {
                if (!curr->right) {
                    curr->right = newNode;
                    break;
                }
                curr = curr->right;
            }
        }
    }

    // 递归复制左、右子树
    copy(Tree->left);
    copy(Tree->right);
}

补充说明 #

• 方案一简单高效，能保证新树是合法的BST，但树的结构可能与源树不完全一致（insert按值的大小插入）。
• 方案二严格复制源树的结构，确保新树与源树的节点连接关系完全相同。

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