当前课程知识点：数据结构 > 第5章 树和二叉树 > 5.4 二叉树的遍历及创建 > 讲解（下）
接着，我们来看二叉树的中序遍历及后序遍历
二叉树的中序遍历是这样的
先以中序访问根的左子树
然后去访问根，再以中序访问根的右子树
根是放在左右子树中间访问的
所以叫中序遍历
在初始情况下，T
是指向树的根结点
我们先要去访问树的左子树(根为+)
再以中序访问+的左子树(根为a)，再以中序访问a的左子树
这时候是空，a的左子树访问完了，访问a
所以，中序遍历得到的第一个结点是a
然后再以中序遍历a的右子树
a的右子树也是空
现在
a这棵子树已经遍历完了
它作为+的左子树遍历完了
这时候，应该去访问+
第二个结点是+
然后，再以中序遍历+的右子树(根为*)，再以中序遍历*的左子树(根为b)
再以中序遍历b的左子树
这时候是空
然后去访问b
然后，再以中序访问b的右子树，为空
现在，b这棵子树也访问完了
回到*
遍历它
然后，再以中序遍历*的右子树
后面的过程，我就不说了
现在，我们来看它对应的算法
终结条件跟前面的先序遍历是一样的
都是T指向的树为空树的时候，返回
打印T指向的结点的信息
这行语句，出现在了2个递归中间
递归访问左、右子树中间
这是与前面先序遍历它的算法不同的地方
我们再来看后序遍历，后序遍历
是先以后序访问树的左子树，再以后序访问数的右子树
最后去访问根
根是放在最后访问的
所以叫后序遍历
类似地，T一开始指向-
先以后序访问左子树+
再以后序访问左子树a
再以后序访问
a的左子树，为空，左子树访问完了
注意，再访问右子树
a的右子树也为空
这时候，才去访问a
所以，后序遍历得到的第一个结点，也是a
虽然跟中序遍历一样
但是这二者的细节是不一样的
+的左子树a访问完了
再以后序访问+的右子树，再以后序访问*的左子树，再以后序访问b的左子树，为空，再以后序访问b的右子树，也为空
然后才到b，第二个是b
b这棵子树访问完了
它作为*的左子树
紧接着，应该去访问*的右子树，注意，还是要以后序访问
然后，再以后序访问-的左子树
c的左子树，c的右子树
然后再到c
所以，第三个是c
c这棵子树访问完了
再以后序访问-的右子树
然后，d的左子树，d的右子树
然后再到d，c、d作为-的左、右子树访问完了
再回到-
所以，下一个是-
后面的过程，我就不详细往下说了
我们来看它的算法，也很简单
打印T指向的结点的数据域，这行语句是放在了2个递归的后面
我们发现，在后序遍历当中，得到的最后一个结点
它是树的根
这个原因很简单
因为，后序遍历，根始终是放在最后访问的
所以，最后一个结点
是树的根
在学习了树的先序、中序、后序遍历之后
我们来看一道题，给定两种遍历序列
如何确定该二叉树
比如，给定的是中序和后序
是否能把这个二叉树确定下来呢
我们来看后序
我们知道，后序遍历
最后一个得到的结点，应该是整棵树的根结点
现在我们能确定，根结点就是-
那么，根结点
它的左子树，又包含哪些结点呢
我们回到中序遍历
根结点-它左边，一定是树的左子树
因为根据中序遍历，先左
再根、再右
根结点
它的左边，一定是树的左子树
说明，A+B
*C，这5个结点是在左子树里面的
如何确定左子树具体的情况呢
我们再回到后序遍历
A+B*C
在后序遍历当中，是这样的
同样，左子树最后一个被访问的结点，是左子树的根
所以，左子树的根是+，那+的左子树又是多少呢
再回到中序遍历，+的左边
只有A
所以，左子树就一个结点A
那+的右子树呢
我们看+的右边，是B*C
再回到后序遍历，B*C
在后序遍历当中，是BC*
那么，*是右子树的根
所以，右子树的根是*
再回到中序遍历，B*C，被*这样一分
所以，*的左子树应该是B，右子树呢
应该是C
这样，我们就把整棵树
它的根的左子树，确定下来了
那么，右子树如何确定呢
根据刚才类似的思想
一样可以确定
现在，我们再来思考一个问题
给定任意2种遍历系列，是否都能唯一确定该二叉树呢
比如，我们给定
先序和后序，或者给定先序和中序，是不是也能把二叉树确定下来呢
这个问题，留给大家当作课下的作业
现在，我们来看二叉树的创建算法
我们采用的算法思想
跟遍历差不多
在遍历的过程当中，逐个把结点创建出来
并且形成结点之间的左孩子、右孩子
这种父子关系
以输入先序序列
创建二叉树为例
创建算法名字叫create
T前面有引用参数，说明我们要在创建的过程当中，去修改这个参数
这里读入一个字符
作为当前创建结点的信息
如果读入的这个字符，是我们约定的一个特殊字符
比如，我们用#来标识那些不存在的结点
也就是为空的孩子
如果它等于标记为空的字符
那么，这时候的T
我们应该修改成NULL
表示是一棵空树
else，我们就进入递归
开始去创建结点，malloc
每次申请一个BinTreeNode类型的结点
把ch赋值给T的数据域
然后开始递归，创建它的左右子树
我们是先创建出来T
然后创建T的左右子树
很明显
将来输入的字符序列，应该是先序
对于这个例子来说
我们要创建7个结点的二叉树
一共要输入8个用来表示空树的#字符
这个算法才能结束
为什么呢
原因很简单
我们刚才已经说了，具有n个结点的二叉链表
它实际上是有n+1个空指针的
为了让这个算法能够结束
我们必须输入足够多的、用来表示空指针的特殊字符#
比如，这棵二叉树
一共要补8个
把那些不存在的孩子，都把它补出来
补了8个空的指针，这个算法才能结束
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
