数据结构导论第四章

复习前节1、数据结构的基本概念2、顺序表、链表3、顺序栈、链栈4、顺序队、链队5、顺序串、链串6、数组和广义表线性表线性表的推广树的推广1数据结构导论第四章共149页，您现在浏览的是第1页!第4章树4.1树的基本概念4.2二叉树4.3二叉树的存储结构4.4二叉树的遍历4.5递归消除4.6树和林4.7判定树和哈夫曼树2数据结构导论第四章共149页，您现在浏览的是第2页!本章项目：电文编码3数据结构导论第四章共149页，您现在浏览的是第3页!文字电文编码电波译码摩尔斯电码（又译为摩斯电码）是一种时通时断的信号代码，这种信号代码通过不同的排列顺序来表达不同的英文字母、数字和标点符号等。它由美国人艾尔菲德·维尔发明（1835年）。4数据结构导论第四章共149页，您现在浏览的是第4页!本章项目：电文编码问题涉及知识点：1、树的概念2、树的专业术语3、二叉树的概念4、哈夫曼树和哈夫曼编码核心问题：如何将电报文字转换成可传送编码5数据结构导论第四章共149页，您现在浏览的是第5页!旋转后6数据结构导论第四章共149页，您现在浏览的是第6页!数据结构中树的形态，具有分层特点ABCDEFGHI7数据结构导论第四章共149页，您现在浏览的是第7页!ABCDEFGHIJKLMNOPQRSTUVWXYZ……..对树中的结点给定一个符号名称，具有一对多的特点8数据结构导论第四章共149页，您现在浏览的是第8页!树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。n>1时，有且仅有一个称为根的结点；其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合又是一棵树，称为子树知识点1：树的概念FGIJABCEDH根根9数据结构导论第四章共149页，您现在浏览的是第9页!结点：数据元素的内容及其指向其子树根的分支结点的度：结点拥有的子树的数目。树的度：树内各结点的度的最大值；知识点2：树的专业术语ABCDEFHGMA、B、C、D、E、F、G、H、M均称为结点A结点的度为2C结点的度为3M结点的度为0树的度为310数据结构导论第四章共149页，您现在浏览的是第10页!结点的层数：树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的高度（深度）：树中所有结点层次的最大值ABCDEFHGM11数据结构导论第四章共149页，您现在浏览的是第11页!路径：若树中存在一个序列k1，k2…kn，使得ki是ki+1的双亲，则称该结点序列为k1到kn的一条路径。路径长度：这些节点经过的边的条数ABCDEFHGM序列：ABDME序列：ABDM序列：ACF是路径非路径是路径12数据结构导论第四章共149页，您现在浏览的是第12页!森林：多棵互不相交的树的集合构成森林ABCDEFHGM三棵树构成的森林13数据结构导论第四章共149页，您现在浏览的是第13页!知识点3：二叉树的概念二叉树(BinaryTree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树同样也都是二叉树ABCDEFHM14数据结构导论第四章共149页，您现在浏览的是第14页!网络信息传输：文字数字编码电信号电文编码发送者数字编码文字电文编码接收者你好0101010101你好核心问题：电文如何编码称为01串？？15数据结构导论第四章共149页，您现在浏览的是第15页!扩展问题：电文传送时的高效性在计算机及通信中，常用二进制编码来表示字符，假设某电文通信中只使用ABCD四个字符每个字母用两位二进制数表示，例如传输100个字母需要用200个二进制位此种编码方式为等长编码，此时电文长度由电文字符数决定对于电文：DABC可翻译为编码：对于编码：01001110可准确翻译为：00表示A01表示B10表示C11表示DBADC1100011016数据结构导论第四章共149页，您现在浏览的是第16页!假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：000011001000考虑问题：出现频率高的字符编码位数少出现频率低的字符编码位数多以此降低电文总长度000表示A001表示B01表示C1表示DA5%B10%C15%D70%假定：问题：传输100个字母所用的二进制位为电文：ACDBA翻译成编码：编码：000011001翻译成电文:3×5+3×10+2×151×70+=145ACDB17数据结构导论第四章共149页，您现在浏览的是第17页!假定：翻译：CBDB翻译：CBDCD新问题2：随意的不等长编码可能导致编码翻译时出现歧义编码：000011001问题：编码是任意给定的吗？000表示A001表示B00表示C1表示D假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：A5%B10%C15%D70%000011001000011001000011001错误！错误！18数据结构导论第四章共149页，您现在浏览的是第18页!知识点4：哈夫曼树与哈夫曼编码树的路径长度：树的根结点到树中每一个结点的路径长度之和。结点的带权的路径长度：该结点到根结点之间的路程长度与该结点上权的乘积路径：若树中存在一个序列k1，k2…kn，使得ki是ki+1的双亲，则称该结点序列为k1到kn的一条路径。路径长度：这些节点经过的边的条数19数据结构导论第四章共149页，您现在浏览的是第19页!树的带权路径长度：树中所有叶子结点的带权的路径长度的和。通常记为：WPL(WeightedPathLength)。树的带权路径长度：4*2+7*3+5*3+2*1dcab247520数据结构导论第四章共149页，您现在浏览的是第20页!abcd7524WPL=7*2+5*2+2*2+4*2=36abcd7524WPL=7*1+5*2+2*3+4*3=35WPL=7*1+4*3+2*3+5*2=35abdc742521数据结构导论第四章共149页，您现在浏览的是第21页!9例如:已知权值W={5,6,2,9,7}构造以权值为叶子的哈夫曼树5627步：把每个权值看作只有一个结点的树22数据结构导论第四章共149页，您现在浏览的是第22页!9例如:已知权值W={5,6,2,9,7}构造以权值为叶子的哈夫曼树5267第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树723数据结构导论第四章共149页，您现在浏览的是第23页!9例如:已知权值W={5,6,2,9,7}构造以权值为叶子的哈夫曼树526771316第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树24数据结构导论第四章共149页，您现在浏览的是第24页!9例如:已知权值W={5,6,2,9,7}构造以权值为叶子的哈夫曼树52677131629第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树构造完成25数据结构导论第四章共149页，您现在浏览的是第25页!假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：A5%B10%C15%D70%0.050.10.150.726数据结构导论第四章共149页，您现在浏览的是第26页!假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：A5%B10%C15%D70%0.050.10.150.70.150.327数据结构导论第四章共149页，您现在浏览的是第27页!项目完成，总结：1，树的概念2，专业术语的定义3，二叉树的概念4，哈夫曼树和哈夫曼编码下节内容：1，二叉树的性质2，二叉树基本操作3，二叉树的应用作业：P996.2128数据结构导论第四章共149页，您现在浏览的是第28页!答案：√一棵树应满足下列条件：（1）有且仅有一个结点没有前驱（双亲）,称该结点为树根;（2）除根结点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继(孩子结点)。判断29数据结构导论第四章共149页，您现在浏览的是第29页!0.10.20.301练习：假设有字符集{A，B，C，D}其在电文中的使用频率分别为{0.1，0.4，0.3，0.2}请给出该字符集中每个字符的哈夫曼编码并将AABCDD电文翻译为哈夫曼编码0.30.6010.4101ADCB编码：A100B0C11D101AABBCDD翻译：100001110110130数据结构导论第四章共149页，您现在浏览的是第30页!4.2二叉树二叉树(BinaryTree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树同样也都是二叉树12345678910111213141531数据结构导论第四章共149页，您现在浏览的是第31页!二叉树的五种形态(a)(b)(c)(d)(e)32数据结构导论第四章共149页，您现在浏览的是第32页!1.一个非空二叉树的第i层上至多有2i-1个结点（i1）证明：i=1,只有根结点，显然成立 设i=k时成立，最多有2k-1个结点 当i=k+1时，最多的结点个数： 2k-1*2=2k-1+1=2k=2(

k+1)-1二叉树的性质12345678910111213141533数据结构导论第四章共149页，您现在浏览的是第33页!3.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设n1为T中度为1的结点数，则总结点数： n=n0+n1+n2(1)另：根据各个结点的前驱和后继情况分支条数=n-1分支条数=n1+2*n2(2)由(1)和(2)有：n1+2*n2=n0+n1+n2-1故n0=n2+1;34数据结构导论第四章共149页，您现在浏览的是第34页!完全二叉树深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树编号从1到n的结点一一对应时，称为完全二叉树。abcdefghij35数据结构导论第四章共149页，您现在浏览的是第35页!4.具有n个结点的完全二叉树的深度:k=log2(n)+1证明：假设n个结点的完全二叉树的深度为k，则n的值应大于深度为k-1的满二叉树的结点数2k-1-1，小于等于深度为k的满二叉树的结点数2k-1，即

2k-1-1<n≤2k-1

进一步可推导出

2k-1≤n<2k两边取对数后，有

k-1≤log2(n)<k进一步可推导出

log2(n)<k≤log2(n)+1因为k是整数，所以有k＝log2(n)+1

36数据结构导论第四章共149页，您现在浏览的是第36页!1.一棵树高为K的完全二叉树至少有（）个结点A.2k–1B.2k-1–1C.2k-1

D.2k习题答案：C37数据结构导论第四章共149页，您现在浏览的是第37页!习题3.有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2答案：B38数据结构导论第四章共149页，您现在浏览的是第38页!二叉树的顺序存储结构整个二叉树可以按照从上到下，从左到右的顺序编号；abcdefghij39数据结构导论第四章共149页，您现在浏览的是第39页!顺序存储结构举例ABCABCØØØØAØBØØØC40数据结构导论第四章共149页，您现在浏览的是第40页!2.链式存储结构二叉链表三叉链表41数据结构导论第四章共149页，您现在浏览的是第41页!ABDCEFADEBCFroot42数据结构导论第四章共149页，您现在浏览的是第42页!ADEBCFroot问题：如何找到某结点的子树？如何找到某结点的双亲？43数据结构导论第四章共149页，您现在浏览的是第43页!三叉链表的定义structbtnode{//结点结构datatypedata;structbtnode*lchild,*rchild}typedefstructbtnode*bitreptr；bitreptr*root;结点结构:lchilddatarchildparent,*parent;;44数据结构导论第四章共149页，您现在浏览的是第44页!4.4二叉树的遍历遍历一棵二叉树是按某种次序系统地“访问”二叉树上的所有结点，使每个结点恰好被“访问”一次。先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法“访问”的含义可以很广，如：输出结点的信息等45数据结构导论第四章共149页，您现在浏览的是第45页!若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：AECBGL46数据结构导论第四章共149页，您现在浏览的是第46页!先（根）序的遍历算法：voidPreorder(bitreptrr){//先序遍历二叉树

if(r！=NULL){visit(r);Preorder(r->lchild);Preorder(r->rchild);

}}AECBGL47数据结构导论第四章共149页，您现在浏览的是第47页!后（根）序的遍历算法：voidPostorder(bitreptrr){//后序遍历二叉树

if(r！=NULL){Postorder(r->lchild);Postorder(r->rchild);visit(r);

}}AECBGL48数据结构导论第四章共149页，您现在浏览的是第48页!遍历举例ABCDEF前序序列：abcdef中序序列：cbefda后序序列：cfedba49数据结构导论第四章共149页，您现在浏览的是第49页!习题2.假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF，请确定一棵二叉树ABDGHCEFIGDHBAECIF前序中序50数据结构导论第四章共149页，您现在浏览的是第50页!习题4.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是()的二叉树A．空或只有一个结点B.高度等于其结点数C．任一结点无左孩子D.任一结点无右孩子先序：根左右后序：左右根答案：B51数据结构导论第四章共149页，您现在浏览的是第51页!树的存储结构ABECDF双亲表示法

孩子链表表示法

孩子兄弟链表表示法

52数据结构导论第四章共149页，您现在浏览的是第52页!孩子兄弟链表表示法两个指针：左孩子指针，右孩子指针53数据结构导论第四章共149页，您现在浏览的是第53页!请画出该树的孩子链表结构图请画出该树的孩子兄弟链表结构图双亲表示法结构图54数据结构导论第四章共149页，您现在浏览的是第54页!树的遍历后序遍历树若树非空，则：（1）依次后序遍历树的棵子树、第二棵子树，……（2）访问树的根结点；55数据结构导论第四章共149页，您现在浏览的是第55页!ABCED前序遍历序列：后序遍历序列：层次遍历序列：ABCDEBCEDAABCDE56数据结构导论第四章共149页，您现在浏览的是第56页!1.树与二叉树的相互转换树转换成的二叉树其右子树一定为空57数据结构导论第四章共149页，您现在浏览的是第57页!森林转换为二叉树58数据结构导论第四章共149页，您现在浏览的是第58页!习题将二叉树转换成树ABCDEFGHIJKLABCDEFGHIJKLCDABCDEFGHIJKLC59数据结构导论第四章共149页，您现在浏览的是第59页!习题设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是()。A.在树T中，X是其双亲的个孩子B.在树T中，X一定无右边兄弟C.在树T中，X一定是叶子结点D.在树T中，X一定有左边兄弟答案：D60数据结构导论第四章共149页，您现在浏览的是第60页!分类与判定树问题：编写程序实现将百分制成绩转换为五级制成绩假设成绩已存入score变量中，转换后等级存入grade变量if(score<60

)grade=“bad”;elseif(score<70)grade=“pass”;elseif(score<80

)grade=“general”;elseif(score<90)grade=“good”;elseif(score<=100)grade=“excellent”;elsegrade=“error”；61数据结构导论第四章共149页，您现在浏览的是第61页!问题：编写程序实现将百分制成绩转换为五级制成绩if(score<60

)grade=“bad”;elseif(score<70)grade=“pass”;elseif(score<80

)grade=“general”;elseif(score<90)grade=“good”;elseif(score<=100)grade=“excellent”;elsegrade=“error”；现实中成绩在五个等级上的分布是不均匀的！！假设分布规律如下：分数0-5960-6970-7980-8990-100比例0.050.150.400.300.1062数据结构导论第四章共149页，您现在浏览的是第62页!假设成绩在五个等级上的分布规律如下：分数0-5960-6970-7980-8990-100比例0.050.150.400.300.100.300.050.400.100.150.300.6010.15先判断是否70-79之间再判断是否80-89后判断是否60-69再判断…63数据结构导论第四章共149页，您现在浏览的是第63页!概念树的路径长度：树的根结点到树中每一个结点的路径长度的和。结点的带权的路径长度：该结点到根结点之间的路程长度与该结点上权的乘积树的带权的路径长度：树中所有叶子结点的带权的路径长度的和。通常记为：WPL(WeightedPathLength)。由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（Huffman）树。64数据结构导论第四章共149页，您现在浏览的是第64页!由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（Huffman）树。abcd7524哈夫曼树的形态是不唯一65数据结构导论第四章共149页，您现在浏览的是第65页!9例如:已知权值W={5,6,2,9,7}562766数据结构导论第四章共149页，您现在浏览的是第66页!95726713例如:已知权值W={5,6,2,9,7}67数据结构导论第四章共149页，您现在浏览的是第67页!957267131629例如:已知权值W={5,6,2,9,7}68数据结构导论第四章共149页，您现在浏览的是第68页!假设成绩在五个等级上的分布规律如下：分数0-5960-6970-7980-8990-100比例0.050.150.400.300.100.300.050.400.100.150.300.6010.15先判断是否70-79之间再判断是否80-89后判断是否60-69再判断…69数据结构导论第四章共149页，您现在浏览的是第69页!A出现的频率为50％B出现的频率为25％C出现的频率为20％D出现的频率为5％用不等长的二进制序列表示字母A、B、C、D使传输的信息的二进制位尽可能少000表示D用001表示C01表示B1表示A传输100个字母所用的二进制位为3×5+3×20+2×25+1×50=175000011001表示什么？2，前缀码三、哈夫曼树的应用DBAC70数据结构导论第四章共149页，您现在浏览的是第70页!利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即：使得所传电文的总长度最短。哈夫曼编码71数据结构导论第四章共149页，您现在浏览的是第71页!2，要求电文总长最短假设每个字符在电文中出现的频率为wi其编码长度为li电文总长：∑wi*li

将wi作为每个叶子节点的权值则∑wi*li是带权路径长度，符合哈夫曼树定义为什么选取哈夫曼编码构造方法72数据结构导论第四章共149页，您现在浏览的是第72页!0.10.20.301例题：假设有字符集{A，B，C，D}其在电文中的使用频率分别为{0.1，0.4，0.3，0.2}请给出该字符集中每个字符的哈夫曼编码并将AABCDD电文翻译为哈夫曼编码0.30.6010.4101ADCB编码：A100B0C11D101AABBCDD翻译：100001110110173数据结构导论第四章共149页，您现在浏览的是第73页!已知一棵二叉树的中根序列和后根序列分别是BDCEAFHG和DECBHGFA，试画出这棵二叉树习题：74数据结构导论第四章共149页，您现在浏览的是第74页!75数据结构导论第四章共149页，您现在浏览的是第75页!实验：将百分制转为五级记分制（要求其算法时间性能尽可能高）ifa<60b=’E’

elseifa<70b=’D’

elseifa<80b=’C’

elseifa<90b=’B’

elseb=’A’;

76数据结构导论第四章共149页，您现在浏览的是第76页!网络信息传输：文字数字编码电信号电文编码发送者数字编码文字电文编码接收者你好0101010101你好核心问题：电文如何编码称为01串？？77数据结构导论第四章共149页，您现在浏览的是第77页!自然中的树抽象的树知识点1：树的概念78数据结构导论第四章共149页，您现在浏览的是第78页!适当进行调整ABCDEFGHI79数据结构导论第四章共149页，您现在浏览的是第79页!某姓氏族谱80数据结构导论第四章共149页，您现在浏览的是第80页!树描述的是一种层次结构，是一种一对多的逻辑关系FGIJABCEDH81数据结构导论第四章共149页，您现在浏览的是第81页!树的其他表示形式ABCDEFHGM82数据结构导论第四章共149页，您现在浏览的是第82页!叶子（终端结点），非终端结点：度为0的结点称为叶子结点；度不为0的结点称为非终端结点。ABCDEFHGM83数据结构导论第四章共149页，您现在浏览的是第83页!孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；双亲在同一层的结点互为堂兄弟。ABCDEFHGMA是B、C的双亲B、C是A的孩子B、C是兄弟关系E、F是堂兄弟关系84数据结构导论第四章共149页，您现在浏览的是第84页!子孙，祖先：以某结点为根的子树中的所有结点都被称为是该结点的子孙。从根结点到该结点路径上的所有结点称为该结点的祖先。ABCDEFHGM85数据结构导论第四章共149页，您现在浏览的是第85页!结点结点的度(Degree)叶子（Leaf)或终端结点分支结点或非终端结点树的度层次(Level)树的深度(Depth)孩子（child)双亲（Parent)兄弟(Sibling)祖先子孙路径ABCDEFHGM86数据结构导论第四章共149页，您现在浏览的是第86页!特征：每个结点最多只有两棵子树子树有左右之分，次序不能任意颠倒，只有一棵子树时也必须分清是左子树还是右子树ABCACB87数据结构导论第四章共149页，您现在浏览的是第87页!项目实现的进一步分析：项目核心问题：如何将电报文字转换成01编码扩展问题：电文传送时的高效性88数据结构导论第四章共149页，您现在浏览的是第88页!实际情况：字符在实际使用中出现频率不一样！新问题1：如何让电文编码缩短为提高电文传送效率，应让电文编码尽量短考虑问题：出现频率高的字符编码位数少出现频率低的字符编码位数多以此降低电文总长度常用汉字6335个，最常用字560个，常用字807个，次常用字1033个，共2400个。这些字占了书刊物汉字出现次数的99%A8.19B1.47C3.83D3.91E12.25F2.26G1.71H4.57I7.10J0.14K0.41L3.77………

前面十位是：ETAOINRSDC89数据结构导论第四章共149页，您现在浏览的是第89页!此种编码方式为不等长编码，采用不等长编码可缩短电文编码长度，从而提高电文传送效率假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：考虑问题：出现频率高的字符编码位数少出现频率低的字符编码位数多以此降低电文总长度000表示A001表示B01表示C1表示DA5%B10%C15%D70%假定：90数据结构导论第四章共149页，您现在浏览的是第90页!新知识：设计不等长编码时，必须做到：任何一个字符的编码不能是另一个字符编码的前缀，这种编码为前缀码新问题2：随意的不等长编码可能导致编码翻译时出现歧义000表示A001表示B01表示C1表示D我们设计的种编码是前缀码新问题3：如何设计前缀码91数据结构导论第四章共149页，您现在浏览的是第91页!知识点4：哈夫曼树与哈夫曼编码树的路径长度：树的根结点到树中每一个结点的路径长度之和。结点的带权的路径长度：该结点到根结点之间的路程长度与该结点上权的乘积树的路径长度：1+1+2+2+3+3结点a的带权路径长度：7*3dcab247592数据结构导论第四章共149页，您现在浏览的是第92页!树的带权路径长度：树中所有叶子结点的带权的路径长度的和。通常记为：WPL(WeightedPathLength)。由n个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最优二叉树，或哈夫曼（Huffman）树。WPL=4*2+7*3+5*3+2*1=46dcab247593数据结构导论第四章共149页，您现在浏览的是第93页!1、根据给定的n个权值{w1,w2,…,wn}，构造n棵只有根结点的二叉树，令其权值为wj;2、在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和;3、从森林中删除这两棵树，同时将新得到的二叉树加入森林中;4、重复上述两步，直到森林中只含一棵树为止，这棵树即哈夫曼树。哈夫曼树的构造方法94数据结构导论第四章共149页，您现在浏览的是第94页!9例如:已知权值W={5,6,2,9,7}构造以权值为叶子的哈夫曼树5267第二步：取权值最小的两棵树，合并成，新树的权值为两棵子树权值之和795数据结构导论第四章共149页，您现在浏览的是第95页!9例如:已知权值W={5,6,2,9,7}构造以权值为叶子的哈夫曼树5267713第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树96数据结构导论第四章共149页，您现在浏览的是第96页!9例如:已知权值W={5,6,2,9,7}构造以权值为叶子的哈夫曼树526771316第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树97数据结构导论第四章共149页，您现在浏览的是第97页!设计电文编码时，随意的不等长编码可能导致编码翻译时出现歧义使用前缀码，可解决不等长编码出现的歧义利用哈夫曼树可构造前缀码构造方法：1，将字符集中的每个字符作为节点2，每个字符的出现频率作为节点的权值3，构造哈夫曼树4，令哈夫曼树中的左分支为0，右分支为1从根到叶子节点的01序列即为叶子节点的编码98数据结构导论第四章共149页，您现在浏览的是第98页!假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：A5%B10%C15%D70%0.050.10.150.70.1599数据结构导论第四章共149页，您现在浏览的是第99页!假定：某电文通信中只由ABCD四个字符构成且出现频率分别为：A5%B10%C15%D70%0.050.10.150.70.150.31ABCD010101A的编码：000B的编码：001C的编码：01D的编码：1电文：DABC编码：100000101每个字符的编码都不是另一字符编码的前缀100数据结构导论第四章共149页，您现在浏览的是第100页!n(n>0)个结点的树的高度:最低是多少？最高是多少？答案：1，n练习ABD101数据结构导论第四章共149页，您现在浏览的是第101页!1、哈夫曼树只有度为0和2的结点，无度为1的结点；2、n个叶子的哈夫曼树的形态一般不唯一，但WPL是相同的；3、n个叶子的哈夫曼树共有2n-1个结点。判断答案：正确102数据结构导论第四章共149页，您现在浏览的是第102页!2009年10月考题：27、由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。103数据结构导论第四章共149页，您现在浏览的是第103页!特征：每个结点最多只有两棵子树子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清是左、右子树。ACBABC104数据结构导论第四章共149页，您现在浏览的是第104页!（1）初始化INITIATE(BT)（2）求根ROOT(BT)（3）求双亲PARENT(BT,x)（4）求左孩子、右孩子Child(BT,x),RChild(BT,x)（5）建树CREAT(x,LBT,RBT)（6）剪枝DELLEFT(BT,x)和DELRIGHT(BT,x)二叉树的基本运算105数据结构导论第四章共149页，您现在浏览的是第105页!2.深度为k的二叉树至多有2k-1个结点(k1)

证明：二叉树的结点个数为： 1+2+…+2k-1=2k-1123456789101112131415106数据结构导论第四章共149页，您现在浏览的是第106页!考虑到有序性，任一结点在树中都有确切的位置，因此可以对满二叉树进行编号。编号方式为：从上到下，从左到右。满二叉树深度为k且有2k-1个结点的二叉树123456789101112131415107数据结构导论第四章共149页，您现在浏览的是第107页!1.满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。(√)2.满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。

(√)判断题108数据结构导论第四章共149页，您现在浏览的是第108页!（a）如果i=1,此结点为根结点，无双亲；若i>1,则其双亲结点是i/2。（b）如果2i>n,则结点i无左孩子，i为叶子结点,否则其左孩子是结点2i。（c）如果2i+1>n，则结点i无右孩子，否则其右孩子是结点2i+1。5.如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,3,…,n,则对任一结点i（1in）有abcdefghij109数据结构导论第四章共149页，您现在浏览的是第109页!2.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。习题结点总个数n=2+3+4+x前驱后继n-1=2*1+3*2+4*3故x=12答案：12110数据结构导论第四章共149页，您现在浏览的是第110页!4.3二叉树的存储结构顺序存储结构链式存储结构111数据结构导论第四章共149页，您现在浏览的是第111页!1．顺序存贮结构将一棵二叉树按完全二叉树顺序存放到一维数组中abcdefghm123456789101112131415

0123456789101112131415abcdefghm112数据结构导论第四章共149页，您现在浏览的是第112页!对于一棵二叉树,若采用顺序存贮时,当它为完全二叉树时,比较方便;若为非完全二叉树,将会浪费大量存贮单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。113数据结构导论第四章共149页，您现在浏览的是第113页!二叉树的链式存储结构二叉链表lchilddatarchilddatalchildrchild114数据结构导论第四章共149页，您现在浏览的是第114页!二叉链表的定义structbtnode{//结点结构datatypedata;structbtnode*lchild,*rchild;}typedefstructbtnode*bitreptr；bitreptr*root;结点结构:lchilddatarchild115数据结构导论第四章共149页，您现在浏览的是第115页!三叉链表lchilddatarchildparentADEBCFroot116数据结构导论第四章共149页，您现在浏览的是第116页!链式存储的缺点；

若一棵二叉树有n个结点,采用二叉链表作存贮结构时,共有2n个指针域,其中只有n-1个指针指向左右孩子,其余n+1个指针为空,没有发挥作用。117数据结构导论第四章共149页，您现在浏览的是第117页!若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：AECBGL118数据结构导论第四章共149页，您现在浏览的是第118页!若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：AECBGL119数据结构导论第四章共149页，您现在浏览的是第119页!中（根）序的遍历算法：voidInorder(bitreptrr){//中序遍历二叉树

if(r！=NULL){Inorder(r->lchild);visit(r);Inorder(r->rchild);

}}AECBGL120数据结构导论第四章共149页，您现在浏览的是第120页!二叉树的遍历算法：AECBGLDLRLDR、LRD、DLR121数据结构导论第四章共149页，您现在浏览的是第121页!习题1.给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是LRNB.NRLC.RLND.RNL答案：D122数据结构导论第四章共149页，您现在浏览的是第122页!习题8.试找出满足下列条件的二叉树1）先序序列与中序序列相同2）中序序列与后序序列相同3）先序序列与后序序列相同答案1）不含左子树的二叉树2）不含右子树的二叉树3）空二叉树或只含根结点的二叉树123数据结构导论第四章共149页，您现在浏览的是第123页!4.6树和林考虑存储结构时，主要考虑逻辑结构：数据元素数据元素之间的关系124数据结构导论第四章共149页，您现在浏览的是第124页!孩子链表表示法顺序存储结点+链式存储孩子结构；找孩子容易，找双亲难；01234567125数据结构导论第四章共149页，您现在浏览的是第125页!双亲表示法树的双亲表示法主要描述的是结点的双亲关系顺序表示，存放顶点和双亲信息126数据结构导论第四章共149页，您现在浏览的是第126页!树的遍历前序遍历树若树非空，则：（1）访问树的根结点；（2）依次前序遍历树的棵子树、第二棵子树，……127数据结构导论第四章共149页，您现在浏览的是第127页!树的遍历层次遍历树1）访问树的根结点；2）依次前序遍历树的层结点、第二结点，……128数据结构导论第四章共149页，您现在浏览的是第128页!森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟树、森林与二叉树的关系树与二叉树的相互转换森林与二叉树的相互转换129数据结构导论第四章共149页，您现在浏览的是第129页!2.森林与二叉树的相互转换130数据结构导论第四章共149页，您现在浏览的是第130页!森林转换为二叉树131数据结构导论第四章共149页，您现在浏览的是第131页!DEFGHIJLABCKFILCABEGHJKD习题二叉树到森林的转换132数据结构导论第四章共149页，您现在浏览的是第132页!4.7判定树和哈夫曼树分类与判定树哈夫曼树与哈夫曼算法133数据结构导论第四章共149页，您现在浏览的是第133页!程序已写出，但是此种判定形式是否最好呢？从何角度考虑程序是否最优？问题：编写程序实现将百分制成绩转换为五级制成绩if(score<60

)grade=“bad”;elseif(score<70)grade=“pass”;elseif(score<80

)grade=“general”;elseif(score<90)grade=“good”;elseif(score<=100)grade=“excellent”;elsegrade=“error”；134数据结构导论第四章共149页，您现在浏览的是第134页!假设成绩在五个等级上的分布规律如下：if(score<60

)grade=“bad”;elseif(score<70)gr