编写算法建立一棵二叉树的二叉链表 输出二叉树的三种遍历序列 统计二叉树结点数 叶子数 深度 用c语言

### C语言实现二叉树的二叉链表存储结构及相关功能 以下是完整的C语言代码，用于实现二叉树的二叉链表存储结构，并完成前序、中序和后序遍历，统计结点总数、叶子结点数以及计算二叉树深度。 #### 定义二叉树节点结构 ```c #include <stdio.h> #include <stdlib> // 定义二叉树节点结构 typedef struct BiTreeNode { char data; struct BiTreeNode *lchild, *rchild; } BiTree; BiTree* CreateBiTree() { char ch; scanf(" %c", &ch); if (ch == '#') { // 如果输入'#'表示该位置为空 return NULL; } BiTree* node = (BiTree*)malloc(sizeof(BiTree)); node->data = ch; // 当前节点的数据 node->lchild = CreateBiTree(); // 递归创建左子树 node->rchild = CreateBiTree(); // 递归创建右子树 return node; } ``` #### 前序、中序和后序遍历函数 ```c void PreOrderTraversal(BiTree* root) { if (root != NULL) { printf("%c ", root->data); // 访问根节点 PreOrderTraversal(root->lchild); // 遍历左子树 PreOrderTraversal(root->rchild); // 遍历右子树 } } void InOrderTraversal(BiTree* root) { if (root != NULL) { InOrderTraversal(root->lchild); // 遍历左子树 printf("%c ", root->data); // 访问根节点 InOrderTraversal(root->rchild); // 遍历右子树 } } void PostOrderTraversal(BiTree* root) { if (root != NULL) { PostOrderTraversal(root->lchild); // 遍历左子树 PostOrderTraversal(root->rchild); // 遍历右子树 printf("%c ", root->data); // 访问根节点 } } ``` #### 统计结点总数、叶子结点数和计算深度 ```c int CountNodes(BiTree* root) { if (root == NULL) { return 0; } return CountNodes(root->lchild) + CountNodes(root->rchild) + 1; // 左子树结点数 + 右子树结点数 + 自身 } int CountLeaves(BiTree* root) { if (root == NULL) { return 0; } if (root->lchild == NULL && root->rchild == NULL) { // 判断是否为叶子节点 return 1; } return CountLeaves(root->lchild) + CountLeaves(root->rchild); // 左右子树叶子节点之和 } int TreeDepth(BiTree* root) { if (root == NULL) { return 0; } int leftDepth = TreeDepth(root->lchild); // 获取左子树深度 int rightDepth = TreeDepth(root->rchild); // 获取右子树深度 return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; // 返回较大者并加1 } ``` #### 主函数调用 ```c int main() { printf("请输入二叉树(按层次顺序输入，'#'表示空节点):\n"); BiTree* root = CreateBiTree(); printf("\n前序遍历序列: "); PreOrderTraversal(root); printf("\n中序遍历序列: "); InOrderTraversal(root); printf("\n后序遍历序列: "); PostOrderTraversal(root); printf("\n\n总结:\n"); printf("总节点数: %d\n", CountNodes(root)); // 输出总节点数 printf("叶子节点数: %d\n", CountLeaves(root)); // 输出叶子节点数 printf("二叉树深度: %d\n", TreeDepth(root)); // 输出二叉树深度 return 0; } ``` --- 以上代码实现了二叉树的二叉链表存储结构及其相关操作[^1]。通过`CreateBiTree()`函数可以方便地按照层次顺序输入一棵二叉树，而三个遍历函数则分别完成了前序、中序和后序遍历的任务。此外，还提供了统计结点总数、叶子结点数以及计算二叉树深度的功能[^2]。 ---