题解 | #二叉树遍历#

数据结构原理题。首先考虑先序、中序两种遍历的定义，然后根据此运用指针解决本问题。

#include<bits/stdc++.h>
int pos;
std::string treeString;

using BiTNode = struct BiTNode {
    char data;
    struct BiTNode* lchild, *rchild;
    BiTNode(char c): data(c), lchild(nullptr), rchild(nullptr) {};
};

BiTNode* Create_Tree() {
    char c = treeString[pos++];
    if (c == '#') // 空结点
        return nullptr;
    auto* root = new BiTNode(c); // 实结点
    root->lchild = Create_Tree(); // 创建左子树
    root->rchild = Create_Tree(); // 创建右子树
    return root;
}
void Traverse(BiTNode* root) {
    if (!root)
        return; // 结点为空则退回上一级结点
    Traverse(root->lchild);// 遍历左子树
    std::cout << root->data << " "; // 遍历完左子树后，输出这个子树的根结点
    Traverse(root->rchild);// 遍历右子树
}
int main() {
    while (std::cin >> treeString) {
        pos = 0;
        BiTNode* root = Create_Tree();
        Traverse(root);
        std::cout << std::endl;
    }
}