当前位置:首页 > 数据结构 > 二叉树 > 正文
SSOJ2464扩展二叉树
400+

题目大意:给出二叉树的先序遍历,输出二叉树的中序遍历和后序遍历。

题目描述

由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树,所以对二叉树做如下处理,将二叉树的空结点用“·”补齐,如下图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树,扩展二叉树的先序和后序序列能唯一确定其二叉树。

现给出扩展二叉树的先序序列,要求输出其中序和后序序列。

样例输入

ABD..EF..G..C..

样例输出

DBFEGAC
DFGEBCA

解题思路

先序遍历,先建立根节点(父亲结点),建立子树(儿子结点)。如果不是空结点“.”,那么必定有左右儿子(左右子树)。

中序遍历,先输出左儿子,再输出自己,最后输出右儿子。

后续遍历:先输出左儿子,再输出右儿子,最后输出自己。

程序实现

以上是堆结构存储的二叉树,下面是用结构体链表存储二叉树。

更多

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2464扩展二叉树:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter