二叉树的应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,二叉树的应用,1,、二叉排序树（二叉查找树）,2,、最优二叉树（哈夫曼树）,请写出上图二叉树的中序遍历序列。,1,二叉排序树,1.1,二叉排序树的定义,二叉排序树,(Binary Sort Tree),又称二叉查找,(,搜索,),树,(Binary Search Tree),。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：,若它的左子树非空，则左子树上所有结点的值,均小于根结点的值；,若它的右子树非空，则右子树上所有结点的值,均大于根结点的值；,左、右子树本身又各是一棵二叉排序树。上述性质简称二叉排序树性质,(BST,性质,),，故二叉排序树实际上是满足,BST,性质的二叉树。,1,二叉排序树,1.2,二叉排序树的特点,（,1,）二叉排序树中任一结点,x,，其左,(,右,),子树中任一结点,y(,若存在,),的关键字必小,(,大,),于,x,的关键字。（,2,）二叉排序树中，各结点关键字是惟一的。,注意,：实际应用中，不能保证被查找的数据集中,各元素的关键字互不相同，所以可将二叉排序树,定义中,BST,性质,(1),里的,“,小于,”,改为,“,大于等于,”,，或,将,BST,性质,(2),里的,大于,改为,小于等于,，甚至可同时修改这两个性质。（,3,）按中序遍历该树所得到的中序序列是一个递增有序序列。,1,二叉排序树,1.2,二叉排序树的特点,例,1.1 (1),输入序列,:5,，,7,，,3,，,4,，,2,，,8,构造,排序,二叉树，写出中序遍历序列；,(2),输入序列,:2,，,3,，,7,，,5,，,8,，,4,构造,排序,二叉树，写出中序遍历序列。,二叉排序树的构造,1,二叉排序树,1.2,二叉排序树的特点,二叉排序树的示例,输入序列决定了二叉排序树的形态。,1,二叉排序树,1.3,二叉排序树的生成,由输入实例,(5,，,3,，,7,，,2,，,4,，,8),，根据生成二叉排序树算法生成二叉排序树的过程。,动画演示,1,二叉排序树,1.3,二叉排序树的生成,如图所示的二叉排序树，中序遍历结果为：,5,，,6,，,8,，,9,，,10,，,11,，,13,，,14,，,15,，,17,。,如何生成这样一棵二叉树呢？,例,1.2,编程输入一组不同的整数（约定大于等于,0,，输入负数表示结束），用二叉排序树排序后按从小到大输出。,问题分析,图,1,先生成一个结点，再根据大小决定这个结点是插在左子树上还是右子树上，如此重复直到输入一个负数。,1,二叉排序树,1.3,二叉排序树的生成,例,1.2,编程输入一组不同的整数，用二叉排序树排序后按从小到大输出。,参考程序,Program p 1_2(Input,Output),；,Type tree=node,；,node=Record,data:Integer,；,lchild,rchild:tree,；,End,；,Var,bt:tree,；,n:Integer,；,1,二叉排序树,1.3,二叉排序树的生成,例,1.2,编程输入一组不同的整数，用二叉排序树排序后按从小到大输出。,Procedure,creat_order_tree(Var,btx:tree,；,nx:Integer,),；,排序二叉树的插入,Var,p,s,f:tree,；,flag:Boolean,；,标识要插入的数是否在树中出现过，防止同一个数重复出现在树中,Begin,New(s,),；,s.data,:=,nx,；,s.lchild,:=Nil,；,s.rchild,:=Nil,；,新建一个结点,s flag:=True,；,假设没出现过,p:=,btx,；,P,指向根结点,While(pNil)And flag Do ,为结点,S,找插入位置、同时判断是否出现过,1,二叉排序树,1.3,二叉排序树的生成,例,1.2,编程输入一组不同的整数，用二叉排序树排序后按从小到大输出。,Begin f:=p,；,If,s.data,=,p.data,Then flag:=False ,出现过做标记,Else If,s.data,p.data,Then p:=,p.lchild,沿左子树方向找,Else p:=,p.rchild,；,沿由子树方向找,End,；,If flag Then Begin ,没出现过、且,p=Nil,说明已找到叶 结点了，那么插入到叶结点的左右孩子中,If,btx,=Nil Then,btx,:=s,；,作为根结点,If,s.data,f.data,Then,f.rchild,:=s,；,右孩子,End,；,End,；,1,二叉排序树,1.3,二叉排序树的生成,例,1.2,编程输入一组不同的整数，用二叉排序树排序后按从小到大输出。,Procedure,inorder_print(btx:tree,),；,递归中序输出,BeginIf,btx,Nil Then Begin,inorder_print(btx.lchild,),；,从小到大输出，如果要求从大到小，,Write(btx.data,),；只要先右再左就可以了,inorder_print(btx.rchild,),；,End,；,End,；,1,二叉排序树,1.3,二叉排序树的生成,例,1.2,编程输入一组不同的整数，用二叉排序树排序后按从小到大输出。,Begin ,主程序,bt,:=Nil,；,根结点初始化，不指向任何结点,Writeln(input,data(if,=0 Then,creat_order_tree(bt,n,),；,Until n0,；,Write(output,sorted data:),；,inorder_print(bt,),；,Writeln,；,End.,1,二叉排序树,1.4,二叉排序树的删除,二叉排序树的删除与普通树及一般二叉树的删除有所不同，因为它要保证所有结点按中序遍历后仍然有序输出，所以，删除二叉树,bt,中一个数据域为,x,的结点的过程如下：,1,首先查找到数据域为,X,的结点,P,；,2,若结点,P,没有左子树，则用右子树的根代替被删除的结点；,3,若结点,P,有左子树，则在其左子树中找到最右结点,R,，将,P,的右子树置为,R,的右子树，再将,P,的左子树的根结点代替被删除的结点,P,。,如图,1,中，删除数据域为,10,的结点变成图,2,左边的,A,图，删除数据,1,二叉排序树,1.4,二叉排序树的删除,Procedure,delnodex(Var,bt:tree,；,x:Integer,),；,Var,p,q,r,t:tree,；,Begin,p:=,bt,；,q:=Nil,；,While(pNil)And(,q.data,x)Do,If(x=2 Do Begin,insert(a,i,),；对,a,的前,i,个元素按,data,域进行排序,ft.data,:=a1.data+a2.data,；生成新的二叉树,ft.lchild,:=a1.addr,；,ft.rchild,:=a2.addr,；,a1.data:=,ft.data,；修改森林,a1.addr:=t,；,a2.data:=,ai.data,；修改森林,a2.addr:=,ai.add,；,i:=i-1,；二叉树数目减一,t:=t+1,；,End,；,End,；,2,最优二叉树,2.2,应用实例,哈夫曼编码,利用,哈夫曼树构造的二进制编码为哈夫曼编码。,也称为二进制前缀编码。,哈夫曼,(Huffman),编码利用码字出现的频率差异而设计的长度不等的编码。频率高的字母码长较短一些，而频率低的字母码长一些，是数字压缩大最低程度。,编码规则：,对哈夫曼树，根结点的编码为空，从根结点开始，每个结点的左孩子的编码是其父结点的编码后添加,0,，而右孩子的编码是其父结点的编码后添加,1,。,2,最优二叉树,2.2,应用实例,哈夫曼编码,例,2.2,如图是,5,个叶子结点的二叉树，每一结点对应一个码字（,00,，,01,，,10,，,110,，,111,）。,编码后添加,1,。,0,1,0,1 0 1,00 01 10 ,000 111,例,2.3,已知一个文件中仅有,8,个不同的字符，各字符出现的个数分别是,3,、,4,、,8,、,10,、,16,、,18,、,20,、,21,。试重新为各字符编码，以节省存储空间。,2,最优二叉树,2.2,应用实例,哈夫曼编码,（,1,）以频率为权值构造哈夫曼树。,（,2,）进行哈夫曼编码。,100,59,41,25,34,15,10,8,7,4,3,18,16,21,20,1,0,00,01,000,0000,00000,00001,0001,001,010,011,10,11,文件长度为,WPL,值，即：,(3,4)5,84,(10,16,18)3,(20,21)2,281,1,、铲雪车,2,、单词查找树,3,、合并果子,练习,练习,1,：铲雪车问题,问题描述,大雪履盖了整个城市，市政府要求冬季服务部门尽快将一些街道（列在一份清单中）的积雪清除掉以恢复交通，整个城市由许多交叉路口和街道构成，当然任意两个交叉路口都是直接或间接连通的，清单给出了最少的街道，使得这些街道的积雪清除后任意两个交叉路口之间有且仅有一条通路，冬季服务部门只有一辆铲雪车及一名司机，这辆铲雪车的出发点位于某个交叉路口。,无论街道上有没有积雪，铲雪车每前进一米都要消耗一升燃料，冬季服务部门要求司机在铲除清单上的所有街道的积雪的前提下，要求消耗燃料最少，积雪铲完后车可以停在任意的交叉路口。,输入格式,输入文件名为,one.in,，第一行包含两个整数,N,和,S,，,1N100000,，,1SN,。,N,为交叉路口的总数；,S,为铲雪车出发的路口序号。路口的标号为,1N,。,接下来的,N-1,行为清单上的街道，每一行包含三个用空格隔开的整数,A,、,B,、,C,，表示一条从交叉路口,A,到交叉路口,B,的街道，,C,为该街道的长度，单位为米，,1C1000,。,输出格式,输出文件名为,one.out,，仅一行包含一个整数表示清除所有积雪所需的最少的燃料数量。,样例输入,5 1,1 2 8,1 3 10,3 4 10,4 5 7,样例输出,43,问题分析,在树的基本概念中，我们知道“一棵树中的任意两个不同结点之间一定存在着一条唯一的路径，不论是直接的或间接的。图论意义上的路径概念”。在本题中，我们把每个路口作为一个结点的话，则整个街道就是一棵树，而且铲雪车出发点正好就是树根，而题目中“任意两个交叉路口之间有且仅有一条通路”这个条件正好符合上述概念。所以本题就变成了一个树的遍历问题，只不过是一个“加权树,权为街道的长度、也即清除本街道积雪所需要的燃料数量”，而且满足“每条边至少被访问一次”和“权的和最小”。对于上述的样例，我们可以画出如图,6_20,所示的树型结构，现在的问题就转变成“求遍历整棵树中的所有结点的权值之和的最小值”，这个问题结果等价于,total*2-maxt,，其中,total=,整棵树的权值之和；,maxt,=,根结点深度遍历到每个叶结点的权值之和的最大值”，如样例中,total=8+10+10+7=35,，,maxt,=max8,10+10+7=27,，所以结果为,35*2-27=43,。,数据结构方面：因为本题的树型结构是多叉树，而且结点数目巨大，存储和操作起来都很麻烦，所以我们把它转换成二叉树的形式。而且处理时没有用邻接矩阵的方法，而是转换成类似于稀疏矩阵的存储方法,。,