【数据结构】第二章 二叉树的遍历
由遍历序列构造二叉树
由先序序列和中序序列可以唯一确定一个二叉树。
后序序列+中序序列可以唯一确定一个二叉树。
层次序列+中序序列可以唯一确定一个二叉树。
例题1：已知先序序列：A B C D E F G H I . 中序序列： B C A E D G H F I
求该二叉树的后序遍历序列。
分析：
①根据先序序列，首先找到根节点 A ，可以将“ 先序” 一分为二。
② 根据先序序列，可知 B 为 左子树的跟结点，D 为右子树的跟结点
③根据先序序列，可知剩下的子树 FGHI 中，F 为根节点。
④ 根据先序序列，可知 G 为 根节点。
⑤ 所以最终二叉树已经显而易见，后序序列为
C B E H G I F D A
例题2：已知先序序列 ： 1 2 4 5 3 6 . 中序序列 ： 4 2 5 1 6 3
分析：
①先根据先序序列，首先找到根节点 1 .将整个树一分为二。
② 根据先序序列，可知 2 为 左子树的根，3 为右子树的根
③最终得到这颗唯一二叉树。后序序列为 ：4 5 2 6 3 1