课 题

6-2用二叉树排序

课时安排

1

课型

素养目标

课程标准要求：1.结合实际理解树结构的概念和特征。

2.理解二叉排序树和二叉树可视化的基本原理。

信息意识：1.认识各种现实生活问题中蕴含的树结构。

2.体会二叉排序树在数据查找中的应用和二叉树绘制参数对可视化效果的控制。

计算思维：1.掌握二叉树抽象数据类型的定义。

2. 初步掌握二叉树排序算法和绘制算法。

数字化学习与创新：1.初步掌握二叉树的两种实现方法。

                  2. 体会递归思想在算法设计中的运用以及计算机视觉艺术形式。

信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的伦理道德和法律法规。

教学重点

用二叉树排序和绘制二叉树。

教学难点

二叉树绘制算法及实际应用。

教学方法

多媒体机房，python编程环境中讲授、演示、动手操作

学习方法

自主探究法

教学过程

个别化教案

一、考勤

二、课前测评：栈及其应用

三、导入新课：

本节课主要学习树结构。其实树结构是平日里我们常见的一种数据结构，例如家族族谱、公司管理层级结构图等，这样的数据结构的存在一定有一定的道理。

1、什么是树

树在我们平日应该算是一个低头不见抬头见的东西了。这里我特地找了个比较好看的树放在这里，大家可以观察一下树的特点，如图

第一反应是不是从树根开始往上生长，分出了特别的多分叉？没错，咱们要学习的树结构就是参照着真正的树衍生过来的，只不过是一个倒着的抽象的树，如图

我们把图中第一层的圆圈看成是树根，以下的几层都是由树根延伸出去的分支，这里的每一个圆圈都可以用于存储我们的数据。

树是一种非线性数据结构，它是由一个或多个结点组成的。

树（Tree）是n（n=0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、……Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。树结构是一对多的结构

2、树结构的特点

1）每个结点有零个或多个子结点

2）没有父结点的结点称为根结点

3）每一个非根结点有且只有一个父结点

4）除了根结点外，每个子结点可以分为多个不相交的子树

3、树结构VS线性结构

4、树的分类

1)       无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；

2)       有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；

3)       二叉树：每个节点最多含有两个子树的树称为二叉树；

4)       完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已 达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;

5)       平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；

6)       排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）；

7)       霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

8)       B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

5、树的存储表示

树的存储一般是顺序存储或者链式存储，即采用顺序表或者链表。

顺序存储：将数据结构存储在固定的数组中，在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。

链式存储：采用链表的方式来存储二叉树的各个结点。

6、什么是二叉树

满足以下两个条件的树就是二叉树：

1）本身是有序树。

2）树中包含的各个节点的度不能超过 2，即只能是 0、1、2。

7、画出二叉树

插图工具使用Python内置的turtle模块，为什么叫这个turtle海龟这个名字呢，可以这样理解，创建一个海龟，海龟能前进、后退、左转、右转，海龟的尾巴朝下，它移动时就会画一条线。并且为了增加海龟画图的艺术价值，可以改变尾巴宽度和尾巴浸入墨水的颜色。

递归绘制螺旋：

四、小结

1．树结构及其实现。

2. 用二叉树排序。

3. 画出二叉树。

作 业

板

书

设

计

树结构

二叉树及排序

画出二叉树

教

学

反

思

教案查阅签字