PTA——数和二叉树

7-10 建立与遍历二叉树

以字符串的形式定义一棵二叉树的先序序列，若字符是‘#’, 表示该二叉树是空树，否则该字符是相应结点的数据元素。读入相应先序序列，建立二叉链式存储结构的二叉树，然后中序遍历该二叉树并输出结点数据。

输入格式:

字符串形式的先序序列（即结点的数据类型为单个字符）

输出格式:

中序遍历结果

输入样例:

在这里给出一组输入。例如：

ABC##DE#G##F###

输出样例:

在这里给出相应的输出。例如：

CBEGDFA

#include<iostream>
#include<string>
using namespace std;
const int N = 10001001;
//结构体的定义
struct TreeNode {
    char data;
    TreeNode* left, * right;
    TreeNode(char val) :data(val), left(nullptr), right(nullptr) {}//初始化
};
//数的建立
TreeNode* BuildTree(const string& T, int& i) {
    if (i >= T.length()) {
        return nullptr;
    }
    char val = T[i++];
    if (val == '#') {
        return nullptr;
    }
    TreeNode* root = new TreeNode(val);
    root->left = BuildTree(T, i);
    root->right = BuildTree(T, i);
    return root;
}
//中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    cout << root->data ;
    inorderTraversal(root->right);
}
int main() {
    string T;
    cin >> T;
    int i = 0;
    TreeNode* root = BuildTree(T, i);
    inorderTraversal(root);
    return 0;
}



/*TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}是C++中的构造函数的定义。这段代码表示了TreeNode结构体的构造函数，用于初始化TreeNode对象的数据成员。

具体来说：

char val是构造函数的参数，表示要传入的节点数据值。
data(val)表示将构造函数参数val赋值给TreeNode对象的data成员，即节点的数据值。
left(nullptr)表示将左子节点初始化为nullptr，表示刚创建的节点暂时没有左子节点。
right(nullptr)表示将右子节点初始化为nullptr，表示刚创建的节点暂时没有右子节点。*/