假设以二叉链作为存储结构,设计一个算法复制一棵二叉树用c语言
时间: 2024-12-11 22:43:04 浏览: 13
在C语言中,如果你想要使用二叉链表作为存储结构来复制一棵二叉树,可以按照递归的方式来实现。这里是一个简单的算法描述:
首先定义二叉链表节点的结构体:
```c
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左孩子指针
struct TreeNode* right; // 右孩子指针
} TreeNode;
```
然后实现复制函数`copyTree`:
```c
TreeNode* copyTree(TreeNode* root) {
if (root == NULL) { // 如果根节点为空,返回空
return NULL;
}
// 创建一个新的节点,并复制旧节点的值
TreeNode* newRoot = (TreeNode*)malloc(sizeof(TreeNode));
newRoot->val = root->val;
// 递归地复制左子树和右子树
newRoot->left = copyTree(root->left);
newRoot->right = copyTree(root->right);
return newRoot;
}
```
这个函数的工作原理是检查当前节点是否为空,如果为空则直接返回NULL。否则,创建一个新的节点,复制原始节点的值,然后递归地复制左右子树。
使用这个函数时,只需调用`copyTree`并传入原二叉树的根节点即可得到新的复制树。注意,这里的复制会创建新的内存空间,因此对于大量数据的树,需要考虑内存管理。
阅读全文