资源描述：
《华师本科生数据结构课件 第6章 二叉树和树.ppt》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第6章二叉树和树树型结构是一类重要的非线性结构。树型结构是结点之间有分支,并且具有层次关系的结构,它非常类似于自然界中的树。树结构在客观世界中是大量存在的。例如家谱、行政组织机构都可用树形象地表示。树结构在计算机领域中也有着广泛的应用,例如在编译程序中,用树结构来表示源程序的语法结构；在数据库系统中,可用树结构来组织信息；在分析算法的行为时,可用树结构来描述其执行过程等等。华中师范大学魏开平王敬华沈显君…系统软件办公室应用操作系统数据库数据结构离散数学……外语中文历史计科教务处科研处总务处………附中ds.cs.ccnu.edu.cnaueecneducc
2、nucsdsbuaawhu………………课前导学6.1二叉树6.2遍历二叉树和线索二叉树6.3树和森林6.4树的应用第六章二叉树和树【学习目标】领会树和二叉树的类型定义，理解树和二叉树的结构差别。熟记二叉树的主要特性，并掌握它们的证明熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。熟练掌握二叉树和树的各种存储结构及其建立的算法。学会编写实现树的各种操作的算法。了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。【重点和难点】重点：二叉树和树的遍历及其应用难点：编
3、写实现二叉树和树的各种操作的递归算法知识点树的类型定义二叉树的类型定义二叉树的存储表示二叉树的遍历以及其它操作的实现线索二叉树树和森林的存储表示树和森林的遍历以及其它操作的实现最优树和赫夫曼编码【学习指南】本章是整个课程的第三个学习重点，也是整个课程中的一大难点。在本章的学习过程中主要应该学会如何根据二叉树和树的结构及其操作的递归定义编写递归算法。本章必须完成的算法设计题为:6.1,6.3,6.4,6.5,6.6,6.7,6.8,6.9,6.10,6.11,6.12,6.14,6.16,6.17,6.18,6.20,6.21,6.24,6.25,6.26
4、6.1二叉树二、二叉树的基本性质一、二叉树的定义和基本术语三、二叉树的存储结构逻辑结构物理结构一、二叉树的定义和基本术语1、二叉树的定义2、二叉树的基本术语3、二叉树的应用举例4、二叉树的基本操作1、二叉树定义二叉树T是n个结点的有限集合，其中n≥0,当n=0时，为空树，否则，其中有一个结点为根结点，其余结点划分为两个互不相交的子集TL、TR，并且TL、TR分别构成叫作左、右子树的二叉树。ACDEFBGHIKJMLA的TLB的TL递归定义二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右
5、子树EF二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树二叉树的注意点二叉树每个结点的孩子都有左右之分，每个结点都有左右两个子树。ACBCBACBACBACBA三个节点的二叉树（五棵）①每个结点最多只有两棵子树(不存在度大于2的结点)；②左子树和右子树次序不能颠倒(有序树)。2、基本术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结
6、点的上层结点叫该结点的双亲深度——树中结点的最大层次数结点的层次——从根结点算起，根为第一层，它的孩子为第二层，……123114589126710——即根结点(没有前驱)——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点根双亲孩子兄弟堂兄弟祖先子孙ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：
7、E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先3、二叉树的应用举例男（色盲）女女男男女男•─ETNAIMOGKDWRUSHVFLPJBXCYZQ••••••••••••────────────国际Morse码变色力缺陷遗传图（隔代遗传）InitBiTree(&T);DestroyBiTree(&T);CreateBiTree(&T,definition);ClearBiTree(&T);BiTreeEmpty(T);BiTreeDe
8、pth(T);Parent(T,e);LeftChild(T,e);RightC
