题解 | #二叉树遍历#

#include <cstdio>
#include <iostream>

using namespace std;

struct Treenode{
	char data;
	Treenode* lchild;
	Treenode* rchild;
};

void Func(const string &s, int *i, Treenode *T){
	if(s[*i] == '#' || *i >= s.size()){
		T->data = -1;
		(*i)++;
		return;
	}else{
		T->data = s[*i];
		T->lchild = (Treenode*)malloc(sizeof(Treenode));
		(*i)++;
		Func(s, i, T->lchild);
		T->rchild = (Treenode*)malloc(sizeof(Treenode));
		Func(s, i, T->rchild);
	}
}

void InOrder(Treenode *T, int &tag){//tag记录是否输出过 
	if(T->data == -1){
		return;
	}
	InOrder(T->lchild, tag);
	if(!tag){
		tag = 1;
	}else{
		printf(" ");
	}
	printf("%c",T->data);
	InOrder(T->rchild, tag);
}

int main(){
	string s;
	while(cin >> s){
		int i = 0;
		Treenode *T = (Treenode*)malloc(sizeof(Treenode));
		Func(s, &i, T);
		int tag = 0;
		InOrder(T, tag);
		printf("\n");
		delete T;
	}
	return 0;
}