第5章+树与二叉树

数据结构(Java语言描述)第五章树与二叉树数据结构（Java语言描述）第五章树与二叉树章节目录作业布置结束放映教学内容5.2二叉树的基本概念5.1树的基本概念5.4哈夫曼树及哈夫曼编码5.3二叉树的遍历5.5树与森林数据结构（Java语言描述）第五章树与二叉树章节目录作业布置结束放映教学重点与难点重点：二叉树的性质；二叉树的存储方法二叉树的遍历及其应用哈夫曼编码难点：二叉树遍历算法的应用数据结构（Java语言描述）第五章树与二叉树章节目录作业布置结束放映课前思考你见过家族谱系图吗？试以图形表示从你的祖父起的家族成员关系。祖父伯父父亲叔父堂兄堂姐你侄儿堂弟这类图形正是本章要讨论的“树”结构。数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录5.1.1树的定义5.1.2树的常用术语5.1树的基本概念数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录5.1.1树的定义树是由n（n≥0）个结点所构成的有限集合，当n=0时，称为空树；当n0时，n个结点满足以下条件：⑴有且仅有一个称为根的结点。⑵其余结点可分为m（m≥0）个互不相交的有限集合，且每一个集合又构成一棵树，这棵树称为是根结点的子树。数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录5.1.1树的定义ABCDEFGHIJMKL例如:rootT1T2T3数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录5.1.1树的定义树的表示方法：树形表示法文氏图表示法凹入图表示法广义表(括号)表示法ABCDEFGHIJMKL树形表示法数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录5.1.1树的定义ABCDEFGHIJMKL树形表示法EKFBDCJLGMIH文氏图表示法A数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录5.1.1树的定义ABCDEFGHIJMKL树形表示法凹入图表示法ABCDEFKLGIHJM数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录5.1.1树的定义ABCDEFGHIJMKL树形表示法广义表(括号)表示法:（A,B(E,F(K,L),C(G),D(H,I,J(M))数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录线性结构树型结构第一个数据元素(无前驱)存在一个根结点(无前驱)最后一个数据元素(无后继)存在多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它结点(一个前驱(双亲)、多个后继(孩子))元素之间存在“一对一”的关系元素之间存在“一对多”的关系数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录5.1.1树的定义5.1.2树的常用术语5.1树的基本概念数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录5.1.2树的常用术语结点:结点的度:树的度:叶子结点:分支结点:数据元素+所有关联子树根的分支结点所拥有子树的数目树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM分支:根和子树根之间的连线(边)结点的路径:由从根到该结点所经分支和结点构成数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：树中所有结点层次数的最大值加1。ABCDEFGHIJMKL假设根结点的层次为0，则其它结点的层次是其双亲结点的层次数加1。有序树：树中各结点的所有子树之间从左到右有严格的次序关系。数据结构（Java语言描述）5.1树的基本概念作业布置结束放映章节目录无序树:森林：由m（m≥0）棵互不相交的树所构成的集合。与有序树相反，无序树是指树中各结点的所有子树之间没有严格的次序关系。BCDEFGHIJMKL数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.1二叉树的定义5.2.2二叉树的性质5.2.3二叉树的存储结构5.2二叉树的基本概念数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.1二叉树的定义二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.1二叉树的定义二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.1二叉树的定义具有3个结点的树与二叉树的形态各有多少种?树有2种而二叉树有5种。问二叉树就是度小于等于2的树，这个结论是否正确？数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录满二叉树的定义如果在一棵二叉树中，它的所有结点或者是叶结点，或者是左、右子树都非空，并且所有叶结点都在同一层上，则称这棵二叉树为满二叉树。01234567891011121314数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录完全二叉树的定义如果在一棵具有n个结点的二叉树中，它的逻辑结构与满二叉树的前n个结点的逻辑结构相同，则称这样的二叉树为完全二叉树01234567890123456789完全二叉树非完全二叉树数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录单分支树的定义左支树：左支树右支树右支树：所有结点都没有右孩子的二叉树。所有结点都没有左孩子的二叉树。ABCDABCD数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.1二叉树的定义5.2.2二叉树的性质5.2.3二叉树的存储结构5.2二叉树的基本概念数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.2二叉树的性质在二叉树的第i层上至多有2i个结点。(i≥0)用归纳法证明：归纳基：归纳假设：归纳证明：i=0层时，只有一个根结点：20=1；假设对所有的j(0≤ji)层，命题成立；则第i层的结点数≤2i-12=2i。性质1：数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.2二叉树的性质深度为h（h≥1）的二叉树上至多含2h-1个结点。性质2：证明：基于上一条性质，深度为h的二叉树上的结点数至多为:20+21++2h-1=2h-1。数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.2二叉树的性质对于任何一棵二叉树，若其叶结点的个数为n0，度为2的结点个数为n2，则有n0=n2+1。性质3：则二叉树上结点总数n=？二叉树上分支总数e=？n0+n1+n2而e与n的关系如何？证明：n1+2n2由此得，n0=n2+1。设度为1的结点数为n1e=n-1数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.2二叉树的性质度为m的树中，叶子结点数与其它结点数之间的关系如何？思考数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.2二叉树的性质具有n个结点的完全二叉树的深度为log2n+1或log2(n+1)。性质4：证明：设完全二叉树的深度为h,则根据第二条性质得2h-1-1n≤2h-1即2h-1≤n2h,h-1≤log2nh因为h只能是整数，因此，h=log2n+1推出数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.2二叉树的性质性质5：若对含n个结点的完全二叉树从上到下且从左至右进行0至n-1的编号，则对完全二叉树中任意一个编号为i的结点,有：(1)若i=0，则该结点是二叉树的根，无双亲，否则，编号为(i-1)/2的结点为其双亲结点；(2)若2i+1≥n，则该结点无左孩子，否则，编号为2i+1的结点为其左孩子结点；(3)若2i+2≥n，则该结点无右孩子结点，否则，编号为2i+2的结点为其右孩子结点。数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.1二叉树的定义5.2.2二叉树的性质5.2.3二叉树的存储结构5.2二叉树的基本概念数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构2.二叉树的链式存储结构1.二叉树的顺序存储结构数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构—顺序存储用一组地址连续的存储单元从根结点开始依次自上而下，并按层次从左到右存储完全二叉树上的各结点元素，即将完全二叉树编号为i的结点元素存储在下标为i数组元素中。对于完全二叉树：数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构—顺序存储例如(完全二叉树）：0123456789abcdefghijabcdefghij0123456789数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构—顺序存储先在树中增加一些并不存在的虚结点并使其成为一棵完全二叉树，然后用与完全二叉树相同的方法对结点进行编号，再将编号为i的结点的值存放到数组下标为i的数组单元中，虚结点不存放任何值。对于非完全二叉树：数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构—顺序存储例如(非完全二叉树）：ABCDEF1401326ABDCEF012345678910111213问：一个深度为k且只有k个结点的右支树需要的数组存储单元为多少？顺序存储仅适用于满或完全二叉树。数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构—链式存储1.二叉链表2．三叉链表数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构—二叉链表rootlchilddatarchild结点结构:ACFBDGE数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构—三叉链表parentlchilddatarchild结点结构:ADEBCFroot数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构—二叉链表二叉链表中结点类的描述(书中P156)publicclassBiTreeNode{}//构造一个空结点publicBiTreeNode(){this(null);}//构造一个左、右孩子域为空的结点publicBiTreeNode(Objectdata){this(data,null,null)；}……privateObjectdata;//结点的数据域privateBiTreeNodelchild,rchild;//左、右孩子域数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构—二叉链表二叉链表中结点类的描述(书中P156)publicclassBiTreeNode{}//构造一个数据域和左、右孩子域都不为空的结点publicBiTreeNode(Objectdata,BiTreeNodelchild,BiTreeNoderchild){this.data=data;this.lchild=lchild;this.rchild=rchild;}…………数据结构（Java语言描述）5.2二叉树的基本概念作业布置结束放映章节目录5.2.3二叉树的存储结构—二叉链表二叉链表存储结构下二叉树类的描述(书中P158)publicclassBiTree{}//构造一棵空树publicBiTree(){this.root=