编程克隆浇树怎么做

时间:2025-01-27 11:50:29 网络游戏

克隆二叉树通常采用递归的方法,具体步骤如下:

基本情况:

如果当前节点为空,则返回空节点。

递归情况:

如果当前节点不为空,则创建一个新的节点,并将当前节点的值复制到新节点中。然后递归地克隆左子树和右子树,并将它们分别赋值给新节点的左子节点和右子节点。

```cpp

include

// 定义二叉树节点结构体

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

// 深度克隆二叉树的函数

TreeNode* cloneTree(TreeNode* root) {

if (root == NULL) {

return NULL;

}

// 创建新节点,并将当前节点的值复制到新节点中

TreeNode* newRoot = new TreeNode(root->val);

// 递归克隆左子树和右子树

newRoot->left = cloneTree(root->left);

newRoot->right = cloneTree(root->right);

return newRoot;

}

// 辅助函数:中序遍历打印二叉树(用于验证克隆结果)

void inorderTraversal(TreeNode* root) {

if (root == NULL) {

return;

}

inorderTraversal(root->left);

std::cout << root->val << " ";

inorderTraversal(root->right);

}

int main() {

// 创建一个示例二叉树

TreeNode* root = new TreeNode(1);

root->left = new TreeNode(2);

root->right = new TreeNode(3);

root->left->left = new TreeNode(4);

root->left->right = new TreeNode(5);

// 克隆二叉树

TreeNode* clonedRoot = cloneTree(root);

// 打印原始树和克隆树的中序遍历结果

std::cout << "Original tree inorder traversal: ";

inorderTraversal(root);

std::cout << std::endl;

std::cout << "Cloned tree inorder traversal: ";

inorderTraversal(clonedRoot);

std::cout << std::endl;

return 0;

}

```

代码解释:

TreeNode结构体:

定义了二叉树节点的结构,包括节点的值`val`,左子节点`left`和右子节点`right`。

cloneTree函数:

递归地克隆二叉树。如果当前节点为空,返回空节点;否则,创建一个新节点,并将当前节点的值复制到新节点中,然后递归克隆左子树和右子树。

inorderTraversal函数:

中序遍历二叉树,用于验证克隆结果是否正确。

main函数:

创建一个示例二叉树,调用`cloneTree`函数进行克隆,并打印原始树和克隆树的中序遍历结果。

通过这种方式,可以确保每个节点都被正确克隆,并且父子节点的指针关系得以保留。