C语言完整代码用二叉链表作为存储结构,建立下图的二叉树。并完成;(1)打印出该树的先序、中序和后序遍历序列;(2)统计叶子结点的个数;(3)打印所有叶子结点;(4)求该二叉树的深度;
时间: 2024-11-30 17:15:07 浏览: 28
在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* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (newNode != NULL) {
newNode->val = val;
newNode->left = newNode->right = NULL;
}
return newNode;
}
// 插入节点到二叉树
void insertNode(TreeNode** root, int val) {
if (*root == NULL) {
*root = createNode(val);
} else {
if (val < (*root)->val) {
insertNode(&((*root)->left), val);
} else {
insertNode(&((*root)->right), val);
}
}
}
// 打印先序遍历
void preOrderTraversal(TreeNode* node) {
if (node != NULL) {
printf("%d ", node->val); // 先访问根节点
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
}
// 中序遍历
void inOrderTraversal(TreeNode* node) {
if (node != NULL) {
inOrderTraversal(node->left);
printf("%d ", node->val); // 然后访问左节点
inOrderTraversal(node->right);
}
}
// 后序遍历
void postOrderTraversal(TreeNode* node) {
if (node != NULL) {
postOrderTraversal(node->left);
postOrderTraversal(node->right);
printf("%d ", node->val); // 最后访问右节点
}
}
// 统计叶子节点
int countLeaves(TreeNode* node) {
if (node == NULL) return 0;
if (node->left == NULL && node->right == NULL) return 1; // 如果左右子节点都为空,则是叶子节点
return countLeaves(node->left) + countLeaves(node->right);
}
// 打印所有叶子节点
void printLeaves(TreeNode* node) {
if (node == NULL) return;
if (node->left == NULL && node->right == NULL) printf("%d ", node->val);
printLeaves(node->left);
printLeaves(node->right);
}
// 求树的深度
int treeDepth(TreeNode* node) {
if (node == NULL) return 0;
int leftDepth = treeDepth(node->left);
int rightDepth = treeDepth(node->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
int main() {
// 初始化二叉树示例数据
TreeNode* root = NULL;
insertNode(&root, 5);
insertNode(&root, 3);
insertNode(&root, 7);
insertNode(&root, 2);
insertNode(&root, 4);
insertNode(&root, 6);
insertNode(&root, 8);
// 遍历和统计
printf("Preorder traversal: ");
preOrderTraversal(root);
printf("\nInorder traversal: ");
inOrderTraversal(root);
printf("\nPostorder traversal: ");
postOrderTraversal(root);
printf("\nNumber of leaves: %d\n", countLeaves(root));
printf("Leaf nodes: ");
printLeaves(root);
printf("\nTree depth: %d\n", treeDepth(root));
return 0;
}
```
这个示例展示了如何使用C语言构建二叉树以及完成题目所给的所有任务。你需要替换`insertNode(&root, ...)`部分的代码来生成你想要的特定二叉树结构。
阅读全文