c++ - 二叉搜索树 - 复制树

Question

我正在用 C++ 对数据结构进行排序，所以我正在编写一堆函数来制作二叉搜索树类。尝试创建复制构造函数/函数来复制树时，我有点迷茫。

void BST<T>::copyBST(Node* treeOriginal, Node* treeNew){

        if (treeOriginal == NULL) //base case to end recursion when at tree end
            treeNew == NULL;
        else{
            Node* treeNew = new Node;  //create the node and set the new key to original
            treeNew->key = treeOriginal->key;

            Node* leftChild = new Node; //create a left node to be child of new node
            treeNew->left = leftChild;
            leftChild->parent = treeNew;

            Node* rightChild = new Node; //create a right node
            treeNew->right = rightChild;
            rightChild->parent = treeNew;

            copyBST(treeOriginal->left, leftChild); //call copy function on subtree of left child
            copyBST(treeOriginal->right, rightChild); //call copy function on subtree of right child
        } 
}

现在，当我尝试运行它时会发生一些事情。首先，它不会复制所有的节点，每次都会复制不同的数量。这对我来说很奇怪，因为我在每个节点上调用递归，因为我从根开始，然后在左侧和右侧调用它。我试着在纸上写下这个过程，从视觉上规划它如何复制原始树，但对我来说这似乎是一个合乎逻辑的过程，找不到它可能丢失的地方。

我还在函数中添加了cout语句，打印出原节点的key、address、parent、children，以及复制节点的key、address、parent、children。我在这个测试中发现的唯一问题是复制节点的父地址总是 00000000，或者 NULL。显然这段代码

leftChild->parent = treeNew; and rightChild->parent = treeNew;

实际上并没有将节点的父指针设置为父节点。

这些是我在尝试解决此问题时发现的唯一明确问题。我不确定如何寻找问题。如果在代码逻辑上看不出任何问题，请问有没有人有其他想法如何找到问题所在？

谢谢!

Answer 1

treeNew 的声明创建了一个按值调用参数。这意味着调用者永远不会看到对此变量的更改。您必须将其设为引用参数，以便可以修改调用者的指针。那么递归复制子树就很简单了:

void BST<T>::copyBST(Node* treeOriginal, Node *parent, Node*& treeNew){

    if (treeOriginal == NULL) //base case to end recursion when at tree end
        treeNew == NULL;
    else{
        Node* treeNew = new Node;  //create the node and set the new key to original
        treeNew->key = treeOriginal->key;
        treeNew->parent = parent;

        // Just call recursively to copy the subtrees:
        copyBST(treeOriginal->left, treeNew, treeNew->left);
        copyBST(treeOriginal->right, treeNew, treeNew->right);
    } 
}

注意添加到第二个参数类型的&。一个更常见的习惯用法是使用函数返回值:

Node* BST<T>::copyOf(Node* treeOriginal, Node *parent){

    if (treeOriginal == NULL) //base case to end recursion when at tree end
        return NULL;

    //create the node and set the new key to original
    Node* treeNew = new Node;
    treeNew->key = treeOriginal->key;
    treeNew->parent = parent;

    // Just call recursively to copy the subtrees:
    treeNew->left = copyOf(treeOriginal->left, treeNew);
    treeNew->right = copyOf(treeOriginal->right, treeNew);

    return treeNew;
}