题解 | #二叉树遍历#

//要点：1.二叉树的结构（可以先写好构造函数）
//     2.先序构造二叉树，为空直接返回，如果没有构造函数，需要malloc并赋值，然后递归到左右子树
//     3.中序遍历输出二叉树
#include <iostream>
#include<string>
using namespace std;
struct Bitnode
{
    char data;
    Bitnode*lchild;
    Bitnode*rchild;
    Bitnode(char c):data(c),lchild(NULL),rchild(NULL){};//构造函数
};
Bitnode* createTree(string s,int &pos)
{
    Bitnode* T;
    char c=s[pos++];
    if(c=='#')return NULL;
    else
    {
        //T未初始化，也可以直接Bitnode*T=new Bitnode(c);
        T=(Bitnode*)malloc(sizeof(Bitnode));
        T->data=c;
        T->lchild=createTree(s,pos);
        T->rchild=createTree(s,pos);
        return T;
    }
}
void inorder(Bitnode*T)
{
    if(!T)return;
    inorder(T->lchild);
    printf("%c ",T->data);
    inorder(T->rchild);
}
int main() {
    string s;
    while (cin >> s) { // 注意 while 处理多个 case
        int pos=0;
        Bitnode*T=createTree(s,pos);
        inorder(T);

    }
    return 0;
}
// 64 位输出请用 printf("%lld")