第六章 树和二叉树.ppt

第6章 树和二叉树F 6.1 树的定义和基本术语F 6.2 二叉树F 6.3 遍历二叉树和线索二叉树F 6.4 树和森林F 6.6 赫夫曼树及其应用 特点：非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个 直接后继（直接后继（1：n）第6章 树和二叉树1.树的定义 注：注：树的定义具有树的定义具有递归性递归性，即树中还有树。，即树中还有树。由一个或多个（n 0）结点组成的有限集合。在任何一棵非空树T中：（1）有且仅有一个结点称为根（root）；（2）当n1时，其余的结点分为m（m 0）个 互不相交的有限集合T1、T2Tm。每个 集合本身又是棵树，被称作这个根的子树。6.1 树的定义和基本术语A只有根结点的树只有根结点的树ABCDEFGHIJKLM根根子树子树6.1 树的定义和基本术语树的抽象数据类型定义D D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。ADT ADT TreeTree TreeTree数据对象数据对象D:数据操作数据操作P:数据关系数据关系R:若若D D是空集，则称为空树；是空集，则称为空树；/允许允许n=0n=0若若D D中仅含一个数据元素，则中仅含一个数据元素，则R R为空集；为空集；其他情况下的其他情况下的R R存在二元关系：存在二元关系：RootRoot唯一唯一/关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明/至少至少1515个个6.1 树的定义和基本术语图形表示法嵌套集合表示法广义表表示法凹入表示法（目录表示法）树的表示方法6.1 树的定义和基本术语图形表示法：三亚学院三亚学院理工分院理工分院人文分院人文分院管理分院管理分院通信通信测控测控电信电信计算机计算机根子树ABCDEFGH6.1 树的定义和基本术语广义表表示法：ABCDEFGH根根作为由子树森林组成的作为由子树森林组成的表的名字写在表的左边表的名字写在表的左边A（B，C，D）A（B，C（E,F,G,H），），D）凹入表示法：ABCDEFGH6.1 树的定义和基本术语ABCDEFGH嵌套表示法：ABDCEGFH6.1 树的定义和基本术语2.若干术语 ABCDJEFG HIKLM 根根-根结点（没有前驱）根结点（没有前驱）森林森林-指指m m棵不相交的树的集合棵不相交的树的集合有序树有序树-结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）无序树无序树-结点各子树可互换位置结点各子树可互换位置 双亲双亲-上层的那个结点（直接前驱）上层的那个结点（直接前驱）孩子孩子-下层结点的子树的根（直接后继）下层结点的子树的根（直接后继）兄弟兄弟-同一双亲下的同一层结点（孩子之间互称兄弟）同一双亲下的同一层结点（孩子之间互称兄弟）堂兄弟堂兄弟-双亲位于同一层的结点（但并非同一双亲）双亲位于同一层的结点（但并非同一双亲）祖先祖先-从根到该结点所经分支的所有结点从根到该结点所经分支的所有结点 子孙子孙-该结点下层子树的任一结点该结点下层子树的任一结点6.1 树的定义和基本术语ABCDJEFG HIKLM 结点结点-树中的数据元素树中的数据元素 结点的度结点的度-结点拥有的子树的数目结点拥有的子树的数目（有几个直接后继度就是几）（有几个直接后继度就是几）结点的层次结点的层次-从根到该结点的层数从根到该结点的层数（根结点算第一层）（根结点算第一层）叶子叶子-度为度为0 0的点（终端结点）的点（终端结点）分支结点分支结点-度不为度不为0 0的点（非终端结点）的点（非终端结点）树的度树的度-所有结点度中的最大值所有结点度中的最大值（Max 各结点的度各结点的度）树的深度树的深度-所有结点中最大的层数所有结点中最大的层数（Max 各结点的层次各结点的层次 ）（或高度）（或高度）6.1 树的定义和基本术语已知一棵树的集合为,，请画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点G的双亲？（4）哪些是结点G的祖先？（5）哪些是结点G的孩子？（6）哪些是结点E的子孙？（7）哪些是结点E的兄弟？哪些是结点F的兄弟？（8）结点B和N的层次号分别是什么？（9）树的深度是多少？（10）以C为根的子树的深度是多少？课堂练习(一)k1k2k3k4k7k5k6一、对照右图回答下列问题：一、对照右图回答下列问题：1、这棵树的根结点？2、这棵树的叶子结点？3、结点k3的度？4、这棵树的度？5、这棵树的深度？6、结点k1的孩子结点？7、结点k3的双亲结点？8、以k3为根的子树的深度？二、已知树的集合为二、已知树的集合为,，分别用分别用图形表示法、广义表表示法、嵌套表示法、凹入表示法画出这棵树。图形表示法、广义表表示法、嵌套表示法、凹入表示法画出这棵树。课堂练习(一)二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转化为唯一对应的二叉树，不失可以证明，所有树都能转化为唯一对应的二叉树，不失一般性。一般性。1.二叉树的定义二叉树的定义2.二叉树的性质二叉树的性质3.二叉树的存储结构二叉树的存储结构6.2 二叉树1 1、二叉树的定义、二叉树的定义 每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）；左子树和右子树次序不能颠倒（有序树）。左子树和右子树次序不能颠倒（有序树）。基本特征：基本特征：基本特征：基本特征：基本形态：基本形态：基本形态：基本形态：具有具有3 3个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？6.2 二叉树-定义2 2、二叉树的性质、二叉树的性质 性质性质1 1：在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个个结点（结点（i0i0）。）。问：第问：第i i层上至少有层上至少有 个结点？个结点？性质性质2 2：深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点（个结点（k0k0）。）。性质性质3 3：对于任何一棵二叉树，若度对于任何一棵二叉树，若度2 2的结点数有的结点数有n2n2个，个，叶子结点数为叶子结点数为n0n0，则，则n0=n2+1n0=n2+1。6.2 二叉树-性质证明性质3：二叉树中全部结点数二叉树中全部结点数n=n0+n1+n2n=n0+n1+n2(叶子数叶子数+度度1 1的结数的结数+度为度为2 2的结点数的结点数)又又 二叉树中全部结点数二叉树中全部结点数n=B+1n=B+1(总分支数总分支数 +根结点根结点)（除根结点外，每个结点必有一个直接前驱，即一个分支）（除根结点外，每个结点必有一个直接前驱，即一个分支）而而 总分支数总分支数B=n1+2n2B=n1+2n2(度为度为1 1必有必有1 1个直接后继，度为个直接后继，度为2 2必有必有2 2个直接后继个直接后继)三式联立可得：三式联立可得：n0+n1+n2=n1+2n2+1n0+n1+n2=n1+2n2+1，即，即n0=n2+1n0=n2+16.2 二叉树-性质满二叉树：深度为深度为k且有且有 2k-1个结点的二叉树。个结点的二叉树。特点：特点：每一层上的结点数都是最大结点数。每一层上的结点数都是最大结点数。可以对满二叉树的结点进行连续编号。可以对满二叉树的结点进行连续编号。4 48 89 95 51010 11116 61212 13137 71414 15152 23 31 1完全二叉树：完全二叉树：深度为深度为k，有，有n个结点的个结点的二叉树，当且仅当其每一个结点都与深度二叉树，当且仅当其每一个结点都与深度为为k的满二叉树中编号从的满二叉树中编号从1至至n 的结点一一的结点一一对应时，称之为完全二叉树。对应时，称之为完全二叉树。特点特点:（1）叶子结点只可能在层次最大的两层上出现；叶子结点只可能在层次最大的两层上出现；（2）对任一结点，若其右分支下的子孙的最大层次为）对任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次数必为则其左分支下的子孙的最大层次数必为h或或h+1。4 48 89 95 510106 67 72 23 31 16.2 二叉树-特例12311458912136710141512311458912671012345671234566.2 二叉树-特例对于特殊性质的二叉树，还具备以下2个性质：性质性质4 4：具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为 loglogloglog2 2 2 2n n n n 1。性质性质5 5：如果对一棵有如果对一棵有n个结点的完全二叉树个结点的完全二叉树(其深度为其深度为 loglogloglog2 2 2 2n n n n 1)的结点按层序编号，则对任一结点的结点按层序编号，则对任一结点i（1in），有：），有：1）如果）如果i i=1，则结点则结点i i是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果i i1，则其双亲则其双亲parent（i i）是结点是结点 i/2 ；2）如果如果2i in，则结点则结点i无左孩子无左孩子(结点结点i i为叶子结点为叶子结点)；否则其；否则其 左孩子左孩子lchild（i i）是结点是结点2i i；3）如果如果2i i+1n，则结点则结点i i无右孩子；否则其右孩子无右孩子；否则其右孩子rchild(i i)是结点是结点2i i+1。4 48 89 95 510106 67 72 23 31 16.2 二叉树-性质一、顺序存储结构3 3、二叉树的存储结构、二叉树的存储结构用一组地址连续的存储单元依次用一组地址连续的存储单元依次自上而下、自左至右存储二叉树自上而下、自左至右存储二叉树上的结点元素。上的结点元素。DHIEFGBCA0123456789ABCDEFGHIDFEBCA0123456789ABCDE0000F仅适合于完全二叉树仅适合于完全二叉树对于非完全二叉树：对于非完全二叉树：将各层空缺处全部补上将各层空缺处全部补上“虚结点虚结点”，其内容为，其内容为0 0缺点：缺点：浪费空间；浪费空间；插入、删除不便插入、删除不便 6.2 二叉树-存储结构二叉树的顺序存储表示可描述为：#define MAX_TREE_SIZE 100 /二叉树的最大结点数二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;/0号单元存储根结点号单元存储根结点SqBiTree bt;即将即将 bt 定义为含有定义为含有MAX_TREE_SIZE个个 TElemType 类型元素的一维数组。类型元素的一维数组。二、链式存储结构二叉链表二叉链表中包含中包含2个指针域。个指针域。一般从根结点开始存储。一般从根结点开始存储。DATAPARENT LCHILD RCHILDlchild data rchild lchild data parent rchild 为了便于找到结点的双亲，为了便于找到结点的双亲，可再增加一个双亲域指针，可再增加一个双亲域指针，将二叉链表变成将二叉链表变成三叉链表三叉链表。链表的链表的头指针头指针指向二叉树的根结点。指向二叉树的根结点。6.2 二叉树-存储结构二叉链表类型表述如下：ltypedef struct BiTNode /结点结构l TElemType data;l struct BiTNode *lchild,*rchild;l /左右孩子指针l BiTNode,*BiTree;结点结构结点结构:lchild data rchild结论1：在含有n个结点的二叉链表中有n1个空链域。（提示：n0=n2+1）两个结论两个结论结论2：在含有n个结点的度为k的树中必有n(k-1)+1 个空链域。（结论1的推广）三叉链表类型表述如下：ltypedef struct TriTNode l DataType data;l struct TriTNode*parent;l struct TriTNode*lchild;l struct TriTNode*rchild;lTriTNode,*TriTree;结点结构结点结构:例：例：CEFDBGAABCDEFG A B C D E F G二叉链表三叉链表在含有n个结点的二叉链表中有n+1个空链域空空指针个数：指针个数：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+16.2 二叉树-存储结构1.设T是一棵完全二叉树,则T的根结点的左子树的结点数n与右子树的结点数n的大小关系是。2.一棵深度为6的满二叉树有个叶子和个分支结点。3.设一棵完全二叉树具有36个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。4.一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系：n0=(k-1)*n1+15.一棵二叉树若采用顺序存储结构，存储于数组T中，如下图所示，请画出该二叉树的二叉链表存储形式。1234567891011121314151617181920e a fdgc jh ib课堂练习(二)一、遍历二叉树按某条搜索路径访问树中每个结点，使得每个结点均被按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。访问一次，而且仅被访问一次。v二叉树由根、左子树、右子树构成，三者的组合可构成二叉树由根、左子树、右子树构成，三者的组合可构成6种种 遍历方案：遍历方案：根左右、根右左、左根右、左右根、右根左、右左根根左右、根右左、左根右、左右根、右根左、右左根v若若限定限定“先左后右先左后右”，则有，则有3种实现方案：种实现方案：根左右根左右 左根右左根右 左右根左右根先序遍历 中序遍历 后序遍历6.3 遍历二叉树和线索二叉树DHIFGBCA1、先序遍历2、中序遍历3、后序遍历访问根结点访问根结点先序遍历左子树先序遍历左子树先序遍历右子树先序遍历右子树A BD CFGH I中序遍历左子树中序遍历左子树访问根结点访问根结点中序遍历右子树中序遍历右子树DB A FCHGI后序遍历左子树后序遍历左子树后序遍历右子树后序遍历右子树访问根结点访问根结点DB FHIGC A例1：6.3 遍历二叉树和线索二叉树1、先序遍历2、中序遍历3、后序遍历+*/AB C DEA/B*C*D+EA B/C*D例2：*AB/C*E+D*E+前缀表达式前缀表达式中缀表达式中缀表达式后缀表达式后缀表达式6.3 遍历二叉树和线索二叉树例：例：已知一棵二叉树的中序序列和后序序列分别是已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和和 DECBHGFA，请画出这棵二叉树。请画出这棵二叉树。讨论：若已知若已知先序序列先序序列（或后序序列）和（或后序序列）和中序序列中序序列，能否恢复，能否恢复 出对应的二叉树？出对应的二叉树？分析：分析：由后序遍历特征，由后序遍历特征，根结点必在后序序列尾部根结点必在后序序列尾部（即（即A A）由中序遍历特征，由中序遍历特征，根结点必在其中间，而且其左部必全部是左根结点必在其中间，而且其左部必全部是左子树的子孙子树的子孙（即（即BDCEBDCE），），其右部必全部是右子树的子孙（即其右部必全部是右子树的子孙（即FHGFHG）继而，根据后序中的继而，根据后序中的DECBDECB子树可确定子树可确定B B为为A A的左孩子，根据的左孩子，根据HGFHGF子子串可确定串可确定F F为为A A的右孩子；以此类推的右孩子；以此类推6.3 遍历二叉树和线索二叉树已知中序遍历：已知中序遍历：B D C E A F H G已知后序遍历：已知后序遍历：D E C B H G F A（B D C E）（F H G）A（D C E）BFGHCD EAABC6.3 遍历二叉树和线索二叉树已知先序遍历序列如下：已知先序遍历序列如下：ABDCEFABCEFD6.3 遍历二叉树和线索二叉树二、线索二叉树普通二叉树只能找到结点的左右孩子的信息普通二叉树只能找到结点的左右孩子的信息，而该结点，而该结点的直接前驱和直接后继只能在遍历过程中获得。的直接前驱和直接后继只能在遍历过程中获得。若若将遍历后对应的有关前驱和后继预存起来将遍历后对应的有关前驱和后继预存起来，则从第一，则从第一个结点开始就能很快地遍历整个树了。个结点开始就能很快地遍历整个树了。例如中序遍历结果：例如中序遍历结果：A/B*C*D+E，实际上已将二叉树转为线实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继。性排列，显然具有唯一前驱和唯一后继。如何预存这类信息呢？增加两个域增加两个域:前驱指针、后继指针前驱指针、后继指针利用利用n+1n+1个空链域个空链域6.3 遍历二叉树和线索二叉树规定：规定：1）若结点有左子树，则）若结点有左子树，则lchild指向其左孩子；指向其左孩子；否则，否则，lchild指向其直接前驱（即线索）；指向其直接前驱（即线索）；2）若结点有右子树，则）若结点有右子树，则rchild指向其右孩子；指向其右孩子；否则，否则，rchild指向其直接后继（即线索）；指向其直接后继（即线索）；lchild data rchild约定：约定：当当TagTag域为域为0 0时，表示时，表示孩子孩子情况；情况；当当TagTag域为域为1 1时，表示时，表示线索线索情况。情况。lchild LTag data RTag rchild6.3 遍历二叉树和线索二叉树有关线索二叉树的几个术语：有关线索二叉树的几个术语：线索链表：线索链表：用上述结点构成的二叉链表用上述结点构成的二叉链表 线索：线索：指向前驱和后继结点的指针指向前驱和后继结点的指针 线索二叉树：线索二叉树：同加上线索的二叉树（同加上线索的二叉树（图形式样图形式样）线索化：线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程对二叉树以某种次序遍历使其变为线索二叉树的过程 线索化过程就是在遍历过程中修改空指针的过程：线索化过程就是在遍历过程中修改空指针的过程：将空的将空的lchildlchild改为结点的直接前驱；改为结点的直接前驱；将空的将空的rchildrchild改为结点的直接后继。改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为非空指针呢？仍然指向孩子结点（称为“正常情况正常情况”）6.3 遍历二叉树和线索二叉树例：画出下列二叉树所对应的中序线索二叉树HHI IF FGGB BC CA AD DE E中序遍历结果：中序遍历结果：HDIBE A FCGNILNIL6.3 遍历二叉树和线索二叉树HHI IF FGGB BC CA AD DE ENILNIL 0 1 0 A 0 0 B 0 0 C 0 0 D 0 1 E 1 1 F 1 1 G 1 1 H 1 1 I 1存储结构存储结构6.3 遍历二叉树和线索二叉树中序遍历结果：中序遍历结果：HDIBE A FCG1.设T是具有3个结点的二叉树，且T的后序序列与中序序列相同，则T的形态为。ABCD2.对于前序遍历和后序遍历结果相同的二叉树为。A.一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树3.设n、m为一棵二叉树上的两个结点，在中序遍历中，n在m前的条件是。A.n在m的右面B.n是m的祖先C.n在m的左面D.n在m的子孙课堂练习(三)-+/a*b-efcd4、写出下列二叉树的先序、中序和后序遍历序列，并画出其后序线索二叉树。5、某二叉树前序遍历序列是ABDGCEFH，中序遍历序列是DGBAECHF，请写出其后序遍历结果。课堂练习(三)1.树的存储结构树的存储结构2.森林与二叉树的转换森林与二叉树的转换3.树和森林的遍历树和森林的遍历6.4 树和森林一、一、树的存储结构树的存储结构树有三种常用存储方式：双亲表示法双亲表示法 孩子表示法孩子表示法 孩子兄弟表示法孩子兄弟表示法1、用双亲表示法来存储方法：方法：方法：方法：用一组用一组连续空间连续空间来存储树的结点，同时在来存储树的结点，同时在每个结点中每个结点中附设一个指示器附设一个指示器，指示其双亲结点在，指示其双亲结点在链表中的位置。链表中的位置。6.4 树和森林-树的存储例1：双亲表示法HDEFGBCA双亲表示法缺点：缺点：求结点的孩子时需要遍历整个结构求结点的孩子时需要遍历整个结构01234567DataParentA-1B0C0D1E1F4G4H46.4 树和森林-树的存储2、用孩子表示法来存储方法方法方法方法：将每个结点的将每个结点的孩子孩子排列起来，形成一个排列起来，形成一个带表头带表头（装父亲结（装父亲结点）点）的线性表的线性表（n个结点要设立个结点要设立n个链表），再将个链表），再将n个个表头用数组存表头用数组存放放起来，这样就形成一个起来，这样就形成一个混合结构混合结构。HDEFGBCA孩子表示法 B C A D E B C D F G H E F G H 0 01 12 23 34 45 56 67 76.4 树和森林-树的存储HDEFGBCA带双亲的孩子表示法Parent Data0 01 12 23 34 45 56 67 7ABCDEFGH-10011444 B C D E F G H 6.4 树和森林-树的存储3、用孩子兄弟表示法来存储方法方法方法方法：用用二叉链表二叉链表来存储树，但链表的两个指针域含义不同。来存储树，但链表的两个指针域含义不同。firstchild data nextsibling指向结点的第一个孩子指向结点的第一个孩子指向结点的第一个兄弟指向结点的第一个兄弟HDEFGBCA孩子兄弟表示法ABDCEFGH6.4 树和森林-树的存储二、二、森林与二叉树的转换森林与二叉树的转换转换步骤转换步骤转换步骤转换步骤：结点的第一孩子做为其左孩子结点的第一孩子做为其左孩子 结点的右邻近兄弟做为其右孩子结点的右邻近兄弟做为其右孩子HDEFGBIACA AB BC CI ID DE EF FGGHH二叉树1、树与二叉树的转换6.4 树和森林-树与二叉树的转换2、二叉树与树的转换转换步骤转换步骤转换步骤转换步骤：把所有右孩子都变成其双亲的兄弟把所有右孩子都变成其双亲的兄弟A AB BC CI ID DE EF FGGHHA AB BI IC CD DE EF FHHGG6.4 树和森林-树与二叉树的转换3、森林与二叉树的转换转换步骤转换步骤转换步骤转换步骤：各树要先各自转为二叉树各树要先各自转为二叉树 依次连接到前一个二叉树的右子树上依次连接到前一个二叉树的右子树上BDACIGHJEFA AB BI IF FC CJ JD DE EGGHHI IJ JGGHHF FE EA AB BC CD D6.4 树和森林-森林与二叉树的转换三、树和森林的遍历三、树和森林的遍历1、树的遍历v 先序遍历v 后序遍历 访问根结点访问根结点 依次先序遍历根结点的每棵子树依次先序遍历根结点的每棵子树 依次后序遍历根结点的每棵子树依次后序遍历根结点的每棵子树 访问根结点访问根结点DBEACABCD EBDCEAA AB BC CE ED D先序：先序：中序：中序：后序：后序：ABCDEBDCEADECBA结论：结论：树后序遍历相当于对应二叉树的中序遍历；树后序遍历相当于对应二叉树的中序遍历；树没有中序遍历，因为子树无左右之分。树没有中序遍历，因为子树无左右之分。6.4 树和森林-树的遍历2、森林的遍历v 先序遍历v 中序遍历访问森林中第一棵树的根结点访问森林中第一棵树的根结点先序遍历第一棵树中根结点的子树森林先序遍历第一棵树中根结点的子树森林先序遍历除去第一棵树之后剩余的树构成的森林先序遍历除去第一棵树之后剩余的树构成的森林中序遍历森林中第一棵树的根结点的子树森林中序遍历森林中第一棵树的根结点的子树森林访问第一棵树的根结点访问第一棵树的根结点中序遍历除去第一棵树之后剩余的树构成的森林中序遍历除去第一棵树之后剩余的树构成的森林BDACIGHJEFABCD E FGH I JBCDAFEHJ IG6.4 树和森林-森林的遍历ABCDEFGHIJKLMNO1、写出下列树的先序和后序遍历序列，并将其转换为相应的二叉树。课堂练习(四)2、把如图所示的树转换成二叉树。HHMMI IJ JB BD DA AE EC CF FGGKKL L课堂练习(四)2、把如图所示的森林转换成二叉树。HHI IF FB BD DJ JA AE EC C课堂练习(四)3、把如图所示的二叉树转换成森林。F FHHI IA AGGE ED DC CJ JB B课堂练习(四)一、一、最优二叉树（赫夫曼树）最优二叉树（赫夫曼树）路 径：由一个结点到另一结点间的分支所构成。路径长度：路径上的分支数目。树的路径长度：从根到每一结点的路径长度之和。带权路径长度：结点到根的路径长度与结点上权值的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。赫夫曼树：带权路径长度最小的树。DEFGBCA6.6 赫夫曼树及其应用例：例：三棵二叉树中，三棵二叉树中，4 4个叶子结点个叶子结点a a、b b、c c、d d分别带权分别带权7 7、5 5、2 2、4 4，它们的带权路径长度分别为，它们的带权路径长度分别为?WPL=7*2+5*2+2*2+4*2=36 WPL=7*2+5*2+2*2+4*2=36 WPL=7*3+5*3+2*1+4*2=46 WPL=7*3+5*3+2*1+4*2=46 WPL=7*1+5*2+2*3+4*3=35 WPL=7*1+5*2+2*3+4*3=35abcddabccdba7 77 77 75 55 55 52 22 22 24 44 44 4WPL=WkLknk=1WeightedPathLengthHuffman树6.6 赫夫曼树及其应用二、构造赫夫曼树的基本步骤二、构造赫夫曼树的基本步骤1 1）根据给定的）根据给定的n n个权值个权值1 1，2 2，n n，构成构成n n棵二叉树的棵二叉树的集合集合F=TF=T1 1，T T2 2，T Tn n，其中每棵二叉树其中每棵二叉树T Ti i中只有一个带权为中只有一个带权为i i的根结点，其左右子树均空；的根结点，其左右子树均空；2 2）在）在F F中中选取两棵根结点的权值最小的选取两棵根结点的权值最小的树作为左右子树构造一棵新树作为左右子树构造一棵新的二叉树，且新的二叉树的的二叉树，且新的二叉树的根结点的权值为其左、右子树上根结点根结点的权值为其左、右子树上根结点的权值之和的权值之和；3 3）在）在F F中删除这两棵树，同时中删除这两棵树，同时将新得到的二叉树加入将新得到的二叉树加入F F中中；4 4）重复）重复2 2）和）和3 3），直到），直到F F只含有一棵树为止。只含有一棵树为止。6.6 赫夫曼树及其应用例：例：画出以画出以7 7、5 5、2 2、4 4四个权值构造生成的赫夫曼树。四个权值构造生成的赫夫曼树。7 75 54 42 2步骤步骤2 27 75 5步步骤骤3 37 74 42 26 65 511114 42 26 64 4骤步骤步4 42 26 65 511117 71818步骤步骤1 1一棵有n个叶子结点的赫夫曼树共有2n-1个结点。6.6 赫夫曼树及其应用三、赫夫曼编码三、赫夫曼编码设有电文A B A C C D A 若若0000、0101、1010、1111，则，则00 01 00 10 00 01 00 10 1010 11 00 11 00，总长，总长1414位；位；若若0 0、0000、1 1、0101，则，则0 00 0 1 1 01 00 00 0 1 1 01 0，总长，总长9 9位，但译码时位，但译码时产生二意性。产生二意性。若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，称为前缀编码。6.6 赫夫曼树及其应用c cd db ba a左分支为左分支为0 0右分支为右分支为1 1HuffmanHuffman编码的结果是：编码的结果是：a=0a=0b=10b=10c=110c=110d=111d=111由于赫夫曼树的由于赫夫曼树的WPLWPL最小，说明编码所需要的长度最小。所以，最小，说明编码所需要的长度最小。所以，这种编码已广泛应用于网络通信中。这种编码已广泛应用于网络通信中。设计电文总长度最短的二进制前缀编码即为设计电文总长度最短的二进制前缀编码即为以以n n种字符出现的频率种字符出现的频率作权值，设计一棵赫夫曼树的问题作权值，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码，由此得到的二进制前缀编码便称为赫夫曼编码。便称为赫夫曼编码。6.6 赫夫曼树及其应用例：例：已知某系统在通信联络中只可能出现八种字符，其概率分别为已知某系统在通信联络中只可能出现八种字符，其概率分别为0.070.07，0.190.19，0.020.02，0.060.06，0.320.32，0.030.03，0.210.21，0.100.10，试设计赫夫曼编码。，试设计赫夫曼编码。解：解：先将概率放大先将概率放大100倍，以方便构造赫夫曼树。倍，以方便构造赫夫曼树。权值集合权值集合w=7，19，2，6，32，3，21，102 23 35 56 611117 7101017172828323260601919 2121404010010011010.10010.21111110.03100.3211100.06111100.02000.1911000.07编码频率6.6 赫夫曼树及其应用typedef struct int weight；/权值分量（可放大取整）权值分量（可放大取整）int parent，lchild，rchild；/双亲和孩子分量双亲和孩子分量HTNode，*HuffmanTree；/用动态数组存储用动态数组存储Huffman树树typedef char*HuffmanCode；/动态数组存储动态数组存储Huffman编码表编码表1、Huffman树和树和Huffman树树编码的存储表示：编码的存储表示：四、如何编程实现四、如何编程实现HuffmanHuffman编码？编码？参见教材参见教材P147建议建议1 1：HuffmanHuffman树中结点的结构可设计成树中结点的结构可设计成4 4分量形式：分量形式：rchildlchildparentweight建议建议2 2：HuffmanHuffman树的存储结构可采用顺序存储结构：树的存储结构可采用顺序存储结构：将整个将整个HuffmanHuffman树的结点存储在一个数组树的结点存储在一个数组HT1.n.mHT1.n.m中中;各叶子结点的各叶子结点的编码存储在另一编码存储在另一“复合复合”数组数组HC1.nHC1.n中中指针型指针指针型指针6.6 赫夫曼树及其应用2、先构造、先构造Huffman树树HTVoid HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n)if (n=1)return;m=2*n-1;/n 个叶子的个叶子的HuffmanTree共有共有2n-1个结点；个结点；HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0单元未用单元未用*w存放存放n个字符的权值个字符的权值for(p=HT,i=1;i=n;+i,+p,+w)*p=*w,0,0,0;/初始化前初始化前n个单元个单元for(；i=m;+i,+p)*p=0,0,0,0;/对叶子之后的存储单元清零对叶子之后的存储单元清零for(i=n+1;i=m;+i)/建建Huffman树树(从从叶子开始叶子开始)Select(HT,i-1,s1,s2);/在在HT1i-1选择选择parent为为0且且weight最小的两个结点，其序号分别为最小的两个结点，其序号分别为S1和和s2 HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;6.6 赫夫曼树及其应用3、求出、求出n个字符的个字符的Huffman编码编码HCHC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配分配n个字符编码的头指针个字符编码的头指针 向量（一维数组）向量（一维数组）cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间分配求编码的工作空间(n)cdn-1=0;/编码结束符（从编码结束符（从cd0cdn-1为合法空间）为合法空间）for(i=1;i0)个结点的完全二叉树的深度为。()log2(n)()log2(n)()log2(n)+1()log2(n)+14把一棵树转换为二叉树后，这棵二叉树的形态是。唯一的有多种有多种，但根结点都没有左孩子有多种，但根结点都没有右孩子课堂练习（选择题）5.树是结点的有限集合，它A根结点，记为T。其余的结点分成为m（m0）个B的集合T1，T2，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1im）。一个结点的子结点个数为该结点的C。供选择的答案A：有0个或1个有0个或多个有且只有1个有1个或1个以上B:互不相交允许相交允许叶结点相交允许树枝结点相交C：权维数度序6.在完全的二叉树中，若一个结点没有A，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左孩子是N在原树里对应结点的B，而N的右子女是它在原树里对应结点的C。A:左结点右结点左结点或者没有右结点兄弟BC：最左结点最右结点最邻近的右兄弟最邻近的左兄弟最左的兄弟最右的兄弟课堂练习1.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。2.给定某二叉树的中序序列为B R X S A C U Y V，后序序列为B R S X C U V Y A，试画出该二叉树的结构图。作业(一)3.对所示二叉树进行后序线索化。HHGGE EF FB BC CA AD D作业(一)4.将下列二叉链表改为先序线索链表。ABCDEFGHIJKLMNLtagLchild24607010012130000RtagRchild35008911000140001234 5 6 7 8 91011121314作业(一)abcdefhgi1.写出如图所示树的三种存储结构。作业(二)3.把如图所示的森林分别转换成二叉树。116718352491013141512作业(二)4.把如图所示的二叉树分别转换成树或森林。AABCABCBCADBCAEFIHLGKJ作业(二)1、设给定权值2，3，4，7，8，9，试构造一棵赫夫曼树，并求其加权路径长度WPL。2、已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。作业(三)教学要求：教学要求：1 1、了解树和森林的概念。包括树的定义、树的术语和性质；、了解树和森林的概念。包括树的定义、树的术语和性质；2 2、熟练掌握二叉树的结构特性、遍历方法，熟悉二叉树的各、熟练掌握二叉树的结构特性、遍历方法，熟悉二叉树的各 种存储结构；种存储结构；3 3、熟悉树的各种存储结构及其特点，掌握树、森林与二叉树、熟悉树的各种存储结构及其特点，掌握树、森林与二叉树 的转换方法的转换方法;4 4、掌握建立赫夫曼树和赫夫曼编码的方法及带权路径长度的、掌握建立赫夫曼树和赫夫曼编码的方法及带权路径长度的 计算。计算。第6章 树和二叉树void void Creat_Bintree(BiTreeCreat_Bintree(BiTree&T)&T)char char chch;if(chif(ch=getchargetchar()=#)()=#)T=NULL;T=NULL;else else T=(T=(BiTNodeBiTNode*)*)malloc(sizeof(BiTNodemalloc(siz