根据后序序列构建二叉树并输出其前序序列

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef struct TreeNode *Tree; //定义了一个叫做TreeNode的结构体指针 *Tree 
 4 typedef char ElementType;
 5 
 6 struct TreeNode{
 7     char val;
 8     Tree left;
 9     Tree right;
10 };
11 stack<char>sta;
12 Tree Creat()
13 {
14     char c = sta.top();
15     sta.pop();
16     Tree T = (Tree)malloc(sizeof(struct TreeNode)); //创建新结点T 
17     if(c=='.')T = NULL;
18     else
19     {   //右左根？ 
20         T->right = Creat(); 
21         T->left = Creat();
22         T->val = c;
23     }
24     return T; //返回头节点T
25 }
26 void xx(Tree &t)
27 {
28     cout<<t->val;
29     if(t->left)xx(t->left);
30     if(t->right)xx(t->right);
31 }
32 int main()
33 {
34     string s;
35     cin>>s;
36     for(int i=0;i<s.length();i++)
37         sta.push(s[i]); //用栈存储二叉树结点，可以实现从后往前遍历 
38     Tree T = Creat(); //后序构造二叉树 
39     xx(T); //先序遍历 
40      return 0;
41 }