《算法与数据结构树与二叉树.pptx》由会员分享，可在线阅读，更多相关《算法与数据结构树与二叉树.pptx（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、先序遍历（DLR）先序遍历函数的遍历过程：若二叉树为空，则空操作；否则：1）先访问树T的根结点；2）先序遍历T的左子树；3）先序遍历T的右子树；二叉树ABFDGIEHCJ第1页/共28页先序遍历 1）A (AL)(AR)二叉树ABFDGIEHCJ B (BL)(BR)C (CL)(CR)(NULL)(NULL)D (DL)(DR)E(EL)(ER)(NULL)(NULL)(NULL)ABCDEFGHIJ第2页/共28页先序遍历算法（DLR）void preorder(bitree *root)bitree *p；p=root if(T!=NULL)printf(“%d”,p-data);pre
2、order(p-lchild);preorder(p-rchild);二叉树第3页/共28页先序遍历（DLR）则先序遍历的结果二叉树-+/*efb-acd-+a*b-cd/ef第4页/共28页中序遍历（LDR）中序遍历函数的遍历过程：若二叉树为空，则空操作；否则：1）中序遍历T的左子树；2）访问T的根结点；3）中序遍历T的右子树；二叉树ABFDGIEHCJ第5页/共28页中序遍历 (TL)A (TR)二叉树ABFDGIEHCJTT1T11T12T121T2T21T22T212T221(T1L)B (T1R)(T11L)C(T11R)(NULL)(NULL)CCBB(T12L)D(T12R)D(
3、T121L)E(T121R)E(NULL)(NULL)E(NULL)DAAGHFJI第6页/共28页中序遍历算法（LDR）void inorder(bitree *root)bitree *p;p=root;if(p!=NULL)inorder(p-lchild);printf(“%d”,p-data);inorder(p-rchild);二叉树第7页/共28页中序遍历（LDR）则中序遍历的结果：二叉树-+/*efb-acd第8页/共28页后序遍历（LRD）后序遍历函数的遍历过程：若二叉树为空，则空操作；否则：1）后序遍历T的左子树；2）后序遍历T的右子树；3）访问T的根结点；二叉树ABFDG
4、IEHCJ第9页/共28页后序遍历二叉树ABFDGIEHCJTT1T11T12T121T2T21T22T212T221 (T1)(T2)A(T11)(T12)B(T111)(T112)C(NULL)(NULL)CC(T121)(T122)D(T1211)(T1212)E(NULL)(NULL)EE(NULL)DDBBHGJIFA第10页/共28页后序遍历算法 void postorder(bitree *root)bitree*p；p=root if(p!=null)postorder(p-lchild);postorder(p-rchild);printf(“%d”,p-data);二叉树第
5、11页/共28页则先序遍历的结果:二叉树-+/*efb-acd-+a*b-cd/ef则后序遍历的结果:则中序遍历的结果:a+b*c-d-e/fabcd-*+ef/-第12页/共28页二叉树v例 已知某二叉树先序遍历的结果：abcdefghij，中序遍历的结果：cdbfeaihgj，此二叉树的结构？a b c d e f g h i jc d b f e a i h g jabcdefgihj第13页/共28页设计算法，按先序次序统计二叉树中叶子结点的个数 void CountLeaf(bitree T,int count)if(T)if(!T-lchild)&(!T-rchild)count+
6、;CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);二叉树遍历算法的应用第14页/共28页设计算法，按中序次序输出二叉树T中度为2的结点的值 此问题的思考方法要求用中序遍历的思想来完成，但是和中序遍历不同的是要求仅输出度为2的结点的值，所以将中序遍历算法中的访问结点的操作改为条件输出结点的值即可。void inorder(bitree *root)bitree *p=root;if(p!=NULL)inorder(p-lchild);if(p-lchild!=null&p-rchild!=null)printf(“%d”,p-data);i
7、norder(p-rchild);二叉树遍历算法的应用第15页/共28页设计算法，求二叉树T的结点数 int inorder(bitree *root)bitree *p=root;int n=0;if(p!=NULL)inorder(p-lchild);n+;inorder(p-rchild);return n;二叉树遍历算法的应用第16页/共28页遇到问题的思考方法 一般来说，当遇到问题时可以用二叉树遍历的思想来思考。描述如下：1）如果T为空，则按预定功能实现对空树的操作。2）否则，假设算法对T的左、右子树都能分别实现预定功能，在此基础上，通过按预定要求适当调用对左、右子树的算法的功能，及
8、对当前结点的操作实现对整个二叉树的功能。二叉树遍历思想的应用第17页/共28页求解给定二叉树的高度 分析：1）如果T为空，则树的高度为0。2）否则，其高度应是其左右子树高度的最大值再加一（假设其左右子树的最大高度能求出来）。算法：int high(Bnode *T)if(T=NULL)return 0;else return max(high(T-lchild),high(T-rchild)+1;二叉树遍历思想的应用第18页/共28页哈夫曼树哈夫曼树最优树路径长度丛树中一个结点到另一个结点之间的分支构成这两个节点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一个结点之间的路
9、径长度之和。树的带权路径长度树中的叶子结点为带权叶子结点，结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。bacd7524dc4ab752ab57cd24ABCA WPL=7*2+5*2+2*2+4*2=36B WPL=4*2+7*3+5*3+2*1=46C WPL=7*1+5*2+2*3+4*3=35第19页/共28页哈夫曼树哈夫曼树最优二叉树 在解决某些问题时，利用哈夫曼树可以得到最佳判定算法。例如要编制一个将百分制转换成等级制的算法。if(a60)printf(“不及格”);else if(a70)printf(“及
10、格”);else if(a80)printf(“中等”);else if(a90)printf(“良好”);else printf(“优秀”);分制比例数0590.0560690.1570790.4080890.30901000.10 要注意对于解决此问题的算法需要重复使用，所以需要考虑算法的质量问题，即其操作所需时间问题。在实际生活中，学生的成绩程正态分布，大部分同学处于7090之间。哈夫曼树又叫做最优二叉树，是n个带权叶子结点构成的所有二叉树中，带全路径长度（WPL）最小的二叉树。第20页/共28页哈夫曼树哈夫曼树最优二叉树a60a70a80a90不及格及格中等良好优良a80a70a60a
11、60良好优良中等及格不及格第21页/共28页哈夫曼树哈夫曼算法 1）根据给定的n 个权值w1,w2,wn，构造成n棵二叉树的集合F=T1,T2,Tn，其中每个Ti只有一个带权为wi的根结点，其左右子树均为空。（一般要求Wi权值升序排列）2）从F中选两棵根结点的权值最小的二叉树作为左右子树构成一棵二叉树（Tn,Tm），并且置新二叉树的根值为其左右子树的根结点的权值之和。3）将新的二叉树并入到F中（按照升序序列），同时上述 Tn,Tm删除掉。4）重复 2），3）部，直到T中只有一棵树为止。第22页/共28页哈夫曼树哈夫曼算法 给定4个数：7，5，2，4。第23页/共28页哈夫曼树分制比例数不及格0
12、.05及格0.15中等0.40良好0.30优秀0.10优秀不及格15及格 30中等 良好 6070=a8080=a9060=a7090=a第24页/共28页哈夫曼算法的应用哈夫曼编码 例：已知一个文件中仅有8各不同的字符，各字符出现的个数分别为是0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11。试重新为各字符编码，以节省存储空间。问题：1）要实现压缩编码，即根据字符的出现次数的多少来给出字符的编码的长短，出现次数多编码短。2）对于每个字符的编码要不同。解决此问题可以借助哈夫曼算法来完成。第25页/共28页哈夫曼算法的应用 1）根据给出的权值(5,29,7,8,14,23,3,11)，构造哈夫曼树。29100154229192383511147858第26页/共28页0哈夫曼算法的应用 1）根据给出的权值(5,29,7,8,14,23,3,11)，构造哈夫曼树。2）设根结点的编码为空，然后从根结点开始依次对各个结点进行编码：左孩子编码为0，右孩子编码为1。291001542291923835111478581000000111111第27页/共28页感谢您的观看！第28页/共28页