1340：【例3-5】扩展二叉树
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。
现给出扩展二叉树的先序序列，要求输出其中序和后序序列。
【输入】
扩展二叉树的先序序列。
【输出】
输出其中序和后序序列。
【输入样例】
ABD..EF..G..C..
【输出样例】
DBFEGAC
DFGEBCA
1. #include <iostream> 2. #include <cstdio> 3. #include <cstring> 4. #include <algorithm> 5. using namespace std; 6. struct node{ 7. char data; 8. int left,right; 9. }t[1000]; 10. int num=1; 11. void build(int root){ 12. char ch; 13. cin>>ch; 14. if(ch!='.'){ 15. t[root].data=ch; 16. t[root].left=++num; 17. build(t[root].left); 18. t[root].right=++num; 19. build(t[root].right); 20. } 21. } 22. void inorder(int root){ 23. if(t[root].data==0) return; 24. inorder(t[root].left); 25. cout<<t[root].data; 26. inorder(t[root].right); 27. } 28. void postorder(int root){ 29. if(t[root].data==0) return; 30. postorder(t[root].left); 31. postorder(t[root].right); 32. cout<<t[root].data; 33. } 34. int main() 35. { 36. build(1); 37. inorder(1); 38. cout<<endl; 39. postorder(1); 40. return 0; 41. }
