c语言实现复制二叉树
时间: 2023-11-18 11:52:17 浏览: 35
复制二叉树的C语言实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* cloneTree(struct TreeNode* root) {
if (root == NULL) {
return NULL;
}
struct TreeNode* newRoot = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newRoot->val = root->val;
newRoot->left = cloneTree(root->left);
newRoot->right = cloneTree(root->right);
return newRoot;
}
```
相关问题
C语言复制二叉树
复制二叉树可以采用递归的方式,对每个节点进行复制,并递归复制其左右子树。以下是一个用 C 语言实现的例子:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 复制二叉树
TreeNode* copyTree(TreeNode* root) {
if (root == NULL) {
return NULL;
}
TreeNode* new_root = (TreeNode*)malloc(sizeof(TreeNode));
new_root->val = root->val;
new_root->left = copyTree(root->left);
new_root->right = copyTree(root->right);
return new_root;
}
// 中序遍历二叉树
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
int main() {
// 创建二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 3;
root->left->left = NULL;
root->left->right = NULL;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 4;
root->right->right = NULL;
root->right->left->left = NULL;
root->right->left->right = NULL;
// 复制二叉树
TreeNode* new_root = copyTree(root);
// 中序遍历原二叉树和复制后的二叉树
printf("Original tree: ");
inorderTraversal(root);
printf("\n");
printf("Copied tree: ");
inorderTraversal(new_root);
printf("\n");
return 0;
}
```
输出结果为:
```
Original tree: 2 1 4 3
Copied tree: 2 1 4 3
```
可以看到,复制后的二叉树与原二叉树结构相同,并且输出的中序遍历结果也相同。
c语言代码实现二叉树的以下功能。二叉树的创建、二叉树的三种递归遍历 二叉树的复制、统汁二叉树的结点数
以下是C语言代码实现二叉树的相关功能:
1. 二叉树的创建
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree();
root->right = createTree();
return root;
}
```
2. 二叉树的三种递归遍历
```c
void preorder(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preorder(root->left);
preorder(root->right);
}
void inorder(TreeNode *root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
void postorder(TreeNode *root) {
if (root == NULL) {
return;
}
postorder(root->left);
postorder(root->right);
printf("%d ", root->val);
}
```
3. 二叉树的复制
```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;
}
```
4. 统计二叉树的结点数
```c
int countNodes(TreeNode *root) {
if (root == NULL) {
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
```