c++ - 按顺序复制二叉树

Question

到目前为止我写的代码是:

void copyInOrder(TNode *orgTree, Tnode *& copyTree){
    if(orgTree !=NULL){
        copyInOrder(orgTree->left_link);
        //create leftmost node of tree but how to link to parent
        copyInOrder(orgTree->right_link);
    }
}

我不知道如何按照其顺序链接到节点的父节点。

Answer 1

假设 orgTree 指向根 (2)。对于复制，我们必须执行以下操作:

1. 在copyTree上创建一个节点，并将值2复制到其中
2. 如果 orgTree->left != NULL，调用 copyInOrder( orgTree->left, copyTree->left );
3. 如果 orgTree->right != NULL，调用 copyInOrder( orgTree->right, copyTree->right );

顺便说一句，这种类型的遍历称为 pre-order traversal ，中序遍历是不同的。