数据结构授课教案-第6章

山东轻工业学院教师授课教案课程名称：数据结构（计科）课程代码：0301306学分：4.5课程类别：必修开课单位:信息科学与技术学院授课班级：授课教师：杨春花山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第六章树和二叉树第一节树的定义和术语树的定义和表示方法；结点、度、叶子和分支结点、孩子和双亲、兄弟、祖先、层次和深度、堂兄弟、有序树、无序树、森林等基本术语。第二节二叉树二叉树的定义和性质；满二叉树和完全二叉树的定义和特点；二叉树的存储结构分类、二叉链表存储结构定义和二叉树的基本操作。第三节二叉树的遍历和线索二叉树（先序、中序、后序）遍历二叉树的操作定义、递归算法，中序遍历的非递归算法，二叉树的层次遍历；线索二叉树的定义、存储表示和实现。第四节树和森林树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法；森林与二叉树的转换；树的先根和后跟遍历和森林的先序和中序遍历。第五节哈夫曼树及其应用赫夫曼树的定义和构造方法，前缀编码和赫夫曼编码的定义和赫夫曼编码/解码算法。目的要求目的：理解树和二叉树的定义和实现。基本要求：理解树的定义、表示方法和相关术语，理解树和森林的遍历，理解哈夫曼树和哈夫曼编码的概念；掌握二叉树的定义、性质、存储结构和基本操作，掌握满二叉树和完全二叉树的概念和性质、二叉树遍历的定义、遍历的递归算法和中序遍历的非递归算法，掌握线索二叉树的概念和线索化的方法、树与二叉树的转换方法和哈夫曼树的构造方法。重点二叉树的性质、存储结构；二叉树的遍历；二叉树的线索化；哈夫曼树的构造、哈夫曼编/译码。难点二叉树的性质；二叉树遍历的算法；哈夫曼树的构造和哈夫曼编/译码。作业布置习题6参考书1.数据结构题集(C语言版),严蔚敏，清华大学出版社，2002。3.数据结构、算法与应用－C++语言描述，(美)SartajSahni著，汪诗林等译，机械工业出版社，2002。课型理论课学时分复习分钟主要教具投影、黑板讲授分钟教学方法讲解、提问、示例配指导分钟教学手段板书、课件总结分钟备注共12学时，其中2学时为习题课注：课型一栏填写理论课、实验课、习题课等授课内容备注第六章树和二叉树树是一种重要的非线性数据结构。树的特点：每个结点至多有一个前驱，可有多个后继。树的应用：在现实中的应用：如族谱、各种社会组织机构等。在计算机领域：编译程序中的语法树、数据库系统中的索引等。6.1树的定义和基本术语1、树的定义树是由n(n≥0)个结点组成的有限集合。如果n=0，称为空树；否则，在一棵非空树中，满足如下两个条件：（1）有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；（2）除根以外的其它结点划分为m(m≥0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。2、树的表示（1）树型表示（直观表示法）（2）二元组表示（3）凹入法（4）嵌套集合表示（5）广义表表示（嵌套括号表示）3、基本术语结点（node）：包含一个数据元素及若干指向其它结点的分支信息。结点的度(degree)：结点的子树个数叶结点(leaf)：度为0的结点，也称为终端结点。分支结点(branch)：度不为0的结点，也称为非终端结点。孩子结点(child)：一个结点的直接后继或某结点子树的根结点。双亲结点(parent)：一个结点的直接前驱或某个结点是其子树之根的双亲。兄弟(sibling)结点:具有同一双亲的所有结点祖先(ancestor)结点:若树中结点k到ks存在一条路径，则称k是ks的祖先子孙(descendant)结点:若树中结点k到ks存在一条路径，则称ks是k的子孙结点所处层次(level):根结点的层数为1，其余结点的层，其余结点的层数为双亲结点的层数加1树的高度(depth):树中结点的最大层数树的度(degree):树中结点的最大度数有序树子树的次序不能互换无序树子树的次序可以互换森林（Forest）互不相交的树的集合4、树的基本操作①初始化②求指定结点所在树的根结点③求指定结点的双亲结点④求指定结点的某一孩子结点⑤求指定结点的最右边兄弟结点⑥将一棵树插入到另一树的指定结点下作为它的子树⑦删除指定结点的某一子树⑧树的遍历6.2二叉树(BinaryTree)6.2.1二叉树的定义1、二叉树（BinaryTree）或为空树，或由根及两棵不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明1）二叉树中每个结点最多有两棵子树；二叉树每个结点度小于等于2;2）左、右子树不能颠倒——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;2、二叉树的五种不同形态3、二叉树和树的区别：二叉树不是树的特殊情形，它们是两个概念。树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。6.2.2二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)性质2：深度为k的二叉树最多有2k-1个结点。(k≥1)性质3：对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1。两种特殊的二叉树：满二叉树：深度为k且有2k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。完全二叉树：若设二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层的结点集中出现在左端若干连续位置上，这就是完全二叉树。完全二叉树举例.性质4：具有n个结点的完全二叉树的深度为└log2n┘+1证明：设完全二叉树的高度为深度为h，则有2h-1-1n≤2h-1⇒2h-1=n2h⇒取对数h–1=log2(n)h。性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：（1）如i=1，则序号为i的结点是根结点，无双亲结点；如i1，则序号为i的结点的双亲结点序号为└i/2┘。（2）如2×in，则序号为i的结点无左孩子；如2×i≤n，则序号为i的结6.2.3二叉树的存储结构1、顺序存储结构#defineMAXNODE100typedefelemtypeSqBiTree[MAXNODE]SqBiTreebt;顺序存储结构仅适用于完全二叉树2、链式存储结构（1）二叉链表：二叉链表中每个结点包含三个域：数据域、左指针域、右指针域typedefstructnode{ElemTypedata;structnode*lchild;structnode*rchild;}BiTNode,*BiTree;（2）三叉链表：三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域6.2.4二叉树的基本操作创建二叉树二叉树的遍历6.3遍历二叉树和线索二叉树6.3.1遍历二叉树（traversingbinarytree）一、遍历二叉树的定义：1、先序遍历（DLR）若二叉树为空，则空操作；否则：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；2、中序遍历（LDR）若二叉树为空，则空操作；否则：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；3、后序遍历（LRD）若二叉树为空，则空操作；否则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点；例：先序遍历、中序遍历、后序遍历下图所示的表达式语法树二、遍历二叉树的递归算法数据结构定义：typedefintElemType;typedefstructnode{ElemTypedata;structnode*lchild,*rchild;}BiTNode,*BiTree;1、先序遍历PreOrderTranverse(BiTreeT){if(T){printf(“%d”,T-data);//访问的方式有多种PreOrderTranverse(T-LChild);PreOrderTranverse(T-RChild);}}2、中序遍历InOrderTranverse(BiTreeT){if(T){InOrderTranverse(T-LChild);printf(“%d”,T-data);//访问的方式有多种InOrderTranverse(T-RChild);}}3、后序遍历PostOrderTranverse(BiTreeT){if(T){PostOrderTranverse(T-LChild);PostOrderTranverse(T-RChild);printf(“%d”,T-data);//访问的方式有多种}}三、遍历二叉树的非递归算法遍历的递归执行过程：（一）基于栈的递归消除1、中序遍历的非递归算法voidInOrder（BiTreeT）{InitStack(S);push(S,T);while(!StackEmpty(S)){if(Getop(S,p)&&p!=NULL)//向左走到尽头{push(S,p-lchild;}pop(S,p);//空指针退栈if(!StackEmpty(S)){//访问结点，向右一步pop(S,p);visit(p-data);p=p-rchild;}}}voidInOrder（BiTreeT）{InitStack(S);p=T;while(p!=NULL||!StackEmpty(S)){if(p!=NULL)/*根指针进栈，遍历左子树*/{push(S,p);p=p-lchild;}else{/*根指针退栈，访问根结点，遍历右子树*/pop(S,p);visit(p-data);p=p-rchild;}}}2、先序遍历的非递归算法voidPreOrder（BiTreeT）{InitStack(S);p=T;while(p!=NULL||!StackEmpty(S)){if(p!=NULL)/*根指针进栈，遍历左子树*/{visit(p-data);push(S,p);p=p-lchild;}else{/*根指针退栈，访问根结点，遍历右子树*/pop(S,p);p=p-RChild;}}}3、后序遍历的非递归算法typedefstruct{BiTreelink;intflag;}stacktype;voidPostOrder（BiTreeT）{stacktypestack[MAXNODE];BiTreep;inttop,sign;if(T==NULL)return;top=-1;/*栈顶位置初始化*/p=T;while(!(p==NULL&&top==-1)){if(p!=NULL)/*结点第一次进栈*/{top++;stack[top].link=p;stack[top].flag=1;p=p-lchild;}else{p=stack[top].link;sign=stack[top].flag;top--;if(sign==1)//结点第二次进栈{top++;stack[top].link=p;stack[top].flag=2;//标记第二次出栈*/p=p-rchild;}else{visit(p-data);p=NULL;}}}}四、层次遍历二叉树二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。例：voidLevelOrder（BiTreebt）/*层次遍历二叉树bt*/{BiTreeQueue[MAXNODE];intfront,rear;if(bt==NULL)return;front=-1;rear=0;queue[rear]=bt;while(front!=rear){front++;p=queue[front];Visit(p-data);if(p-lchild!=NULL)/*队首结点的左孩子入队*/{rear++;queue[rear]=p-lchild;}if(p-rch