一、教学内容

栈、队列、树、二叉树

二、教学目标

1.了解栈、队列的概念。  

2.掌握线树、二叉树相关知识。

三、教学重点

1. 树

2. 二叉树

四、教学难点

二叉树

五、教学思路和方法

[教学思路设计]  综合运用讲授、例题，对比学习。 

[教学资源]  多媒体课件 

[教学安排] 100分钟

六、教学内容和过程：

详细教学过程和内容

备注

（教学方法及手段）

一、复习上节课内容（10分钟）

二、讲解与示范（90分钟）

（一）栈(stack)

---栈的运算仅限定在表尾一端进行的线性表。

引入：例题

（二）队列

定义：只允许在表的一端进行插入，而在表的另一端进行删除，是一种先入先出的线性表（FIFO, first in first out）。

引入：例题

（三）树的定义与基本术语

树是n(n>=0) 个节点的有限集。

树的结点：树结构的基本单元，包含一个数据元素以及若干个指向其子树的分支。

结点的度：拥有的子树的个数。

树的度：树内各结点的度的最大值。

树的深度(高度)是树中结点的最大层次。

叶子节点是度为0的结点。

父节点：是该节点的子树的根节点。相应地，该节点是孩子的双亲结点。

子点是同一个双亲结点的孩子结点。

结点的层次：根节点是第一层，根的孩子结点为第二层，依次类推。

有序数：树中结点的各子树从左到右是有次数的树。否则，称为无序树。

森林是m(m>=0)棵互不相交的树的集合。

（四）二叉树

二叉树是每个结点至多只有两棵子树，并且子树存在左右之分，其次序不能任意颠倒的树形结构。由此可知，二叉树可以为空树。

1．二叉树的性质

性质1. 在二叉树的第i层上至多有2i-1个结点(i>=1)

性质2. 深度为k的二叉树至多有2k-1个结点(k>=1)

性质3. 对任何一棵二叉树T，如果其终端结点的个数为m，度为2的结点的个数为n，则有m=n+1

性质4. 具有n个结点的完全二叉树的深度为└ log2n ┘+1

2．二叉树的两种特殊形态的树

满二叉树：一个深度为k且有2k-1个结点的二叉树。

完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。

3.二叉树的存储结构

（1）顺序存储结构

用一组地址连续的存储单元依次自上而下、自左向右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中。

此种存储方式的缺点就是不能完全利用数组的存储空间，造成空间资源浪费。

（2）链式存储结构

根据二叉树的定义得知，每一个结点都有一个数据元素和指向左右子树的分支构成，因此，定义二叉树结点的存储结构为数据域、左右指针域。

4.二叉树的遍历

前序遍历方式：根左右

中序遍历方式：左根右  

后序遍历方式：左右根

引入：例题

七、作业布置

教材P53思考题2、3、4