文章目录[隐藏]
- 5.5 遍历二叉树和线索二叉树
- 遍历二叉树算法描述
- 先序遍历二叉树的操作定义
- 中序遍历二叉树的操作定义:
- 后续遍历二叉树的操作定义:
- 例题
- 2.根据遍历序列确定二叉树
- 例题:由先序和中序确定一个二叉树
- 例题:由中序序列和后序序列求二叉树
- 复习:
- 先序遍历:
- 二叉链表实现
- 二叉树先序遍历算法
- 中序遍历:
- 后序算法
- 遍历算法的分析:
- 遍历二叉树的非递归算法
- 中序遍历非递归算法
- 二叉树的层次遍历
- 二叉树遍历算法的应用——二叉树的建立
- 按先序遍历序列建立二叉树的二叉链表
- 复制二叉树
- 计算二叉树的深度
- 计算二叉树节点总数
- 计算二叉树叶子节点数(补充)
- 线索二叉树
- 5.6 树和森林
- 树与二叉树的转换
- 5.6.2 森林与二叉树的转换
- 5.6.3 树与森林的遍历
- 5.7 哈夫曼树及其应用
- 5.8 案例分析与实现
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
也可以按照每个树的先(后)序遍历然后所有的链接起来的方法进行遍历森林。
叨叨几句... NOTHING