按先序次序建立一棵二叉树,输入时,以井号表示空指针。对其进行后序遍历,并统计叶子结点的个数。
时间: 2024-06-03 11:12:18 浏览: 3
建立二叉树的步骤如下:
1. 读入一个字符ch;
2. 若ch为'#',则令p指向空指针;
3. 若ch为其他字符,动态生成一个新的结点,并将ch存入其中;
4. 递归读入左子树;
5. 递归读入右子树。
后序遍历二叉树的步骤如下:
1. 若当前结点非空,则先递归遍历其左子树;
2. 再递归遍历其右子树;
3. 最后访问该结点。
统计叶子结点的个数的步骤如下:
1. 若当前结点为空,则返回0;
2. 若当前结点为叶子结点,则返回1;
3. 否则,递归计算其左子树和右子树的叶子结点个数之和。
完整代码如下:
相关问题
按先序次序建立一棵二叉树,输入时,以井号表示空指针。对其进行后序遍历,并统计叶子结点的个数。 c语言代码
以下是按先序次序建立一棵二叉树,后序遍历并统计叶子节点个数的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 按先序次序建立二叉树
TreeNode* createTree() {
char ch;
scanf("%c", &ch);
if (ch == '#') {
return NULL;
}
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = ch;
node->left = createTree();
node->right = createTree();
return node;
}
// 后序遍历并统计叶子节点个数
int postOrder(TreeNode *root, int *count) {
if (!root) {
return 0;
}
int left = postOrder(root->left, count);
int right = postOrder(root->right, count);
if (!root->left && !root->right) {
(*count)++;
}
printf("%c ", root->val);
return left + right + 1;
}
int main() {
TreeNode *root = createTree();
int count = 0;
printf("后序遍历:");
postOrder(root, &count);
printf("\n叶子节点个数:%d\n", count);
return 0;
}
```
输入样例:
```
AB##C##D##
```
输出样例:
```
后序遍历:BCDA
叶子节点个数:2
```
按先序次序建立一棵二叉树,输入时,以井号表示空指针。对其进行后序遍历,并统计叶子的个数
输入样例:
A B D # # E # # C # #
输出样例:
D E B C A
3
二叉树的结构体定义如下:
```c++
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
```
可以使用递归的方式进行后序遍历,并在遍历时统计叶子结点的个数。
C++ 代码如下:
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)