中序和后序确定二叉树 已知一棵二叉树的前序序列和中序序列分别是ABCDEFGHIJ和BAEDCHGIFJ，构造二叉树，并写出其后序序列？

已知一棵二叉树的前序序列和中序序列分别是ABCDEFGHIJ和BAEDCHGIFJ，构造二叉树，并写出其后序序列？

这是一个递归算法。

第一个预排序必须是根，根是a

从预排序中，我们可以分离左右子树：B和edchgifj，它们是预排序

从预排序中，我们可以分离左右子树：B和cdefghij，它们是预排序。

这样的问题变成了两个同样的小问题，递归就解决不了了。

首先要明确前序、中序、后序的遍历顺序：前序：父节点、左子节点、右子节点；中序：左子节点、父节点、右子节点；后序：左子节点、右子节点、父节点；后序：左子节点、右子节点、右子节点；后序：左子节点、右子节点；后序：左子节点节点，右子节点；首先根据前序遍历，确定整棵二叉树的根节点（前序的第一个节点）；然后通过中间序遍历，将整棵二叉树按根节点直接划分为两个子树。

此时，按照预序和中间序一步一步地绘制整个二叉树并不困难。然后我们可以编写后序遍历序列。例如：已知二叉树的前序遍历序列为bc D E F H，中序遍历序列为bd C E a H F，写后序遍历序列。根据预排序，树的根节点是a；根据中间顺序和根节点，B、D、C、E在根节点的左子树上，H、F在根节点的右子树上；通过对每个子树的逐步分析，树是a/b f/C H/De后一个顺序是：decbhfa

要通过分段来解决问题，先找到根节点（通过后一个顺序），然后将中间顺序的序列分成两段，左子树和右子树，然后递归地，在分割时，您可以使用中间顺序的左右子树的节点数来确定序列中每个段的节点数。

例如，middle bdace

post dbeca1，在本例中，它是一个

2。中间顺序对应的根是a，所以a是根，BD是左子树，CE是右子树

3。左子树上有两个节点，右子树上有两个节点，因为后一个顺序的遍历是先左后右，所以后一个顺序被分成两段，左dB和右EC

4。因此，确定左子树的根是B，右子树的根是C

5如果节点和节点数是递归确定的，则右子树是e

上面得到的结果

二叉树的结构图

---a

-/-]---B---C

---

---D---e

是ABCDE

中序和后序确定二叉树 二叉树前序中序后序代码 知道前序和中序求后序

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。