SSOJ2464扩展二叉树
2541+
作者：crxis 发布：2017-07-03 分类：二叉树
题目大意：给出二叉树的先序遍历，输出二叉树的中序遍历和后序遍历。
题目描述
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用“·”补齐，如下图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。
现给出扩展二叉树的先序序列，要求输出其中序和后序序列。
样例输入
ABD..EF..G..C..
样例输出
DBFEGAC
DFGEBCA
解题思路
先序遍历，先建立根节点（父亲结点），建立子树（儿子结点）。如果不是空结点“.”，那么必定有左右儿子（左右子树）。
中序遍历，先输出左儿子，再输出自己，最后输出右儿子。
后续遍历：先输出左儿子，再输出右儿子，最后输出自己。
程序实现
以上是堆结构存储的二叉树，下面是用结构体链表存储二叉树。
