当前课程知识点：数据结构 > 第5章 树和二叉树 > 5.4 二叉树的遍历及创建 > 讲解（上）
本节，我们来学习二叉树的遍历及创建
先来看遍历
所谓遍历
就是依照某种次序，将给定的数据结构当中所有的元素，访问且仅访问一次
我们前面打印一个线性表当中所有的元素，实际上就是一种最简单的遍历
二叉树有4种遍历方式
分别是先序遍历、中序遍历、后序遍历，以及层序遍历
我们先来看先序遍历，先序遍历
是先访问树的根结点
然后，去访问根结点的左子树L
再去访问根结点的右子树R
需要注意，在访问左右子树的时候，必须以相同的序去访问
也就是说
对于先序遍历来说
在访问完根结点之后
还得以先序去访问它的左子树
再以先序访问它的右子树，我们后面会详细地讲到
现在，我们来看树的先序遍历它的算法思想
刚才我们说过，先序遍历
是先访问树的根结点
然后，再以先序访问它的左子树
再以先序访问它的右子树
从刚才的描述
这个算法就比较适合以递归的形式来呈现
若二叉树T为空，则返回
我们现在看到的这句话
实际上就是递归的终结条件
当树为空的时候
我们就不需要再往下遍历了
如果非空呢
我们去访问T的根结点
实际上，就是T指向的那个结点r
然后，再以先序访问r的左子树，也就是图当中的L
这是一个递归的步骤
原问题出现在了问题步骤当中
但是规模小了
是子树。以先序访问完树的左子树
之后，再以先序访问根的右子树
所以，从整体上来看，先序遍历
它的算法，实际上就包含2个自己调用自己的步骤
分别是以先序访问左子树以及访问右子树
当然
在访问左右子树之前
得先访问当前树的根
现在，我们来看一个具体的树，这棵树
跟我们前面见的树，有点不太一样
在这棵树当中
叶子结点是a
b
c、d
这样的操作数
而非叶结点是运算符
对于这样的树
我们称为表达式树
当然
我们现在讲先序遍历
我们不用管一棵树
它代表的具体意义是什么
这棵树，我们很容易通过人脑，来给出它的先序序列
树的根是-
那我们先访问-
然后，再以先序访问-的左子树
这时候，子树的根是+
然后访问+，再去访问+的左子树a
再去访问a的左子树
注意，我们刚才讲到，终结条件是T为空
不是说T只有一个根结点
而是T为空
所以，在访问完a之后
我们还得去访问a的左子树
发现a的左子树是空
这时候，a的左子树访问完了
再去访问a的右子树
根据刚才的定义
左子树访问完了，访问右子树。a的右子树也是空
这时候，以a为根的这棵子树才访问完毕
+的左子树访问完了
我们再以先序去访问+的右子树
先访问*，再以先序访问*的左子树
后面的过程，我就不往下说了
我们以先序遍历，得到的表达式树的序列
称为前缀表达式
后面，我们还会遇到中缀以及后缀表达式
接下来，我们来看先序遍历它的算法
实现
算法的名字叫preOrder，参数是T
也就是给出来的
要遍历的二叉树
它的根
根据刚才讲的
如果T指向的结点是空的
那么，空树直接作为终结条件，返回
因为if控制的是一个return
所以，后面可以不要else
T指向的树非空
这时候，我们直接将T指向的结点
它的数据域打印出来，就可以了
紧接着，去以先序访问T的左子树
问题规模越来越小
原来是T
现在是T的左子树
然后，再以先序访问T的右子树
那这个算法
它的时间复杂度是多少呢
递归程序
它的实际执行流程，跟循环有点像
都是往前跳
然后，将之前执行过的代码再执行一次
循环的执行次数，通常是很容易能够分析出来的
但递归的次数，不太那么容易分析
这里，跟大家说一个简单的方法
我们看程序的第5行，第5行是打印T指向的结点
它的数据域，无论这个递归要执行多少次
要保证第5行一定会执行
结点个数次，因为无论怎么样
要把树当中每一个结点的信息打印出来
所以，这个算法它的时间复杂度就是结点个数n
这个算法的空间复杂度又是多少呢
我们来分析一下
如果T指向最开始的这个-
那么，打印完-之后，去递归遍历左子树；遍历左子树+的时候，打印完+，又进行了更深的递归
大家要知道递归的层次、深度
然后，要去遍历+的左子树a；+的左子树a
遍历完了之后，要去遍历a的左子树
a的左子树为空
这时候，才回到上一层
所以，这个递归的深度、递归的层数，实际上是跟整棵树的高度相关的
所以，这个算法它的空间复杂度
就是树的深度
因为，每一次递归，都需要将当前的语句地址以及当前一些参数入栈
以便转到递归处
每次递归，实际上都需要用一些空间保存这些信息
那么，空间复杂度
对于递归算法来说
对于先序遍历这个算法来说
它的空间复杂度就是树的深度
树的深度，极端情况下
有n个结点的树
它的深度就是n，这样一棵二叉树
所以，空间复杂度也是O(n)
-讲解
-作业
-讨论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 归并排序
--讲解
--作业
-讨论
