创建一棵二叉树,计算二叉树结点个数、叶子结点个数、二叉树深度、复制二叉树并将其以前序遍历、中序遍历、后序遍历进行输出。c语言完整打出代码
时间: 2024-12-13 22:15:31 浏览: 10
在C语言中,创建二叉树、计算节点和叶子节点数量、深度以及遍历操作可以使用递归实现。下面是一个简单的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 计算节点数
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
// 判断是否是叶子节点
int isLeaf(TreeNode* node) {
return node->left == NULL && node->right == NULL;
}
// 计算深度
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
return 1 + MAX(maxDepth(root->left), maxDepth(root->right));
}
// 深拷贝二叉树
TreeNode* copyTree(TreeNode* root) {
if (root == NULL) return NULL;
return createNode(root->val)(copyTree(root->left))(copyTree(root->right));
}
// 遍历函数模板,填充实际遍历过程
void traverse(TreeNode* root, void (*visit)(int)) {
if (root != NULL) {
visit(root->val); // 先访问根节点
traverse(root->left, visit); // 再递归左子树
traverse(root->right, visit); // 最后递归右子树
}
}
// 前序遍历
void preOrderTraversal(TreeNode* root) {
printf("前序遍历: ");
traverse(root, printf("%d "));
}
// 中序遍历
void inOrderTraversal(TreeNode* root) {
printf("中序遍历: ");
traverse(root, printf("%d "));
}
// 后序遍历
void postOrderTraversal(TreeNode* root) {
printf("后序遍历: ");
traverse(root, printf("%d "));
}
int main() {
// 创建一个简单的二叉树作为示例
TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
// 输出相关信息
printf("节点总数: %d\n", countNodes(root));
printf("叶子节点数: %d\n", countNodes(findLeaves(root)));
printf("最大深度: %d\n", maxDepth(root));
// 打印复制后的二叉树
TreeNode* copyRoot = copyTree(root);
printf("\n复制后二叉树:\n");
preOrderTraversal(copyRoot);
inOrderTraversal(copyRoot);
postOrderTraversal(copyRoot);
return 0;
}
```
在这个代码片段中,`findLeaves` 函数需要你自己实现,因为题目没有包含这个部分。它应该遍历每个节点检查是否是叶子节点。注意,这个代码只是一个基础示例,实际应用中可能会有更复杂的情况,例如处理空指针、内存管理等。
阅读全文