最新消息:点击查看大S的省钱秘笈

已知二叉树的中序序列和前序序列(或后序)求解树

编程相关 Slyar 165浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

今天数据结构课讲树的存储和遍历,老师讲的很简单,也没什么代码要发...唯一看到一个比较重要的东西,总结一下算法好了。

这种题一般有二种形式,共同点是都已知中序序列。如果没有中序序列,是无法唯一确定一棵树的,证明略。

一、已知二叉树的前序序列和中序序列,求解树。

1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。

2、求解树的子树。找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点。

3、递归求解树。将左子树和右子树分别看成一棵二叉树,重复1、2、3步,直到所有的节点完成定位。

二、已知二叉树的后序序列和中序序列,求解树。

1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。

2、求解树的子树。找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点。

3、递归求解树。将左子树和右子树分别看成一棵二叉树,重复1、2、3步,直到所有的节点完成定位。

举例说明:根据已知求解二叉树

中序序列 BDCEAFHG
后序序列 DECBHGFA

1、BDCEAFHG在后序序列中最后出现的元素为A,BDCE|A|FHG
2、BDCE在后序序列中最后出现的元素为B,|B|DCE|A|FHG
3、FHG在后序序列中最后出现的元素为F,|B|DCE|A||F|HG
4、DCE在后序序列中最后出现的元素为C,|B|D|C|E|A||F|HG
5、HG在后序序列中最后出现的元素为G,|B|D|C|E|A||F|H|G|
6、所有元素都已经定位,二叉树求解完成。

以前还写过一篇文章《求二叉树的后序遍历 C语言 数组实现》,是已知二叉树的前序遍历和后序遍历,求二叉树的后序遍历。

转载请注明:Slyar Home » 已知二叉树的中序序列和前序序列(或后序)求解树

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (5)

  1. @xmach 奇怪了,我很早以前就改了啊,难道回档了?...谢谢哈
    Slyar7年前 (2009-10-28)回复
  2. 好像有点小错: 一、已知二叉树的前序序列和中序序列,求解树。 1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。 2、求解树的子树。找出根节点在“前”序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。............ 以上应该是找出根结点在“中”序遍历中的位置吧
    xmach7年前 (2009-10-28)回复
  3. 前天腾(和谐)讯笔试题目的选择题,嗯。
    Felix0218年前 (2009-05-18)回复
  4. 记得有个多叉树走迷宫的经典例子... 居然没个例子养眼诶...
    苏洋8年前 (2009-05-13)回复
  5. 好久不见更新阿。。。来膜拜一下,嗯。月底去上海玩儿吧。。东华的比赛。。
    Felix0218年前 (2009-05-12)回复