C语言用递归算法复制二叉树T为一颗新二叉树, 采用二叉链表存储结构
时间: 2024-11-11 21:02:40 浏览: 16
在C语言中,递归算法用于复制二叉树通常涉及到深度优先搜索(Depth First Search,DFS),这里我们假设二叉树节点结构包含左孩子、右孩子和值的指针。下面是一个基本的递归函数示例,它会创建一个新的节点并链接到原树的相应位置:
```c
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左孩子指针
struct TreeNode* right; // 右孩子指针
} TreeNode;
// 创建一个新的树节点
TreeNode* createNode(int val) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 递归复制二叉树
TreeNode* copyTreeRecursively(TreeNode* root) {
if (root == NULL) { // 如果根节点为空,则返回空
return NULL;
}
// 创建新节点并赋值
TreeNode* newRoot = createNode(root->val);
// 递归地复制左右子树,并链接新节点
newRoot->left = copyTreeRecursively(root->left);
newRoot->right = copyTreeRecursively(root->right);
return newRoot;
}
```
这个`copyTreeRecursively`函数首先检查当前节点是否为空,如果为空则直接返回NULL。然后,它创建一个新节点,设置其值为原始节点的值,接着递归地复制左子树和右子树,并将它们链接到新节点上。
阅读全文