按照先序建立二叉树即可,然后再按照中序输出。
#include<iostream>
using namespace std;
typedef struct node{
char val;
struct node *left,*right;
}*TreeNode,Node;
void build(TreeNode &root,string &str){
char c = str[0];
str = str.substr(1);
if(c == '#')
return;
if(root == NULL){
root = (TreeNode)malloc(sizeof(Node));
root->val = c;
root->left = NULL;
root->right = NULL;
}
build(root->left,str);
build(root->right,str);
}
void mid(TreeNode root){
if(root == NULL)
return;
mid(root->left);
cout << root->val << " ";
mid(root->right);
}
int main()
{
string str;
while(cin >> str){
TreeNode root = NULL;
build(root,str);
mid(root);
cout << endl;
}
}