现在的位置: 首页 > 综合 > 正文

算法之二叉树中序前序序列(或后序)求解树

2017年05月28日 ⁄ 综合 ⁄ 共 447字 ⁄ 字号 评论关闭

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

<1>已知二叉树的前序序列和中序序列,求解树。

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

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

边和右边都为空,则根节点已经为叶子节点。

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

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

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

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

边和右边都为空,则根节点已经为叶子节点。

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

抱歉!评论已关闭.