《管理学六树》PPT课件.ppt

树的概念、表示形式、存储结构 森林的存储结构 二叉树的概念、表示、遍历 二叉树的计数 霍夫曼树,第六章 树与二叉树,6.1 树的基本概念,树的定义 树是由n (n 0)个结点组成的有限集合。如果n = 0，称为空树；如果n 0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； 除根以外的其它结点划分为m (m 0)个互不相交的有限集合T0, T1, , Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,结点(node) 分支(branch)结点 叶(leaf)结点 子女(child)结点 双亲(parent)结点 兄弟(sibling)结点,祖先(ancestor)结点 子孙(descendant)结点 结点的度(degree) 树的度(degree) 结点所处层次(level) 树的深度(depth),树的表示形式,树形图表示 嵌套集合表示 凹入表/书目表表示,A- B- E- F- J- K- C-,G- D- H- I-,树的存储结构（1）,双亲表示法,树的存储结构（2）,孩子表示法,双亲孩子表示法,树的存储结构（3）, 孩子兄弟表示法,任何一棵树的孩子兄弟表示法，其右子树必空。,树的存储结构（4）,6.2 二叉树 (Binary Tree),二叉树的定义,二叉树的五种不同形态,一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,性质1 一棵非空二叉树的第i层上至多有2i1个结点（i1）。 性质2 深度为k的二叉树至多有2k1个结点（k1）。 性质3 对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。,二叉树的性质,证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1,定义1 满二叉树(Full Binary Tree) 深度为k的且有 2k+1-1个结点的二叉树称为满二叉树。 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的深度为h，则共有h+1层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。,性质4 具有n个结点的完全二叉树，其深度为log2n+1。 其中x是向下取整符号，表示不大于x的最大整数。 x 是向上取整符号，表示不小于x的最小整数。,二叉树的性质,性质5 对于具有n个结点的完全二叉树，如果按照从上到下、同一层次上的结点按从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于序号为i的结点有： 1）如果i1，则结点i的双亲是结点i/2；如果i1，则结点i为二叉树的根，没有双亲。 2）如果2in，则结点i无左子女（此时结点i为终端结点）；否则其左子女为结点2i。 3）如果2i+1n，则结点i无右子女；否则其右子女为结点2i1。,完全二叉树的数组表示 一般二叉树的数组表示,二叉树的表示,数组表示,单支树,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。,struct node /二叉树结点的类型 struct node *lchild; /存储左孩子结点位置 typedef data; /数据域 struct node *rchild; /存储右孩子结点位置 ,二叉链表表示,三叉链表表示,struct node /二叉树结点的类型 struct node *lchild; /存储左孩子结点位置 typedef data; /数据域 struct node *rchild; /存储右孩子结点位置 struct node *parent; /存储双亲结点位置 ,二叉树链表表示的示例,二叉树链表表示的示例,二叉树链表表示的示例,二叉树遍历 (Binary Tree Traversal),所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有,前序 DLR 镜像 DRL 中序 LDR 镜像 RDL 后序 LRD 镜像 RLD,前序遍历 (Preorder Traversal),前序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 访问根结点 (D)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f,表达式语法树,算法实现：二叉树的创建,struct tree * creat() char c; struct tree * t; c=getchar(); if(c= ) t=NULL; else t=(struct tree *)malloc(LEN); /创建新结点 t-data=c; t-lchild=creat(); /递归建立左子树 t-rchild=creat(); /递归建立右子树 return t; /返回头结点 ,以前序次序ABCDE建立二叉树，如图所示。,算法实现： 前序遍历（1）,/前序遍历二叉树的递归算法 void preorder(bintree t) if (t) printf(“%c“,t-data); preorder(t-lchild); preorder(t-rchild); ,算法实现：前序遍历（2）,/非递归实现二叉树的前序遍历 void preorder1(bintree t) seqstack s; s.top=-1; while (t)|(s.top!=-1) /当前处理的子树不为空或栈不为空则循环 while (t) printf(“%c “,t-data); s.top+; s.datas.top=t; t=t-lchild; if (s.top-1) t=pop( ,中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (D)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f,中序遍历 (Inorder Traversal),表达式语法树,算法实现：中序遍历（1）,/中序遍历二叉树的递归算法 void inorder(bintree t) if(t) inorder(t-lchild); printf(“%c“,t-data); inorder(t-rchild); ,中序遍历 中序遍历与后序遍历走过的路线一样，只是在从左子树退出后立即访问根结点，再遍历右子树。 中序遍历也要使用一个递归工作栈。,算法实现：中序遍历（2）,void inorder1(bintree t) /非递归实现二叉树的中序遍历 seqstack s; s.top=-1; while(t!=NULL) | (s.top!=-1) while (t) push( ,后序遍历 (Postorder Traversal),后序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (D)。 遍历结果 a b c d - * + e f / -,表达式语法树,为记忆走过的结点，设置一个工作栈： PopTim = 0, 1或2，表示第几次退栈，用以判断下一步向哪一个方向走。,后序遍历时，每遇到一个结点，先把它推入栈中，让PopTim=0。在遍历其左子树前，改结点的PopTim=1，将其左子女推入栈中。在遍历完左子树后，还不能访问该结点，必须继续遍历右子树，此时改结点的PopTim=2，并把其右子女推入栈中。在遍历完右子树后，结点才退栈访问。,请写出后序遍历的算法（递归与非递归算法）,层次遍历 从根开始逐层访问， 用FIFO队列实现。,遍历顺序,树的遍历,先根次序遍历：先访问树的根结点，然后依次 先根遍历根的每棵子树 后根次序遍历：先依次后根遍历每棵子树，然 后访问根结点,先根序列：A B C D E,后根序列：B C E D A,求出该树的先根序列和后根序列。,先根序列：ABCEIJFGKHD,后根序列：BIJEFKGHCDA,森林的遍历,森林的二叉树表示,(1) 先序遍历的规则： 若森林F为空, 返回；否则 访问F的第一棵树的根结点； 先根次序遍历第一棵树的根结点的子树森林； 先根次序遍历其它树组成的森林。,先序遍历时结点的访问序列：A B C D E F G H I K J,森林的遍历,森林的二叉树表示,(2) 中序遍历的规则： 若森林F为空，返回；否则 中根次序遍历第一棵树的根结点的子树森林； 访问F的第一棵树的根结点； 中根次序序遍历其它树组成的森林。,中根遍历时结点的访问序列：B C E D A G F K I J H,森林的遍历,森林的二叉树表示,(3) 广度优先遍历(层次序遍历) ： 若森林F为空，返回；否则 依次遍历各棵树的根结点； 依次遍历各棵树根结点的所有子女； 依次遍历这些子女结点的子女结点。,层次序遍历时结点的访问序列：A F H B C D G I J E K,二叉树的计数,问题： n 个数据值，可能构造多少种不同的二叉树？,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,二叉树的计数,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,若研究 n 个数据值可能构造多少种不同的二叉树？我们可以固定前序排列，选择所有可能的中序排列。,如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。,例如，有 3 个数据 1, 2, 3 ，可得5种不同的二叉树。它们的前序排列均为 123，中序序列可能是 123，132，213，231，321。,有0个, 1个, 2个, 3个结点的不同二叉树如下,计算具有n个结点的不同二叉树的棵数,例如，具有4个结点的不同二叉树,Catalan函数,问题的提出,6.5 哈夫曼编码及其应用,电子期刊、网络音乐、网络电影,数据存储的压力,数据通信的压力,大数据量,计算机处理的压力,数据压缩是关键。压缩的关键在于编码。,教学目的,本节课的教学目的是在研究编码的要求和原理的基础上，学习一种被广泛应用而且高效的编码方法哈夫曼编码。,6.5 哈夫曼编码及其应用,电话号码是一种常用的编码,澳门,62551234,0086,106,027,重拨,一、编码的要求,电话编码不当闹笑话,？,编码,解码,一个集合中任一编码不能 是另一编码的前半部分， 即前缀编码。,编码要求1,62551234,0086,106,027,1234,0086,10,60276255,一、编码的要求,大陆编码,0086,00853,澳门编码,变长编码，使用次数越多 的编码越短，使电文总长 度最短。,编码要求2,大陆有13亿人口,澳门有53万人口,一、编码的要求,前缀编码,编码要求1,二进制编码,编码要求3,电文总长度最短,编码要求2,一、编码的要求,二、哈夫曼编码,哈夫曼编码是一种效率高、运算速度快的编码方法，根据待压缩数据的特征，压缩率可达到20%-90%。 许多知名的压缩工具和压缩算法里（如WinZip和JPEG），都有哈夫曼编码的身影。,David A. Huffman （ 19251999）,二、哈夫曼编码,1950年，哈夫曼（Huffman）在MIT(麻省理工)的研究生班学习。范诺（Fano）教授让学生们自己决定是参加期未考试还是做一个大作业。哈夫曼选择了后者，这个大作业促使了后来哈夫曼算法的诞生。 1952年，范诺提出了范诺编码，该编码可以取得一定的压缩效果，但是离真正实用的压缩算法还相去甚远。 同年，哈夫曼提出了哈夫曼编码，这是第一个真正实用的编码方法。,David A. Huffman （ 19251999）,要理解哈夫曼编码，先要理解 （一）哈夫曼树的定义 （二）如何构造哈夫曼树 （三）如何构造哈夫曼编码,二、哈夫曼编码,（一）哈夫曼树的定义,例1：一个数据文件仅包含字符a, b, c, d, 字符的权值分别为6, 4, 1, 2，可构造如下一棵二叉树。,结点的带权路径长度：结点的路径长度与该结点权值的乘积。,结点的路径长度：从根结点到该结点的路径上分支的数目。,（一）哈夫曼树的定义,在所有含 n 个叶子结点、并带相同权值的二叉树中，带权路径长度取最小值的二叉树，即最优二叉树，又称哈夫曼树。,树的带权路径长度：树中所有叶子结点的带权路径长度之和。,WPL =6+4*2+(1+2)*3=23,WPL =1+2*2+(4+6)*3=35,例1：字符a, b, c, d分别带权6, 4, 1, 2, 可构造出如下三棵二叉树(还有许多棵)，它们的WPL分别为：,WPL =(6+4+1+2)*2=26,（二）构造哈夫曼树,构造哈夫曼树的原理 权值越大的叶子结点离根越近 权值越小的叶子结点离根越远,（二）构造哈夫曼树,构造哈夫曼树的方法 (1) 初始化 (2) 选择与合并 (3) 删除与加入 (4) 重复2，3直到F中只有一棵树。,（二）构造哈夫曼树,例2：假设有一个包含1 000 000个字符的数据文件仅包含字符a-e，每个字符出现的频度如下表中所示。请构造哈夫曼树。,（二）构造哈夫曼树,（二）构造哈夫曼树,(1)初始化：根据给定的n个权值wl，w2，wn构成n棵二叉树的森林F=T1，T2，Tn，其中每棵二叉树Ti中都只有一个权值为wi的根结点。,（二）构造哈夫曼树,(2)选择与合并：从F中选根权最小的两棵二叉树Ti和Tj，分别作为左右子树，根结点r的权为wi+wj 。,13,T1,T2,T3,T4,T5,（二）构造哈夫曼树,(3)删除与加入：从F中删除Ti和Tj ，新的树加入F。,13,T1,T2,T3,T4,T5,（二）构造哈夫曼树,13,T1,T2,T3,T4,(3)删除与加入：从F中删除Ti和Tj ，新的树加入F。,（二）构造哈夫曼树,(4) 重复2，3 直到F中只有一棵树。,13,T1,T2,T3,T4,（二）构造哈夫曼树,25,13,(4) 重复2，3 直到F中只有一棵树。,T1,T2,T3,（二）构造哈夫曼树,(4)重复