湖北大学知行学院 教师：涂晓帆 Sunday, December 09, 2018

Presentation on theme: "湖北大学知行学院 教师：涂晓帆 Sunday, December 09, 2018"— Presentation transcript:

1 湖北大学知行学院 教师：涂晓帆 Sunday, December 09, 2018
数据结构 湖北大学知行学院 教师：涂晓帆 Sunday, December 09, 2018

2 目录 自我介绍 课程介绍 教学内容 ＦＡＱ

3 自我介绍 我的名字：涂晓帆 我的电话：１８１２０５５６８８０ 我的邮箱：７６３３９２７＠qq.com 我的主页：tuxf.net

4 课程介绍 程序=数据结构+算法 计算机的基本任务是对数据的处理，而数据又分为数值数据和非数值数据，目 前世界上超过90%的数据处理都是对非数值数据的处理，数据结构就是研究非数 值数据之间的结构关系，以及表示方法、存储方法和处理方法。 知识基础：Ｃ语言程序设计（或者其他高级语言，如pascal、basic、java、 c++、c#、JS、Python、swift……）、面向对象程序设计、数据库 后继课程：计算方法、Visual C++（或其他工程应用开发方法学习，如 JavaWeb、.Net、Delphi、Android、IOS等开发工具的课程） 课时：每周4节课，共12周 评分标准：平时成绩20%（考勤、课堂表现）、作业表现30%、期末成绩50% 教程：数据结构（c语言版）-严蔚敏、吴伟民，清华大学出版社 课程公告、课件下载、作业发布、提交：tuxf.net

5 教学内容 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表 第六章 树和二叉树 第七章 图
第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表 第六章 树和二叉树 第七章 图 第八章 动态存储管理 第九章 查找 第十章 内部排序 第十一章 外部排序 第十二章 文件

6 第六章 树和二叉树 主要内容: 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林
第六章 树和二叉树 主要内容: 6.1 树的定义和基本术语 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历 6.5 树与等价问题 6.6 赫夫曼树及其应用 6.6.1 最优二叉树 6.6.2 赫夫曼编码

7 重点回顾： 1、树的定义 2、二叉树的定义 3、Microsoft Visual Studio 4、递归

8 重点回顾——1、树的定义 树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有 层次关系的结构。它非常类似于自然界中的树。     树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形 象地表示。     树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源 程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为 时，可用树来描述其执行过程。

9 重点回顾——2、二叉树的定义—1 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往 是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的 存储结构及其算法都较为简单，因此二叉树显得特别重要。 说明 1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2; 2）左、右子树不能颠倒——有序树; 3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念; A F G E D C B

10 重点回顾——2、二叉树的定义—2 二叉树的顺序存储结构
1、用一维数组bt[ ]存放一棵完全二叉树 2、将标号为 i 的结点的数据元素存放在分量 bt[i-1]中 3、存储位置隐含了树中的关系，树中的关系是通过完全二叉树的性质实现的。例如，bt[5]（i=6)的双亲结点标号是k=trunc(i/2)=3,双亲结点所对应的数组分量bt[k-1]=bt[2] A 1 A C C B 2 B 3 F 4 F D E D 5 E 6 7 10 G 8 9 G m-1 A B C D E 0 F G

11 重点回顾——2、二叉树的定义—3 二叉链表 A B ∧ ∧ D C ∧ ∧E ∧ ∧F ∧ 二叉链表中每个结点包含三个域： 1、数据域
2、左指针域 3、右指针域 Struct node { int data; struct node *lch,*rch; };

12 重点回顾——3、Visual Studio

13 重点回顾——4、递归

14 本节课内容

15 6.3.1 遍历二叉树 主要内容： 重点、难点 遍历的基本概念 各种遍历方法的思想 各种遍历方法的递归算法和非递归算法
6.3.1 遍历二叉树 主要内容： 遍历的基本概念 各种遍历方法的思想 各种遍历方法的递归算法和非递归算法 以先序输入方式建立二叉树的算法。 重点、难点 各种遍历方法的非递归算法

16 一. 遍历的基本概念 遍历是各种数据结构最基本的操作，许多其他的操作 可以在遍历基础上实现。
一. 遍历的基本概念 遍历是各种数据结构最基本的操作，许多其他的操作 可以在遍历基础上实现。 二叉树的遍历：沿某条路径周游二叉树，对树中的每 个结点访问一次且仅访问一次。 “访问”的含义很广，可以是对结点的各种处理，如修改结点数据、输出结点 数据。

17 两种基本策略： 广度遍历 深度遍历 如何访问二叉树的每个结点， 而且每个结点仅被访问一次？ ？ A F E D C B

18 广度遍历策略 遍历结果：A B C D E F 层次遍历方法：从上到下、从左到右访问各结点 1 2 3 4 5 6 7 8 A B C D
适用于顺序存储结构 存储结构 A F E D C B 1 2 3 4 5 6 7 8 A B C D φ E F 遍历结果：A B C D E F

19 深度遍历策略 二叉树由根、左子树、右子 树三部分组成 二叉树的遍历可以分解为： B 有六种遍历方法： F D G A 访问根（D） C
E D C B 二叉树由根、左子树、右子 树三部分组成 二叉树的遍历可以分解为： 访问根（D） 遍历左子树（L） 遍历右子树（R） 有六种遍历方法： D L R，L D R，R D L ， D R L， L R D ，R L D 约定先左后右,有三种遍历方 法，分别称为先序遍历、中序 遍历、后序遍历

20 二、各种遍历的思想 1 . 先序遍历（DLR） 2 . 中序遍历（LDR） 3. 后序遍历（RDL）

21 1 . 先序遍历（DLR） B F G D H K A 例：先序遍历右图所示的二叉树，所得先序遍历序列： E
若二叉树非空，则依次进行以下操作 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树； A 例：先序遍历右图所示的二叉树，所得先序遍历序列： A, B, C, D, E, F, G, H, K E B F C G D Flash演示 H K

22 2. 中序遍历（LDR） B 例：中序遍历右图所示的二叉树，所得中序遍历序列： F B, D, C, A, E, H, G, K, F G
若二叉树非空，则依次进行以下操作 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树； A F H E D C B G K 例：中序遍历右图所示的二叉树，所得中序遍历序列： B, D, C, A, E, H, G, K, F Flash演示

23 3. 后序遍历（LRD） B F 例：后序遍历右图所示的二叉树，所得后序遍历序列： D, C, B, H, K, G, F, E, A G
若二叉树非空，则依次进行以下操作 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点； A F H E D C B G K 例：后序遍历右图所示的二叉树，所得后序遍历序列： D, C, B, H, K, G, F, E, A Flash演示

24 软件水平考试有关试题 2015年试题 2004年试题 2002年试题 1999年试题

25 2015年 试题 对于非空的二叉树，设D代表根结点，L代表根结点的左子树R代表根结 点的右子树。若对下图所示的二叉树进行遍历后的结点序列为 ，则遍历方式是（59）。  A）LRD B）DRL C）RLD D）RDL

26 2002年 试题 假设一棵二叉树的后序遍历序列为 D G J H E B I F C A，中序遍历序列为
D B G E H J A C I F，则其前序遍历序列 为 。 A）A B C D E F G H I J B）A B D E G H J C F I C）A B D E G H J F I C D）A B D E G J H C F I A B D E G H J C F I

27 1999试题2 二叉树的查找有深度优先和广度优先二类，深度优先包括 _C_。当一棵二叉树的前序序列和中序序列分别是
H G E D B F C A 和 E G B D H F A C时，其后序序列 必是_D_,层次序列为_E_. C: (1)前序遍历 后序遍历 中序遍历 (2)前序遍历 后序遍历 层次遍历 (3)前序遍历 中序遍历 层次遍历 (4)中序遍历 后序遍历 层次遍历 D: (1) B D E A G F H C (2) E B D G A C F H (3) H G F E D C B A (4) H F G D E A B C H G E D B F C A E: (1) B D E A C G F H (2) E B D G A C F H (3) H G F E D C B A (4) H F G C D E A B

28 软件设计师 2004上半年 设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y 之前，而在其后根遍历序列中x在y之后，则x和y的关系是__(10)__。 A．x是y的左兄弟 B．x是y的右兄弟 C．x是y的祖先 D．x是y的后裔

29 三、遍历的递归算法 void preorder（btree *t） { if (t) { putchar(t->data);
前序遍历（DLR） void preorder（btree *t） { if (t) { 若二叉树t非空，则： putchar(t->data); 访问根结点t preorder(t->lchild); 前序遍历t的左子树 前序遍历t的右子树 preorder(t->rchild); }

30 中序遍历、后序遍历的递归算法 后序遍历 中序遍历 void postorder（bitree *t）
{ if ( t ) { postorder(t->lchild); postorder(t->rchild); putchar(t->data); } 中序遍历 void inorder（bitree *t） { if ( t ) { inorder(t->lchild); putchar(t->data); inorder(t->rchild); } 你能写出后序遍历递归算法了吧

31 思考： 1、树的应用场景、应用方式 2、算法复杂度

32 拓展阅读： 红黑树、B+树 挑战：红黑树的构造、遍历、插入、删除（可选作业，可加分 ）

33 下一节课的准备 完成作业、拓展阅读 尽力实现挑战作业 预习线索二叉树、树、森林概念

34 作业： 二叉树中序遍历 设计一个包含各种情况的二叉树 输入：字符模式下，中序输入二叉树 处理：存入数据库
输出：按后序遍历方法输出所有节点内容 作业形式：Word，包含设计图、源代码、注释、调试截图 截止时间：下次上课前一天晚上八点以前 注意事项：邮件主题格式——班级_姓名_数据结构_第5次作业

35 ＦＡＱ 考试时间：下个月底 考试形式：笔试+课程设计 拓展阅读：《数据结构C++语言描述》、《计算方法》
下一阶段的学习目标：IDE、Windows程序设计、Web程序设计、数据库高 级应用、网络编程

36 Thanks！