以结构体数组作为二叉树的存储结构,求二叉树的叶子结点个数。 输入格式: 输入二叉树的先序序列。 提示:一棵二叉树的先序序列是一个字符串,若字符是‘#’,表示该二叉树是空树,否则该字符是相应结点的数据元素。 输出格式: 输出有两行: 第一行是二叉树的中序遍历序列; 第二行是二叉树的叶子结点个数。
时间: 2023-06-10 15:04:23 浏览: 55
N’,表示该结点为空;否则,表示该结点的值。每个结点之间用空格分隔。例如,先序序列为“ABD N N CEH I N N F G N N”,表示的二叉树如下:
A
/ \
B C
/ / \
D E H
/ \
I F
/
G
输出格式:输出二叉树的叶子结点个数,即只有左右子树都为空的结点个数。 示例: 输入:"ABD N N CEH I N N F G N N" 输出:5
解释: 上述示例中,只有D、I、G三个结点左右子树都为空,所以叶子结点个数为3。
相关问题
请用c++语言写代码,题目是以结构体数组作为二叉树的存储结构,求二叉树的叶子结点个数。 输入格式: 输入二叉树的先序序列。 提示:一棵二叉树的先序序列是一个字符串,若字符是‘#’,表示该二叉树是空树,否则该字符是相应结点的数据元素。 输出格式: 输出有两行: 第一行是二叉树的中序遍历序列; 第二行是二叉树的叶子结点个数。
C语言代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
char data;
struct TreeNode *lchild; // 左子树指针
struct TreeNode *rchild; // 右子树指针
} TreeNode, *pTreeNode;
pTreeNode createNode(char data) {
// 创建一个新的节点
pTreeNode newNode = (pTreeNode)malloc(sizeof(TreeNode));
newNode->data = data;
newNode->lchild = NULL;
newNode->rchild = NULL;
return newNode;
}
pTreeNode createTree(char *str, int *index) {
// 根据先序序列创建一颗二叉树
if (str[*index] == '\0') {
return NULL;
}
if (str[*index] != '#') {
pTreeNode newNode = createNode(str[*index]);
(*index)++;
newNode->lchild = createTree(str, index);
(*index)++;
newNode->rchild = createTree(str, index);
return newNode;
} else {
(*index)++;
return NULL;
}
}
int countLeaf(pTreeNode root) {
// 二叉树叶子结点计数
int count = 0;
if (root == NULL) {
return 0;
}
if (root->lchild == NULL && root->rchild == NULL) {
return 1;
}
count += countLeaf(root->lchild);
count += countLeaf(root->rchild);
return count;
}
int main() {
char str[100];
int index = 0;
printf("请输入二叉树的先序序列:");
scanf("%s", str);
pTreeNode root = createTree(str, &index);
int leafNum = countLeaf(root);
printf("叶子结点个数为:%d\n", leafNum);
return 0;
}
C语言:先序遍历序列建立一个二叉树的二叉链表,统计二叉树中叶子结点个数和二叉树的深度
下面是用C语言实现先序遍历序列建立二叉树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树的结构体
typedef struct TreeNode {
char data; // 数据域
struct TreeNode* leftChild; // 左子树指针
struct TreeNode* rightChild; // 右子树指针
} TreeNode;
// 先序遍历序列建立二叉树
TreeNode* buildTree() {
char c;
scanf("%c", &c);
if (c == '#') {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = c;
root->leftChild = buildTree();
root->rightChild = buildTree();
return root;
}
// 统计二叉树中叶子结点个数
int countLeaves(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->leftChild == NULL && root->rightChild == NULL) {
return 1;
}
return countLeaves(root->leftChild) + countLeaves(root->rightChild);
}
// 计算二叉树的深度
int calcDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = calcDepth(root->leftChild);
int rightDepth = calcDepth(root->rightChild);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main() {
printf("请输入先序遍历序列:");
TreeNode* root = buildTree();
printf("二叉树叶子结点个数:%d\n", countLeaves(root));
printf("二叉树的深度:%d\n", calcDepth(root));
return 0;
}
```
这里采用了递归的方式实现了先序遍历序列建立二叉树、统计二叉树中叶子结点个数和计算二叉树的深度。其中,函数`countLeaves()`用于统计二叉树中叶子结点个数,函数`calcDepth()`用于计算二叉树的深度。
运行结果如下:
```
请输入先序遍历序列:AB#D##CE###
二叉树叶子结点个数:3
二叉树的深度:3
```