数据结构(遍历二叉树)

发布于 2021-09-28  714 次阅读


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

二叉树的遍历:

file

file

遍历二叉树算法描述

file

file

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

file

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

file

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

file

例题

先:ABDGCEHF
中:DGBAEHCF
后:GDBHEFCA
file
先:-+axb-cd/ef
表达式的前缀表达式
中:a+bxc-d-e/f
表达式的中缀表达式
后:abcd-x+ef/-
表达式的后缀表示(逆波兰式)
file

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

file

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

file

file

file

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

file

复习:

先序遍历:

file

先序遍历列:ABDC

二叉链表实现

file

二叉树先序遍历算法

file

执行过程:

file

中序遍历:

file

file

后序算法

file

file

file

遍历算法的分析:

file

时间复杂度O(n)
空间复杂度O(n)

file

遍历二叉树的非递归算法

中序遍历非递归算法

file

file

file

二叉树的层次遍历

file

file

file

file

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

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

file

file

复制二叉树

file

计算二叉树的深度

file

计算二叉树节点总数

file

计算二叉树叶子节点数(补充)

file

线索二叉树

file

file

file

file

file

file

file

先序线索二叉树

file

中序线索二叉树

file

后序线索二叉树

file

file

file

file

5.6 树和森林

file

5.6.1 树的存储结构

1.双亲表示法

file

file

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

file

file

file

3.孩子兄弟表示法(二叉树表示法,二叉链表表示法)

file

例子:

file

树与二叉树的转换

file

file

file

file

将二叉树转换成树

file

file

5.6.2 森林与二叉树的转换

森林变二叉树

file

file

二叉树变森林

file

file

5.6.3 树与森林的遍历

1.树的遍历(三种方式)

file

2.森林的遍历

file

先序遍历(森林)

file

中序遍历(森林)

file

例子:

先:ABCDEFGHIJ
中:BCDAFEHJIG
file

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

5.7 哈夫曼树及其应用

5.8 案例分析与实现


擦肩而过的概率