求树的遍历算法,现在知道树（注意不是单指二叉树）的根节点和后序遍历,而且可以知道每一个结点的父结点,求前序遍历.例如：（图例）这只是一个例子,我求得是算法阿.

Question

求树的遍历算法,
现在知道树（注意不是单指二叉树）的根节点和后序遍历,而且可以知道每一个结点的父结点,求前序遍历.
例如：（图例）
这只是一个例子,我求得是算法阿.

Answer 1

使用孩子兄弟链表作为树的数据结构：每个结点有两个分支,左分支代表该结点的第一个孩子,右分支代表该结点的下一个兄弟.这样就可以将树转化为与二叉树类似的数据结构
该数据结构的C代码如下:
typedef struct CSNode {
ElemType data;
struct CSNode *firstchild,*nextsibling;
} CSNode,*CSTree;
容易证明,原树的先序遍历＝二叉树的先序遍历,原树的后序遍历＝二叉树的中序遍历
所以只要通过题目条件,建立起该树对应的二叉树,就很容易得到原树的先序遍历
按照如下的思路很容易建立对应二叉树：
将后序遍历序列反转,得到一个序列.
（很容易注意到,这个序列是一个从右向左的先序遍历）
以这个序列为模板,逐个考察该序列的元素
{若该元素没有父亲,
那么就是根结点；
若该元素的父亲的左指针为空,
（也就是说,它的父亲还没有挂孩子）
那么就把这个该元素挂到它父亲的左指针上暂时作为第一个孩子；
若该元素的父亲的左指针为另一个结点p,
（该元素与p有相同的父亲,但比p来得晚一些,这说明该元素比p更靠左）
那么
{把p挂到该元素的右指针上变成兄弟,把该元素挂到父亲的左指针上；}
}
这样一来,就得到了对应的二叉树
然后对二叉树做一个先序遍历,就得到了原树的先序遍历
我只提供一个思路,时间关系,具体代码我就不写了
相信这个对你来说只是举手之劳.