二叉树序列口诀 数据结构中已知前序序列和中序序列，怎么得出后序序列？

数据结构中已知前序序列和中序序列，怎么得出后序序列？

一般可以先恢复二叉树，然后再进行后序遍历得到后序序列。恢复过程如下：首先，前序序列中的第一个是根。得到中间顺序后，中间顺序可分为三部分：左子树的中间顺序、根和右子树的中间顺序。然后，左子树的中间阶和右子树的中间阶可以返回到前序序列，这些子树的中间阶可以在序序列中分成三部分，子树的根仍然在第一位。再回到子树的中间顺序进行剪切，直到所有子树只有一个节点

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

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

二叉树序列口诀 中序序列和后序序列 前序序列中序序列后序序列

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