主观题二叉树先序遍历pta

### 二叉树先序遍历主观题及练习题 #### 题目描述 以二叉链表作为二叉树的存储结构，输入二叉树的先序序列，要求输出以下内容： 1. 二叉树的中序遍历序列。 2. 二叉树的叶子结点个数。 #### 输入格式 输入为一个字符串，表示二叉树的先序遍历序列。若字符为`#`，则表示该节点为空；否则，字符为相应节点的数据元素。 #### 输出格式 输出两行： 1. 第一行是二叉树的中序遍历序列。 2. 第二行是二叉树的叶子结点个数。 #### 示例 **输入样例：** ``` ABC##DE#G##F### ``` **输出样例：** ``` CBEDGF 4 ``` --- #### 解决方案 ##### 数据结构定义 为了实现二叉树的构建与遍历，可以定义如下的二叉树节点结构[^3]： ```c typedef struct BiTNode { char data; // 节点数据 struct BiTNode* lchild; // 左子树指针 struct BiTNode* rchild; // 右子树指针 } BiTNode, *BiTree; ``` ##### 构建二叉树函数 通过递归方式构建二叉树，代码如下： ```c void CreateBiTree(BiTree* T) { char ch; scanf("%c", &ch); if (ch == '#') { *T = NULL; // 空树 } else { *T = (BiTNode*)malloc(sizeof(BiTNode)); // 创建新节点 (*T)->data = ch; CreateBiTree(&((*T)->lchild)); // 递归创建左子树 CreateBiTree(&((*T)->rchild)); // 递归创建右子树 } } ``` ##### 中序遍历函数 通过递归实现二叉树的中序遍历，代码如下： ```c void InOrderTraverse(BiTree T) { if (T != NULL) { InOrderTraverse(T->lchild); // 遍历左子树 printf("%c", T->data); // 访问根节点 InOrderTraverse(T->rchild); // 遍历右子树 } } ``` ##### 统计叶子节点个数函数 通过递归统计二叉树的叶子节点个数，代码如下： ```c int CountLeaves(BiTree T) { if (T == NULL) { return 0; // 空树没有叶子节点 } else if (T->lchild == NULL && T->rchild == NULL) { return 1; // 当前节点为叶子节点 } else { return CountLeaves(T->lchild) + CountLeaves(T->rchild); // 递归统计左右子树的叶子节点 } } ``` ##### 主函数 将上述函数整合到主函数中，代码如下： ```c #include <stdio.h> #include <stdlib.h> typedef struct BiTNode { char data; struct BiTNode* lchild; struct BiTNode* rchild; } BiTNode, *BiTree; void CreateBiTree(BiTree* T) { char ch; scanf("%c", &ch); if (ch == '#') { *T = NULL; } else { *T = (BiTNode*)malloc(sizeof(BiTNode)); (*T)->data = ch; CreateBiTree(&((*T)->lchild)); CreateBiTree(&((*T)->rchild)); } } void InOrderTraverse(BiTree T) { if (T != NULL) { InOrderTraverse(T->lchild); printf("%c", T->data); InOrderTraverse(T->rchild); } } int CountLeaves(BiTree T) { if (T == NULL) { return 0; } else if (T->lchild == NULL && T->rchild == NULL) { return 1; } else { return CountLeaves(T->lchild) + CountLeaves(T->rchild); } } int main() { BiTree T = NULL; CreateBiTree(&T); // 构建二叉树 InOrderTraverse(T); // 输出中序遍历序列 printf("\n"); printf("%d\n", CountLeaves(T)); // 输出叶子节点个数 return 0; } ``` --- #### 测试结果 对于输入样例`ABC##DE#G##F###`，程序输出为： ``` CBEDGF 4 ``` ---