生成并遍历二叉树？

Question

生成并遍历二叉树。
请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。
测试：
输入：ABC**DE*G**F***

Answer 1

C++代码如下：

#include<iostream>

#include<string>

using namespace std;

struct TreeNode { // 二叉树结构

    char val;

    TreeNode *left, *right;

    TreeNode(char ch) : val(ch), left(nullptr), right(nullptr) {}

};

// 由扩展前序序列生成二叉树

TreeNode* construct(string& s, int& i) { // 注意传入的i为引用

    if (i == s.length())

        return nullptr;

    TreeNode *root = nullptr;

    if (s[i] != '*') {

        root = new TreeNode(s[i]);

        ++i;

        root->left = construct(s, i);

        ++i;

        root->right = construct(s, i);

    }

    return root;

}

void preOrder(TreeNode* root) { // 前序遍历

    if (root) {        

        cout << root->val;

        preOrder(root->left);

        preOrder(root->right);

    }

}

void inOrder(TreeNode* root) { // 中序遍历

    if (root) {

        inOrder(root->left);

        cout << root->val;

        inOrder(root->right);

    }

}

void postOrder(TreeNode* root) { // 后序遍历

    if (root) {

        postOrder(root->left);

        postOrder(root->right);        

        cout << root->val;

    }

}

int main() {

    string s = "ABC**DE*G**F***";

    cout << "扩展前序序列为：" << s << endl;

    int i = 0;

    TreeNode* root = construct(s, i); // 生成该二叉树

    cout << "其前序遍历序列为：";

    preOrder(root);

    cout << endl;

    cout << "其中序遍历序列为：";

    inOrder(root);

    cout << endl;

    cout << "其后序遍历序列为：";

    postOrder(root);

    cout << endl;

    return 0;

}

编译通过，输出如下：

符合示例结果，望采纳~