序： 构造出一棵二叉树的方法有很多，基于*序拓展序列也可以构造出亦可唯一的一棵二叉树，本文给出基于后序拓展序列生成二叉树（基于链表实现）。
何谓后续拓展序列？ 后续拓展序列指在二叉树的后续遍历序列中增加空节点的序号。
Input
一行字符，即扩展后序序列Output
输出对应的前序遍历结果思路： 通过栈来实现。 从字符串头开始，如果是空节点进栈，否则就是非空节点，将最后两个提出，与该节点建立关系（根左右），再将该节点入栈。走完整个字符串，最后整棵二叉树便建成了。
原因： 由于加入了空序号，那么这棵二叉树是一棵完全二叉树。那么后续序列一定严格满足左右根的顺序，并且在同一级。
源代码：
/* About: binary tree-postorder Auther: kongse_qi Date:2017/03/15 */ #include <iostream> #include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> using namespace std; const int maxn = 10005; typedef struct qi_{ char x; struct qi_ *left, *right; }qi;//二叉树的组成 char a[maxn]; qi *x[maxn]; int end; inline qi *build(char a)//建树 { qi *curr = (qi*)malloc(sizeof(qi)); curr -> x = a; curr -> left = NULL; curr -> right = NULL; return curr; } inline qi* to(qi* a, qi* b, qi* c)//标记出关系 { c -> left = a; c -> right = b; return c; } void search(qi* curr)//输出 { if(curr -> x != '.') cout << curr->x; if(curr -> left != NULL) search(curr -> left); if(curr -> right != NULL) search(curr -> right); return ; } int main() { //freopen("test.in", "r", stdin); scanf("%s", a); for(int i = 0; i != strlen(a); ++i) { if(isalpha(a[i])) { x[end++] = build(a[i]); x[end-3] = to(x[end-3],x[end-2], x[end-1]); end = end-2; } else x[end++] = build('.'); } search(x[end-1]); return 0; }拓展： 求某节点与根节点的距离： 只需要将输出函数修改一下：
void search(qi* curr) { ++ans;//向下一层 if(curr -> x == xx) cout << ans-1, exit(0);//xx即询问的节点 if(curr -> left != NULL) search(curr -> left); if(curr -> right != NULL) search(curr -> right); --ans;//返回上一层 return ; }备注： 链表建树会比直接使用数组要慢。用数组分别存左右孩子的节点，思路与链表相同，只是写法稍有区别，故不给出代码。
自此完成。 箜瑟_qi 2017.04.13 21:22
