关于#c++#的问题：输入说明:按先序方式依次输入二叉树中各结点的值，注意:用#补齐空结点.输出说明:依次输出先序、中序、后序遍历序列（相关搜索：编写程序|二叉树的遍历|中序遍历）

Question

C++编写程序，实现对二叉树的遍历,
按先序序列建立二叉树的二叉链表(用#补齐空结点)，然后分别用三种递归方法:先序、中序和后序对二叉树进行遍历并输出遍历结果。
输入说明:按先序方式依次输入二叉树中各结点的值，注意:用#补齐空结点.输出说明:依次输出先序、中序、后序遍历序列。
输入样例1:
1240*56#07##30#输出样例1:
先序遍历序列:1245673中序遍历序列:4265713后序遍历序列:4675231
输入样例2:
ABC##DE#G##F###输出样例2:
先序遍历序列:ABCDEGF中序遍历序列:CBEGDFA后序遍历序列:CGEFDBA

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题分析： 本题需要实现对二叉树的遍历，按先序序列建立二叉树的二叉链表，然后分别用三种递归方法:先序、中序和后序对二叉树进行遍历并输出遍历结果。可以使用指针来实现二叉树。先序遍历的顺序是根->左->右，中序遍历的顺序是左->根->右，后序遍历的顺序是左->右->根。 解决方案：

1. 定义二叉树结点，包括指向左右孩子的指针和结点值。

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};

1. 根据先序遍历序列建立二叉树，按照先序遍历的顺序，如果当前结点值不为#，则建立新结点，并将其左右孩子指针初始化为nullptr，否则返回nullptr。递归调用建立左子树和右子树。最后返回根结点指针。

TreeNode* createTree() {
    char c;
    cin >> c;
    if (c == '#') return nullptr;
    auto root = new TreeNode(c);
    root->left = createTree();
    root->right = createTree();
    return root;
}

1. 先序遍历，按照先序遍历的顺序访问结点，并递归调用左子树和右子树的遍历。

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val;
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

1. 中序遍历，按照中序遍历的顺序递归调用左子树、访问结点、递归调用右子树。

void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    cout << root->val;
    inorderTraversal(root->right);
}

1. 后序遍历，按照后序遍历的顺序递归调用左子树、右子树、访问结点。

void postorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val;
}

1. 完整代码：

#include <iostream>
using namespace std;
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};
// 建立二叉树
TreeNode* createTree() {
    char c;
    cin >> c;
    if (c == '#') return nullptr;
    auto root = new TreeNode(c);
    root->left = createTree();
    root->right = createTree();
    return root;
}
// 先序遍历
void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val;
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    cout << root->val;
    inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    cout << root->val;
}
int main() {
    auto root = createTree();
    // 先序遍历
    cout << "先序遍历序列:";
    preorderTraversal(root);
    cout << endl;
    // 中序遍历
    cout << "中序遍历序列:";
    inorderTraversal(root);
    cout << endl;
    // 后序遍历
    cout << "后序遍历序列:";
    postorderTraversal(root);
    cout << endl;
    return 0;
}