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

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++代码示例来实现这个功能：

#include <iostream>
#include <string>

using namespace std;

// 二叉树结点的定义
struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

// 利用先序序列递归创建二叉树
TreeNode* createTree(string& preorder, int& index) {
    if (index >= preorder.size() || preorder[index] == '#') {
        index++;
        return nullptr;
    }
    TreeNode* node = new TreeNode(preorder[index++]);
    node->left = createTree(preorder, index);
    node->right = createTree(preorder, index);
    return node;
}

// 先序遍历
void preorderTraversal(TreeNode* root, string& result) {
    if (root == nullptr) return;
    result += root->data;
    preorderTraversal(root->left, result);
    preorderTraversal(root->right, result);
}

// 中序遍历
void inorderTraversal(TreeNode* root, string& result) {
    if (root == nullptr) return;
    inorderTraversal(root->left, result);
    result += root->data;
    inorderTraversal(root->right, result);
}

// 后序遍历
void postorderTraversal(TreeNode* root, string& result) {
    if (root == nullptr) return;
    postorderTraversal(root->left, result);
    postorderTraversal(root->right, result);
    result += root->data;
}

// 计算叶子结点数
int countLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

int main() {
    string preorder;
    cin >> preorder;
    
    int index = 0;
    TreeNode* root = createTree(preorder, index);
    
    if (!root) {
        cout << "0" << endl;
        return 0;
    }
    
    string preOrderResult, inOrderResult, postOrderResult;
    preorderTraversal(root, preOrderResult);
    inorderTraversal(root, inOrderResult);
    postorderTraversal(root, postOrderResult);
    
    int leafCount = countLeaves(root);
    
    cout << preOrderResult << endl;
    cout << inOrderResult << endl;
    cout << postOrderResult << endl;
    cout << leafCount << endl;
    
    return 0;
}

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

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

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

跳转到最佳答案楼层

FishC

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

#include <iostream>
#include <string>

using namespace std;

// 二叉树结点的定义
struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

// 利用先序序列递归创建二叉树
TreeNode* createTree(string& preorder, int& index) {
    if (index >= preorder.size() || preorder[index] == '#') {
        index++;
        return nullptr;
    }
    TreeNode* node = new TreeNode(preorder[index++]);
    node->left = createTree(preorder, index);
    node->right = createTree(preorder, index);
    return node;
}

// 先序遍历
void preorderTraversal(TreeNode* root, string& result) {
    if (root == nullptr) return;
    result += root->data;
    preorderTraversal(root->left, result);
    preorderTraversal(root->right, result);
}

// 中序遍历
void inorderTraversal(TreeNode* root, string& result) {
    if (root == nullptr) return;
    inorderTraversal(root->left, result);
    result += root->data;
    inorderTraversal(root->right, result);
}

// 后序遍历
void postorderTraversal(TreeNode* root, string& result) {
    if (root == nullptr) return;
    postorderTraversal(root->left, result);
    postorderTraversal(root->right, result);
    result += root->data;
}

// 计算叶子结点数
int countLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

int main() {
    string preorder;
    cin >> preorder;
    
    int index = 0;
    TreeNode* root = createTree(preorder, index);
    
    if (!root) {
        cout << "0" << endl;
        return 0;
    }
    
    string preOrderResult, inOrderResult, postOrderResult;
    preorderTraversal(root, preOrderResult);
    inorderTraversal(root, inOrderResult);
    postorderTraversal(root, postOrderResult);
    
    int leafCount = countLeaves(root);
    
    cout << preOrderResult << endl;
    cout << inOrderResult << endl;
    cout << postOrderResult << endl;
    cout << leafCount << endl;
    
    return 0;
}

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

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

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