5.5 遍历二叉树和线索二叉树

二叉树的遍历：

遍历二叉树算法描述

先序遍历二叉树的操作定义

中序遍历二叉树的操作定义：

后续遍历二叉树的操作定义：

例题

先:ABDGCEHF
中:DGBAEHCF
后:GDBHEFCA

先:-+axb-cd/ef
表达式的前缀表达式
中：a+bxc-d-e/f
表达式的中缀表达式
后：abcd-x+ef/-
表达式的后缀表示（逆波兰式）

2.根据遍历序列确定二叉树

例题：由先序和中序确定一个二叉树

例题：由中序序列和后序序列求二叉树

复习：

先序遍历：

先序遍历列：ABDC

二叉链表实现

二叉树先序遍历算法

执行过程：

中序遍历：

后序算法

遍历算法的分析：

时间复杂度O（n）
空间复杂度O（n）

遍历二叉树的非递归算法

中序遍历非递归算法

二叉树的层次遍历

二叉树遍历算法的应用——二叉树的建立

按先序遍历序列建立二叉树的二叉链表

复制二叉树

计算二叉树的深度

计算二叉树节点总数

计算二叉树叶子节点数（补充）

线索二叉树

先序线索二叉树

中序线索二叉树

后序线索二叉树

5.6 树和森林

5.6.1 树的存储结构

1.双亲表示法

2.树的存储结构—孩子链表

3.孩子兄弟表示法（二叉树表示法，二叉链表表示法）

例子：

树与二叉树的转换

将二叉树转换成树

5.6.2 森林与二叉树的转换

森林变二叉树

二叉树变森林

5.6.3 树与森林的遍历

1.树的遍历（三种方式）

2.森林的遍历

先序遍历（森林）

中序遍历（森林）

例子：

先：ABCDEFGHIJ
中：BCDAFEHJIG

也可以按照每个树的先（后）序遍历然后所有的链接起来的方法进行遍历森林。

5.7 哈夫曼树及其应用

5.8 案例分析与实现