搜索
《数据结构与算法》课时教案第四章树和二叉树（12学时）第1页共34页课时教案周次第周第13次课课题§4.1树的逻辑结构和存储结构授课类型理论课（√）、实践课（）、实习（）时间设计授课内容与教学设计第四章树和二叉树教学目的要求：本章主要介绍树的基本概念，树的存储表示，树的遍历，树、森林和二叉树的转换，二叉树的定义、性质和存储结构，二叉树的遍历，哈夫曼树及其应用。要求学生掌握树和二叉树的递归定义、有关的术语及基本概念；二叉树的性质及其表示方法，二叉树的存储结构；二叉树的三种遍历；树、森林和二叉树之间的相互转换；树、森林的遍历及存储结构；哈夫曼树的建立及其应用。§4.1树的逻辑结构和存储结构4.1.1树型结构实例1．家族树图4-1家族树2．书的目录结构图4-2书的目录4.1.2树的定义1．树的定义树(Tree)是n(n≥0)个结点的有限集(记为T)，T为空时称为空树，否则它满12学时2学时祖父伯父父亲叔父堂兄堂姐本人堂弟侄儿(a)家族树家族关系表示：R={祖父，伯父,祖父，父亲，祖父，叔父，伯父，堂兄,伯父，堂姐，父亲，本人，叔父，堂弟,堂兄，侄儿}(b)家族谱系的关系表示数据结构线性表和广义表……树图栈队列树二叉树线性表广义表栈和队列《数据结构与算法》课时教案第四章树和二叉树（12学时）第2页共34页足以下两个条件：(1)有且仅有一个结点没有前驱，称该结点为根结点(Root)；(2)除根结点以外，其余结点可分为m(m≥0)个互不相交的有限集合T0，Tl，…，Tm-1。其中每个集合又构成一棵树，树T0，Tl，…，Tm-1被称为根结点的子树(Subtree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结构。图4-3树的示例图4-3(a)是一棵只有一个根结点的树；图4-3(b)是一棵有12个结点的树，即T={A，B，C，…，K，L}。A是树根，除根结点A之外，其余的11个结点分为三个互不相交的集合。T1，T2和T3是根A的三棵子树，且本身又都是一棵树。所以树的定义是递归的。2．树的基本术语树的结点包含一个数据元素及若干指向其子树的分支。（1）结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点;（2）树的度:树中所有结点的度的最大值Max(D(I))含义:树中最大分支数为树的度;（3）结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.树中结点的最大层次称为树的深度或高度（4）森林:是m(m=0)棵互不相交的树的集合森林与树概念相近,相互很容易转换.（5）有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：（6）孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。（7）子孙:以某结点为根的子树中的所有结点都被称为是该结点的子孙。（8）祖先:从根结点到该结点路径上的所有结点。（9）兄弟:同一个双亲的孩子之间互为兄弟。（10）堂兄弟:双亲在同一层的结点互为堂兄弟。3.树的基本运算树的基本运算主要有：（⒈）初始化操作INITIATE(T)：创建一棵空树。1学时AT(a)只有根结点的树ABDCJEGFHKILT1T2T3(b)有12个结点的树《数据结构与算法》课时教案第四章树和二叉树（12学时）第3页共34页（⒉）求根函数ROOT(T)：求树T的根；ROOT(X)：求结点x所在树的根。（⒊）求双亲函数PARENT(T,x)：在树T中求x的双亲。（⒋）求第i个孩子函数CHILD(T,x,i)：在树T中求结点x的第i个孩子。（⒌）建树函数CRT-TREE(x,F)：建立以结点x为根，森林F为子树的树。（6.）遍历树操作TRAVERSE(T)：按顺序访问树T中各个结点。4.1.3树的表示树的逻辑表示方法有多种，常见的有：1．树形图表示法2．嵌套集合表示法（文氏图表示法）3．凹入表示法4．广义表表示法4.1.4树的存储结构和线性表一样，树可以用顺序和链式两种存储结构。树的顺序存储结构适合树中结点比较“满”的情况。根据树的非线性结构特点，常用链式存储方式来表示树。树常用的存储方法有：双亲存储表示法、孩子链表表示法和孩子兄弟链表表示法。1．双亲存储表示法一般采用顺序存储结构实现。用一组地址连续的存储单元来存放树的结点，每个结点有两个域：data域-----存放结点的信息；parent域-----存放该结点双亲结点的位置特点：求结点的双亲很容易，但求结点的孩子需要遍历整个向量。存储结构描述为：#defineMaxTreeSize100//定义数组空间的大小typedefcharDataType；//定义数据类型typedefstruct{DataTypedata；//结点数据intparent；//双亲指针，指示结点的双亲在数组中的位置}PTreeNode；(A(B(E(F),G),C,D(H(I),J,K(L)))(c)广义表表示法ABDJCKLHIEFG(a)嵌套集合表示法ABEFGCDHIJKL(b)凹入表示法《数据结构与算法》课时教案第四章树和二叉树（12学时）第4页共34页typedefstruct{PTreeNodenodes[MaxTreeSize];intn；//结点总数}PTree；PTreeT；//T是双亲链表2．孩子链表表示法这是树的链式存储结构。每个结点的孩子用单链表存储，称为孩子链表。n个结点可以有n个孩子链表（叶结点的孩子链表为空表）。n个孩子链表的头指针用一个向量表示。特点：与双亲相反，求孩子易，求双亲难。图4-6树的孩子链表结构存储结构描述为：typedefstructCTNode{intchild;//孩子链表结点structCTNode*next;}*ChildPtr;typedefstruct//孩子链表头结点{ElemTypedata;//结点的数据元素ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstructABCFGDEHIA-1B0C0D1E1F1G2H4I4(a)树(b)树的双亲存储结构序号dataparent012345678ABCFGDEABC∧D∧EF∧G∧(a)树(b)树的孩子存储结构012345612∧345∧6∧《数据结构与算法》课时教案第四章树和二叉树（12学时）第5页共34页{CTBoxnodes[MaxTreeSize];intn,r,//数的结点数和根结点的位置}CTree;孩子链表表示法的类型说明typedefstructCnode//DataType和MaxTreeSize由用户定义{//孩子链表结点intchild;//孩子结点在数组中对应的下标structCNode*next;}Cnode;typedefstruct//孩子链表头结点{DataTypedata;//存放树中结点数据CNode*firstchild;//孩子链表的头指针}PTNode;typedefstruct{PTNodenodes[MaxTreeSize];intn,root;//树的结点数和根结点的位置}Ctree;CtreeT;//T的孩子链表表示3．孩子兄弟链表表示法孩子兄弟链表表示法也是树的一种链式存储结构。用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。这种结构也称为二叉链表。图4-7树的孩子-兄弟存储结构特点：双亲只管长子长子连接兄弟树的孩子兄弟链表的存储结构描述为：typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;孩子兄弟存储结构的最大优点是可以方便地实现树和二叉树的相互转换和树的各种操作。但是，孩子兄弟存储结构的缺点也是查找当前结点的双亲结点比较麻烦，需要从树根结点开始逐个结点比较查找。A∧B∧D∧C∧E∧F∧∧G∧《数据结构与算法》课时教案第四章树和二叉树（12学时）第6页共34页4.1.5树和森林的遍历1．树的遍历所谓树的遍历，就是按照某种顺序依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性结构的树结点变成线性序列的一种方式。树的遍历可以按深度优先遍历，也可以按照广度优先（按层次）遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。(1)前序遍历的递归定义：若树T非空，则：访问根结点R；按照从左到右的顺序依次前序遍历根结点R的各子树T1，T2，…，Tk。(2)后序遍历的递归定义：若树T非空，则：按照从左到右的顺序依次后序遍历根T的各子树Tl，T2，…，Tk；访问根结点R。广度优先（按层）遍历广度优先（按层次）遍历定义为：先访问第一层结点（即树根结点），再从左至右访问第二层结点，依次按层访问……，直到树中结点全部被访问为止。对图4-6(a)中的树进行按层次遍历得到树的广度优先遍历序列为：ABCDEFG。说明：①前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。（4.2节将介绍二叉树）②后序遍历树恰好等价于中序遍历该树所对应的二叉树。树的先序遍历算法描述如下：voidPreorder(Btree*root)//先根遍历k叉树{if(root!=NULL){printf(“%c\n”,root-data);//访问根结点for(i=0;ik;i++)preorder(root-t[i]);//递归前序遍历每一个子结点}}2．森林的遍历森林的深度优先遍历通常也有两种方式：前序遍历和后序遍历。(1)前序遍历森林若森林非空，则：访问森林中第一棵树的根结点；前序遍历第一棵树中根结点的各子树所构成的森林前序遍历去掉第一棵树外其它树构成的森林。(2)后序遍历森林若森林非空，则:后序遍历森林中第一棵树中根结点的各子树所构成的森林；访问第一棵树的根结点；后序遍历去掉第一棵树外其它树构成的森林。当用二叉链表作为树和森林的存储结构时，树和森林的前序遍历和后序遍历可用二叉树的前序遍历和中序遍历算法来实现。《数据结构与算法》课时教案第四章树和二叉树（12学时）第7页共34页图4-8森林和对应的二叉树授课重点、难点教学重点：熟悉树型结构常用术语，掌握基本概念以及树的存储。教学难点：树和森林的遍历。课堂讨论、思考题、作业作业：P159-163一、1-8二、1-4四、3。教学后记ABCDEFGHIJABECDFIGJH(a)森林(b)对应的二叉树《数据结构与算法》课时教案第四章树和二叉树（12学时）第8页共34页课时教案周次第周第14次课课题§4.2二叉树授课类型理论课（√）、实践课（）、实习（）时间设计授课内容与教学设计§4.2二叉树4.2.1二叉树的定义与性质二叉树(BinaryTree)是另一种重要的树型结构。是度为2的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。1．二叉树的递归定义二叉树(BinaryTree)是n(n≥0)个结点的有限集。它或者是空集(n=0)，或者同时满足以下两个条件：(1)有且仅有一个根结点；(2)其余的结点分成两棵互不相交的左子树和右子树。二叉树与树有区别：树至少应有一个结点，而二叉树可以为空；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据结构。二叉树有5种基本形态：(a)空二叉树(b)只有根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左右子树均不为空的二叉树图4-9二叉树的五种基本形态两种特殊形态的二叉树：满二叉树和完全二叉树。(1)满二叉树(Full