上节回顾 7.3二叉树的设计和实现 7.3.1二叉树的存储结构 7.3.2二叉链存储结构的二叉树操作实现
1 上节回顾 7.3 二叉树的设计和实现 7.3.1 二叉树的存储结构 7.3.2 二叉链存储结构的二叉树操作实现
7.4二叉树遍历 74.1二叉树遍历 1、遍历定义指按照某种顺序访问二叉树中的每个结点, 使每个结点被访问一次且仅被访问一次。 (或指按某条搜索路线遍访每个结点且不 重复) 2、遍历用途是树结构插入删除、修改、耷找和排 序运算的前提,是二叉树一切运算的基础 和核心。 3、遍历方法对每个结点的查看通常都是“先左后右
2 7.4 二叉树遍历 7.4.1 二叉树遍历 1、遍历定义—— 2、遍历用途—— 3、遍历方法—— 指按照某种顺序访问二叉树中的每个结点， 使每个结点被访问一次且仅被访问一次。 （或指按某条搜索路线遍访每个结点且不 重复）。 它是树结构插入、删除、修改、查找和排 序运算的前提，是二叉树一切运算的基础 和核心。 对每个结点的查看通常都是“先左后右”
4、遍历规则 二又树由根、左子树、右子树构成,定义为D、L、R 令D、L、R的组合定义了六种可能的遍历方案: LDR. LRD. DLR DRL RDL RLD 令若限定先左后右,则有三种实现方案 DLR LDR LRD 先序遍历中序遍历 后序遍历 注:“先、中、层的意思是指访问的结点D是先于子树出 现还是后于子树出现。 以根结点为参照系
3 4、遍历规则——— 二叉树由根、左子树、右子树构成，定义为D、L、R 以根结点为参照系 注：“先、中、后”的意思是指访问的结点D是先于子树出 现还是后于子树出现。 ❖ D、 L、R的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLD ❖ 若限定先左后右，则有三种实现方案： DLR LDR LRD 先序遍历 中序遍历 后序遍历
5、二叉树遍历的基本方法 有三种:先序遍历(LR)、中序遍历LDR)、后序遍历(LRD 通常可以把二叉树遍历操作设计成递归算法。 (一)先序遍历二叉树的递归算法为: 若二叉树为空,则算法结束;否则: (1)访问根结点; (2)先序遍历根结点的左子树; (3)先序遍历根结点的右子树。 (二)中序遍历二叉树的递归算法为 若二叉树为空,则算法结束;否则: (1)中序遍历根结点的左子树; (2)访问根结点;
4 5、二叉树遍历的基本方法 有三种:先序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD) 通常可以把二叉树遍历操作设计成递归算法。 （一）先序遍历二叉树的递归算法为： 若二叉树为空，则算法结束；否则： （1）访问根结点； （2）先序遍历根结点的左子树； （3）先序遍历根结点的右子树。 （二）中序遍历二叉树的递归算法为： 若二叉树为空，则算法结束；否则： (1）中序遍历根结点的左子树； （2）访问根结点；
(3)中序遍历根结点的右子树 (三)后序遍历二叉树的递归算法为: 若二叉树为空,则算法结束;否则 (1)后序遍历根结点的左子树; (2)后序遍历根结点的右子树; (3)访问根结点。 (四)二叉树的层序遍历算法: (1)初始化设置一个队列; (2)把根结点指针入队列; (3)当队列非空时,循环执行步骤(3.a)到步骤(3.c):
5 （3）中序遍历根结点的右子树。 （三）后序遍历二叉树的递归算法为： 若二叉树为空，则算法结束；否则： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。 （四）二叉树的层序遍历算法： (1)初始化设置一个队列； (2)把根结点指针入队列； (3)当队列非空时，循环执行步骤(3.a)到步骤(3.c):