题解 | #二叉树遍历#

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

struct TreeNode{
    char data;
    TreeNode * leftchild;
    TreeNode * rightchild;
    TreeNode(char c) : data(c), leftchild(NULL), rightchild(NULL){}
};

TreeNode* Build(int& position, string str){   //建立树
    char c = str[position++]; //当前字符
    if(c == '#') return NULL; //返回空树
    TreeNode* root = new TreeNode(c);  //创建新结点
    root -> leftchild = Build(position, str);  //创建左子树
    root -> rightchild = Build(position, str);  //创建右子树
    return root;
}

void InOrder(TreeNode* root){  //中序遍历
    if(root != NULL){
        InOrder(root->leftchild);
        printf("%c ", root->data);
        InOrder(root->rightchild);
    }
}

int main(){
    string str;
    while(cin >> str){
        int position = 0;  //标记字符串处理位置
        TreeNode* root = Build(position, str);
        InOrder(root);
        printf("\n");
    }
    return 0;
}