c语言假设以二叉链作为存储结构,设计一个算法复制一棵二叉树。用相关数据进行测试。
时间: 2024-11-25 07:11:27 浏览: 13
数据结构实验报告-实现二叉树的基本操作-用顺序存储和链式存储结构
5星 · 资源好评率100%
在C语言中,复制一棵二叉树可以使用递归的方式来实现。假设我们有一个二叉链表节点定义如下:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
复制二叉树的算法步骤如下:
1. 创建一个新的`TreeNode`实例,用于存放新复制的节点值。
2. 如果原节点为空,则返回新节点。
3. 对于原节点的左孩子和右孩子分别进行递归复制操作。
4. 将复制得到的新节点设置为当前节点的左右孩子。
下面是一个简单的函数实现示例:
```c
TreeNode* copyTree(TreeNode* root) {
if (root == NULL) {
return NULL;
}
// 新建一个节点并赋值
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = root->val;
newNode->left = copyTree(root->left);
newNode->right = copyTree(root->right);
return newNode;
}
```
为了测试这个功能,你可以创建一些二叉树的数据结构,例如:
```c
// 测试数据
TreeNode* originalRoot = createTestTree(); // 创建一个有特定结构的测试二叉树
// 复制二叉树
TreeNode* copiedRoot = copyTree(originalRoot);
// 验证复制结果
compareTrees(originalRoot, copiedRoot); // 比较原始树和复制树是否一致
// 释放内存
free(originalRoot);
free(copiedRoot);
```
其中`createTestTree()` 和 `compareTrees()` 是辅助函数,用于构建测试树和比较两个树是否相等。
阅读全文