[已解决]先序序列创建二叉树，输出先序序列、中序序列、后序序列并输出叶子结点数

yangzhixiaohuli

对于给定的二叉树，输出其先序序列、中序序列、后序序列并输出叶子结点数。

二叉树.png

输入格式:
二叉树的先序遍历序列。

提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。

输出格式:
若是非空二叉树，则输出四行内容 第一行是二叉树的先序遍历序列； 第二行是二叉树的中序遍历序列； 第三行是二叉树的后序遍历序列； 第四行是叶子结点数；

若是空二叉树 只需输出叶子数0

输入样例1:
FCA##DB###EHM###G##
输出样例1:
FCADBEHMG
ACBDFMHEG
ABDCMHGEF
4
输入样例2:
#
输出样例2:
0

这题用C或者C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-11-15 16:10:38

要解决这个问题，我们可以使用递归来构建二叉树，然后对生成的树进行先序、中序和后序遍历。此外，我们需要计算二叉树的叶子结点数。下面是一个简单的C++代码示例来实现这个功能：

1. #include <iostream>
   
2. #include <string>
   
3. 
   
4. using namespace std;
   
5. 
   
6. // 二叉树结点的定义
   
7. struct TreeNode {
   
8.     char data;
   
9.     TreeNode* left;
   
10.     TreeNode* right;
    
11.     TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
    
12. };
    
13. 
    
14. // 利用先序序列递归创建二叉树
    
15. TreeNode* createTree(string& preorder, int& index) {
    
16.     if (index >= preorder.size() || preorder[index] == '#') {
    
17.         index++;
    
18.         return nullptr;
    
19.     }
    
20.     TreeNode* node = new TreeNode(preorder[index++]);
    
21.     node->left = createTree(preorder, index);
    
22.     node->right = createTree(preorder, index);
    
23.     return node;
    
24. }
    
25. 
    
26. // 先序遍历
    
27. void preorderTraversal(TreeNode* root, string& result) {
    
28.     if (root == nullptr) return;
    
29.     result += root->data;
    
30.     preorderTraversal(root->left, result);
    
31.     preorderTraversal(root->right, result);
    
32. }
    
33. 
    
34. // 中序遍历
    
35. void inorderTraversal(TreeNode* root, string& result) {
    
36.     if (root == nullptr) return;
    
37.     inorderTraversal(root->left, result);
    
38.     result += root->data;
    
39.     inorderTraversal(root->right, result);
    
40. }
    
41. 
    
42. // 后序遍历
    
43. void postorderTraversal(TreeNode* root, string& result) {
    
44.     if (root == nullptr) return;
    
45.     postorderTraversal(root->left, result);
    
46.     postorderTraversal(root->right, result);
    
47.     result += root->data;
    
48. }
    
49. 
    
50. // 计算叶子结点数
    
51. int countLeaves(TreeNode* root) {
    
52.     if (root == nullptr) return 0;
    
53.     if (root->left == nullptr && root->right == nullptr) return 1;
    
54.     return countLeaves(root->left) + countLeaves(root->right);
    
55. }
    
56. 
    
57. int main() {
    
58.     string preorder;
    
59.     cin >> preorder;
    
60.    
    
61.     int index = 0;
    
62.     TreeNode* root = createTree(preorder, index);
    
63.    
    
64.     if (!root) {
    
65.         cout << "0" << endl;
    
66.         return 0;
    
67.     }
    
68.    
    
69.     string preOrderResult, inOrderResult, postOrderResult;
    
70.     preorderTraversal(root, preOrderResult);
    
71.     inorderTraversal(root, inOrderResult);
    
72.     postorderTraversal(root, postOrderResult);
    
73.    
    
74.     int leafCount = countLeaves(root);
    
75.    
    
76.     cout << preOrderResult << endl;
    
77.     cout << inOrderResult << endl;
    
78.     cout << postOrderResult << endl;
    
79.     cout << leafCount << endl;
    
80.    
    
81.     return 0;
    
82. }

复制代码

### 程序说明：
1. **`createTree`函数**：从给定的先序序列构建二叉树。
2. **遍历函数**：分别实现了先序、中序和后序遍历。
3. **`countLeaves`函数**：递归计算叶子结点的数量。
4. **`main`函数**：读取输入，构建树，进行遍历并输出结果。

在实际使用时，将样例输入传递给程序，它将按照要求输出二叉树的遍历结果和叶子结点数。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

要解决这个问题，我们可以使用递归来构建二叉树，然后对生成的树进行先序、中序和后序遍历。此外，我们需要计算二叉树的叶子结点数。下面是一个简单的C++代码示例来实现这个功能：

1. #include <iostream>
   
2. #include <string>
   
3. 
   
4. using namespace std;
   
5. 
   
6. // 二叉树结点的定义
   
7. struct TreeNode {
   
8.     char data;
   
9.     TreeNode* left;
   
10.     TreeNode* right;
    
11.     TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
    
12. };
    
13. 
    
14. // 利用先序序列递归创建二叉树
    
15. TreeNode* createTree(string& preorder, int& index) {
    
16.     if (index >= preorder.size() || preorder[index] == '#') {
    
17.         index++;
    
18.         return nullptr;
    
19.     }
    
20.     TreeNode* node = new TreeNode(preorder[index++]);
    
21.     node->left = createTree(preorder, index);
    
22.     node->right = createTree(preorder, index);
    
23.     return node;
    
24. }
    
25. 
    
26. // 先序遍历
    
27. void preorderTraversal(TreeNode* root, string& result) {
    
28.     if (root == nullptr) return;
    
29.     result += root->data;
    
30.     preorderTraversal(root->left, result);
    
31.     preorderTraversal(root->right, result);
    
32. }
    
33. 
    
34. // 中序遍历
    
35. void inorderTraversal(TreeNode* root, string& result) {
    
36.     if (root == nullptr) return;
    
37.     inorderTraversal(root->left, result);
    
38.     result += root->data;
    
39.     inorderTraversal(root->right, result);
    
40. }
    
41. 
    
42. // 后序遍历
    
43. void postorderTraversal(TreeNode* root, string& result) {
    
44.     if (root == nullptr) return;
    
45.     postorderTraversal(root->left, result);
    
46.     postorderTraversal(root->right, result);
    
47.     result += root->data;
    
48. }
    
49. 
    
50. // 计算叶子结点数
    
51. int countLeaves(TreeNode* root) {
    
52.     if (root == nullptr) return 0;
    
53.     if (root->left == nullptr && root->right == nullptr) return 1;
    
54.     return countLeaves(root->left) + countLeaves(root->right);
    
55. }
    
56. 
    
57. int main() {
    
58.     string preorder;
    
59.     cin >> preorder;
    
60.    
    
61.     int index = 0;
    
62.     TreeNode* root = createTree(preorder, index);
    
63.    
    
64.     if (!root) {
    
65.         cout << "0" << endl;
    
66.         return 0;
    
67.     }
    
68.    
    
69.     string preOrderResult, inOrderResult, postOrderResult;
    
70.     preorderTraversal(root, preOrderResult);
    
71.     inorderTraversal(root, inOrderResult);
    
72.     postorderTraversal(root, postOrderResult);
    
73.    
    
74.     int leafCount = countLeaves(root);
    
75.    
    
76.     cout << preOrderResult << endl;
    
77.     cout << inOrderResult << endl;
    
78.     cout << postOrderResult << endl;
    
79.     cout << leafCount << endl;
    
80.    
    
81.     return 0;
    
82. }

复制代码

### 程序说明：
1. **`createTree`函数**：从给定的先序序列构建二叉树。
2. **遍历函数**：分别实现了先序、中序和后序遍历。
3. **`countLeaves`函数**：递归计算叶子结点的数量。
4. **`main`函数**：读取输入，构建树，进行遍历并输出结果。

在实际使用时，将样例输入传递给程序，它将按照要求输出二叉树的遍历结果和叶子结点数。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。