数据基础结构 8

教案纸（首页）第1页第次课学时授课时间___________教学主题树的基本定义和性质；树的遍历方法和存储结构；教学要求1、掌握树的定义及其逻辑结构特性，数组抽象数据类型的描述方法。2、掌握树的逻辑结构表示方法和树的性质。3、掌握树的遍历方法和树的存储结构。4、掌握栈在实际求解问题中的应用方法。教学重点树的递归特点；树的性质、树的遍历和树的存储结构教学难点树的性质、树的遍历和树的存储结构。教学方法讲授教学手段多媒体、板书讲授要点1、树的逻辑结构特性及树抽象数据类型的描述。2、树的逻辑表示方法及树的基本术语。3、树的性质。4、树的遍历方法。5、树的存储结构。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记7.1树的概念树型结构是一类重要的非线性结构，正如在课前思考题所看到的，树型结构广泛用于描述家族谱系以及其它社会组织结构。在计算机领域中，如编译程序中的语法结构和数据库中的信息组织也都需要借用树来描述。本章将讨论树和二叉树两种树型结构。1、树的定义树：T={D，R}。D是包含n个结点的有限集合（n≥0）。当n=0时为空树，否则关系R满足以下条件:有且仅有一个结点d0∈D，它对于关系R来说没有前驱结点，结点d0称作树的根结点。除根结点外，每个结点有且仅有一个前驱结点。D中每个结点可以有零个或多个后继结点。2、树的逻辑表示属性表示法文氏图表示法凹入表示法括号表示法3、树的基本术语结点的度与树的度：树中一个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度，通常将度为m的树称为m次树或者m叉树。分支结点与叶结点：度为零的结点称为终端结点或叶结点（或叶子结点）。度不为零的结点称为非终端结点，又叫分支结点。度为1的结点称为单分支结点；度为2的结点称为双分支结点，依此类推。路径与路径长度：两个结点di和dj的结点序列（di，di1，di2，…，dj）称为路径。其中<dx，dy>是分支。路径长度等于路径所通过的结点数目减1（即路径上分支数目或边的数目）。孩子结点、双亲结点和兄弟结点：在一棵树中，每个结点的后继，被称作该结点的孩子结点（或子女结点）。相应地，该结点被称作孩子结点的双亲结点（或父母结点）。具有同一双亲的孩子结点互为兄弟结点。子孙结点和祖先结点：在一棵树中，一个结点的所有子树中的结点称为该结点的子孙结点。从根结点到达一个结点的路径上经过的所有结点被称作该结点的祖先结点。结点的层次和树的高度：树中的每个结点都处在一个层次上。结点的层次从树根开始定义，根结点为第1层，它的孩子结点为第2层，以此类推，一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度（或树的深度）。有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。4、树的性质性质1树中的结点数等于所有结点的度数之和加1。性质2度为m的树中第i层上至多有mi-1个结点（i≥1）。性质3高度为h的m次树至多有个结点。性质4具有n个结点的m次树的最小高度为logm(n(m-1)+1)。5、树的基本运算树的运算主要分为三大类：查找满足某种特定关系的结点，如查找当前结点的双亲结点等。插入或删除某个结点，如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等。遍历树中每个结点。6、树的遍历树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。主要遍历方法：先根遍历，若树不空，则先访问根结点，然后依次先根遍历各棵子树。后跟遍历，若树不空，则先依次后根遍历各棵子树，然后访问根结点。层次遍历，若树不空，则自上而下、自左至右访问树中每个结点。7、树的存储结构双亲存储typedefstruct{ElemTypedata; //结点的值intparent; //指向双亲的位置}PTree[MaxSize];孩子链存储结构typedefstructnode{ElemTypedata; //结点的值structnode*sons[MaxSons]; //指向孩子结点}TSonNode;孩子兄弟链存储typedefstructtnode{ElemTypedata; //结点的值structtnode*hp; //指向兄弟structtnode*vp; //指向孩子结点}TSBNode;教学总结：本章节介绍了树的基本定义，树的逻辑结构，树的性质以及树的存储结构。

第次课学时授课时间__________教学主题二叉树教学要求1、掌握二叉树的定义及其性质。2、掌握二叉树与树、森林之间的转换。教学重点二叉树与树、森林之间的转换方法；二叉树的递归特点、二叉树的性质和二叉树的两种存储结构。教学难点二叉树与树、森林之间的转换方法；二叉树的递归特点、二叉树的性质和二叉树的两种存储结构。5、完全二叉树和满二叉树的特点。教学方法讲授教学手段多媒体、板书讲授要点1、二叉树的递归定义和二叉树的性质。2、完全二叉树和满二叉树的特点。3、二叉树与树、森林之间的转换方法。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记7.2二叉树的概念和性质二叉树的定义二叉树是有限的结点集合。这个集合或者是空(称为空二叉树)。或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树的结构特点：每个结点最多只有两棵子树，即结点的度不大于2子树有左右之分，子树的次序(位置)不能颠倒即使结点只有一颗子树，也有左右之分两种特殊的二叉树满二叉树:若二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。完全二叉树:假如一棵包含n个结点的二叉树中每个结点都可以和满二叉树中编号为1至n的结点一、一对应，则称这类二叉树为完全二叉树。3、二叉树的性质性质1非空二叉树上叶结点数等于双分支结点数加1。即：n0=n2+1。性质2非空二叉树上第i层上至多有2i-1个结点（i≥1）。性质3高度为h的二叉树至多有2h-1个结点（h≥1）。性质4完全二叉树性质（含n个结点）：n1=0或者n1=1。n1可由n的奇偶性确定。若i≤n/2，则编号为i的结点为分支结点，否则为叶结点。4、二叉树与树、森林之间的转换森林、树转换成二叉树二叉树还原为森林、树教学总结：本章节主要介绍了二叉树的定义，二叉树的性质，两种特殊的二叉树以及二叉树与树、森林之间的转换。第次课学时授课时间___________教学主题二叉树的两种存储结构；二叉树的基本运算算法设计教学要求1、掌握二叉树的两种存储结构。2、掌握二叉树的基本运算算法设计。教学重点二叉树的两种存储结构；二叉树的基本运算算法教学难点二叉树的存储结构及其特点；二叉树的基本运算算法教学方法讲授、练习教学手段多媒体、上机实操讲授要点1、二叉树的两种存储结构及其特点。2、二叉树的基本运算算法设计方法。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记二叉树的存储结构1、二叉树的顺序存储结构用数组实现特点：对于完全二叉树来说，其顺序存储是十分合适的。在顺序存储结构中，找一个结点的双亲和孩子都很容易。2、二叉树的链式存储结构用二叉链表实现特点：除了指针外，二叉链比较节省存储空间。在二叉链中，找一个结点的孩子很容易，但找其双亲不方便。二叉树的基本运算及其实现1、二叉树的基本运算创建二叉树CreateBTree(*b，*str)：根据二叉树括号表示法字符串str生成对应的二叉链存储结构b。销毁二叉链存储结构DestroyBTree(*b)：销毁二叉链b并释放空间。查找结点FindNode(*b，x)：在二叉树b中寻找data域值为x的结点，并返回指向该结点的指针。找孩子结点LchildNode(p)和RchildNode(p)：分别求二叉树中结点p的左孩子结点和右孩子结点。求高度BTHeight(*b)：求二叉树b的高度。若二叉树为空，则其高度为0；否则，其高度等于左子树与右子树中的最大高度加l。输出二叉树DispBTree(*b)：以括号表示法输出一棵二叉树。2、二叉树的基本运算的实现通过例子具体讲解采用二叉链表的存储方式对二叉树的基本运算算法设计实现。例子：将二叉树的二叉链结点类型及其基本运算函数存储在btree.cpp文件中。#include"btree.cpp" //包含二叉树的基本运算函数voidmain(){BTNode*b,*p;CreateBTree(b,"A(B(D(,G)),C(E,F))");printf("b:");DispBTree(b);printf("\n");printf("b的高度:%d\n",BTHeight(b));p=FindNode(b,'F');if(p!=NULL)printf("b中存在F结点\n");elseprintf("b中不存在F结点\n");DestroyBTree(b);}第次课学时授课时间___________教学主题二叉树的遍历教学要求1、掌握二叉树的遍历过程。2、掌握遍历二叉树的算法设计及其应用。教学重点二叉树的遍历过程；遍历二叉树的算法及其应用教学难点遍历二叉树的算法和对递归的理解教学方法讲授+练习教学手段多媒体、上机实操讲授要点1、二叉树的遍历过程。2、二叉树的先序、中序和后序遍历递归和非递归算法设计及其应用。3、二叉树的层次遍历算法设计及其应用。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记二叉树的遍历"遍历"的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。因此进行遍历应该确定一条搜索路径，使得结构中的每个数据元素都出现在这条搜索路径上，才能确保每个数据元素都被访问到。由于二叉树中每个结点都有两个后继，则可以有三条搜索路径：

1)先左(子树)后右(子树)；

2)先右(子树)后左(子树)；

3)按层次从上到下。

按层次从上到下的遍历比较简单，先访问第一层的结点(即根结点)，再访问第二层，第三层，…，直到最后一层，对每一层的结点则从左到右，即"先被访问的父结点的孩子结点"先于"后被访问的父结点的孩子结点"进行访问。例如，下列所示二叉树进行"按层次遍历"时，对结点访问的先后次序为：ABCDEFGHIJ。

1)和2)两条搜索路径相互对称，故以下重点讨论先左后右的遍历。先左后右的遍历从二叉树的结构定义得知，二叉树是由"根结点"、"左子树"和"右子树"三部分构成，则遍历二叉树的操作可分解为"访问根结点"、"遍历左子树"和"遍历右子树"三个子操作，并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样"递归"进行。因此整个遍历的操作只要在一条搜索路径上一次完成这三个子操作即可。

下图所示为对二叉树进行遍历的先左后右的搜索路径。从图可得知两个结论：1)由于左右子树互不相交，因此对左子树的遍历一定不会访问到右子树上的结点，反之对右子树的遍历也一定不会访问到左子树，因此沿这条搜索路径必可实现对二叉树中每个结点都访问到且只访问一次；2)也正由于左右子树不相交，因此在遍历了左子树之后必须回到根结点才能继续遍历右子树。由此可见，在这条搜索路径上从进入二叉树到离开二叉树，一共三次遇到根结点，因此访问根结点的操作可在任意一次也只能在其中一次进行。由此得到以下三个遍历二叉树的算法：

先序遍历二叉树中序遍历二叉树后序遍历二叉树若二叉树为空，则空操作；

否则

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。若二叉树为空，则空操作；

否则

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。若二叉树为空，则空操作；

否则

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。按照遍历过程中先后访问的次序将二叉树中的结点排列起来分别得到二叉树的先序序列、中序序列和后序序列。由以上遍历算法的定义很容易写出对应的递归算法。voidPreorder(BiTreeT，void(*visit)(BiTree))

{

//先序遍历以T为根指针的二叉树

if(T){//T=NULL时，二叉树为空树，不做任何操作

visit(T);//通过函数指针*visit访问根结点

Preorder(T->Lchild,visit);//先序遍历左子树

Preorder(T->Rchild,visit);//先序遍历右子树

}//}二叉树遍历算法的应用例7-11统计二叉树中叶子结点的个数

容易想到，实现这个操作只要对二叉树"遍历"一遍，并在遍历过程中对"叶子结点计数"即可。显然这个遍历的次序可以随意，即先序或中序或后序均可，只是为了在遍历的同时进行计数，需要在算法的参数中设一个"计数器"。intNodes(BTNode*b){if(b==NULL)return0;elsereturnNodes(b->lchild)+Nodes(b->rchild)+1}例7-13假设二叉树采用二叉链存储结构，设计一个算法Level()求二叉树b中值为x的结点的层次（假设所有结点值唯一）intLevel(BTNode*b，ElemTypex，inth)//找到p结点后h为其层次，否则为0{intL;if(b==NULL)return0; //空树时返回0elseif(b->data==x)returnh; //找到结点时else{L=Level(b->lchild，x，h+1); //在左子树中查找if(L==0) //左子树中未找到时在右子树中查找returnLevel(b->rchild，x，h+1); elsereturnL;}}

第次课学时授课时间___________教学主题哈夫曼树和哈夫曼编码的构造过程及其特点教学要求1、掌握二叉树的构造过程。2、掌握哈夫曼树和哈夫曼编码的构造过程。教学重点哈夫曼树的特点、哈夫曼树构造过程；哈夫曼编码的特点、哈夫曼编码构造过程教学难点哈夫曼树构造过程；哈夫曼编码构造过程教学方法讲授、练习教学手段多媒体、上机实操讲授要点1、二叉树的构造过程。2、哈夫曼树和哈夫曼编码的构造过程及其特点。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）教学内容备注与后记哈夫曼树和哈夫曼编码最优树，又称哈夫曼树（HuffmanTree）是一类带权路径长度最短的树，本节仅限于讨论最优二叉树。

首先介绍路径和路径长度的概念。由从树的根结点到其余结点的分支构成一条路径，路径上的分支数目称路径长度。一般情况下，树的路径长度指的是从树根到树中其余每个结点的路径长度之和。

结点的带权路径长度则定义为从树根到该结点之间的路径长度与该结点上所带权值的乘积。假设树上有n个叶子结点，且每个叶子结点上带有权值为Wk(k=1,2,…,n)，则树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记作

其中

lk为带权Wk的叶子结点的带权路径长度。

假设有n个权值{w1，w2，…wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。显然，这样的二叉树可以构造出多棵，其中必存在一棵带权路径长度WPL取最小的二叉树，称该二叉树为最优二叉树。例如，右图中的四棵二叉树，都有5个叶子结点且带相同权值5、6、2、9、7，它们的带权路径长度分别为

WPL=73+93+52+62+22=74(左上图)

WPL=21+63+74+94+52=94(右上图)

WPL=62+72+53+23+92=65(左下图)

WPL=21+53+73+93+63=83(右下图)

其中以左下图中二叉树的带权路径长度为最小。可以验证，它恰为最优二叉树，即在所有叶子结点带权为5、6、2、9、7的二叉树中，带权路径长度的最小值为65。最优树的构造方法

哈夫曼最早给出了一个构造最优树的带有一般规律的算法，俗称哈夫曼算法。现以最优二叉树为例叙述如下：

(1)根据给定的n个权值{w1,w2,…wn}，构成n棵二叉树的集合F={T1,T2,…,Tn}，