c++ - 如何将二叉树附加到另一个

Question

我正在编写一个函数，该函数应该附加一个二叉树来替换另一棵树的节点。我将两棵树的根和我要替换的节点的标识符传递给函数，但我不确定如何交换指向我要删除的节点的指针的地址并将其设置为指向我要追加的树的根。

void Tree::appendTree(TreeNode *ptrMod, TreeNode *ptrApp, string 
type_node) {
    if (ptrMod == nullptr) {
        return;
    }
    if (ptrMod->getType() == type_node) {
        delete(ptrMod);
        ptrMod=ptrApp;
    } else {
        appendTree(*(ptrMod->getLeftAddress()),ptrApp,type_node);
        appendTree(*(ptrMod->getRightAddress()),ptrApp,type_node);
    }
}

ptrMod 指向我正在检查的节点，以检查它是否是我要替换的节点。 ptrApp 是我要追加的树的根。

Answer 1

需要做的更改很少:1. 添加一个返回值，以便您知道交换是否成功。 2. 在删除的子树上递归释放内存。

bool Tree::appendTree(TreeNode* & ptrMod, TreeNode* & ptrApp, string 
type_node) {
    if(ptrMod==nullptr)
    {
        return false; // did not swap
    }
    if(ptrMod->getType() == type_node){
        delete(ptrMod); // I hope you overloaded the delete operator to correctly delete all nodes of the tree
        ptrMod=ptrApp;
        return true; // swapped correctl;
        }
        else
        {
            if (appendTree(*(ptrMod->getLeftAddress()),ptrApp,type_node))
                return true;
            else return appendTree(*(ptrMod->getRightAddress()),ptrApp,type_node);
        }
}