二叉树的应用

二叉树的应用1、二叉排序树（二叉查找树）2、最优二叉树（哈夫曼树）请写出上图二叉树的中序遍历序列。1二叉排序树1.1二叉排序树的定义二叉排序树(BinarySortTree)又称二叉查找(搜索)树(BinarySearchTree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；③左、右子树本身又各是一棵二叉排序树。上述性质简称二叉排序树性质(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编程输入一组不同的整数，用二叉排序树排序后按从小到大输出。[参考程序]Programp1_2(Input,Output)；Typetree=^node；node=Recorddata:Integer；lchild,rchild:tree；End；Varbt:tree；n:Integer；1二叉排序树1.3二叉排序树的生成例1.2编程输入一组不同的整数，用二叉排序树排序后按从小到大输出。Procedurecreat_order_tree(Varbtx:tree；nx:Integer)；{排序二叉树的插入}Varp,s,f:tree；flag:Boolean；{标识要插入的数是否在树中出现过，防止同一个数重复出现在树中}BeginNew(s)；s^.data:=nx；s^.lchild:=Nil；s^.rchild:=Nil；{新建一个结点s}flag:=True；{假设没出现过}p:=btx；{P指向根结点}While(pNil)AndflagDo{为结点S找插入位置、同时判断是否出现过}1二叉排序树1.3二叉排序树的生成例1.2编程输入一组不同的整数，用二叉排序树排序后按从小到大输出。Beginf:=p；Ifs^.data=p^.dataThenflag:=False{出现过做标记}ElseIfs^.datap^.dataThenp:=p^.lchild{沿左子树方向找}Elsep:=p^.rchild；{沿由子树方向找}End；IfflagThenBegin{没出现过、且p=Nil说明已找到叶结点了，那么插入到叶结点的左右孩子中}Ifbtx=NilThenbtx:=s；{作为根结点}Ifs^.dataf^.dataThenf^.lchild:=s；{插入左孩子}Ifs^.dataf^.dataThenf^.rchild:=s；{右孩子}End；End；1二叉排序树1.3二叉排序树的生成例1.2编程输入一组不同的整数，用二叉排序树排序后按从小到大输出。Procedureinorder_print(btx:tree)；{递归中序输出}BeginIfbtxNilThenBegininorder_print(btx^.lchild)；{从小到大输出，如果要求从大到小，Write(btx^.data,’‘)；只要先右再左就可以了}inorder_print(btx^.rchild)；End；End；1二叉排序树1.3二叉排序树的生成例1.2编程输入一组不同的整数，用二叉排序树排序后按从小到大输出。Begin{主程序}bt:=Nil；{根结点初始化，不指向任何结点}Writeln(‘inputdata(if0thenover!):’)；Repeat{不断输入正数，不断插入}Read(n)；Ifn=0Thencreat_order_tree(bt,n)；Untiln0；Write(‘outputsorteddata:’)；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二叉排序树的删除Proceduredelnodex(Varbt:tree；x:Integer)；Varp,q,r,t:tree；Beginp:=bt；q:=Nil；While(pNil)And(q^.datax)DoIf(xp^.data)ThenBeginq:=p；p:=p^.lchild；EndElseBeginq:=p；p:=p^.rchild；End；If(p=Nil)ThenWriteln(‘notfound’)ElseIf(p^.lchild=nil)ThenIf(q=Nil)Thent:=p^.rchild删除操作的过程：1二叉排序树1.4二叉排序树的删除ElseIf(q^.lchild=p)Thenq^.lchild:=p^.rchildElseq^.rchild:=p^.rchildElseBeginr:=p^.lchild；While(p^.rchildNil)Dor:=r^.rchild；r^.rchild:=p^.rchild；If(q=Nil)Thent:=p^.lchildElseIf(q^.lchild=p)Thenq^.lchild:=p^.lchildElseq^.rchild:=p^.lchildEnd；End；删除操作的过程：2最优二叉树2.1问题描述及求解方法给定一组数值{w1，w2，……wn}作为叶子结点的权值，构造一棵二叉树。如果∑wiLi最小，则称此二叉树为最优二叉树，也称哈夫曼树。并称∑wiLi为带权路径长度。注意：对于同一组给定叶结点所构造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。2最优二叉树2.1问题描述及求解方法构造最优二叉树算法如下：1、根据给顶的n个权值{w1,w2,w3,……,wn}，构成n棵二叉树的集合T={T1，T2，T3，……，Tn}，其中每个Ti只有一个带权为wi的根结点，其左、右子树均空。2、从T中选两棵根结点的权值最小的二叉树，作为左、右子树构成一棵新的二叉树，并置新二叉树的根值为其左、右子树的根结点的权值之和。3、从T中将刚才所选的两棵二叉树删除，填入新二叉树。4、重复2、3步骤直至T中只有一棵二叉树为止，即得到最优二叉树。2最优二叉树2.1问题描述及求解方法构造最优二叉树算法如下：1、根据给顶的n个权值{w1,w2,w3,……,wn}，构成n棵二叉树的集合T={T1，T2，T3，……，Tn}，其中每个Ti只有一个带权为wi的根结点，其左、右子树均空。2、从T中选两棵根结点的权值最小的二叉树，作为左、右子树构成一棵新的二叉树，并置新二叉树的根值为其左、右子树的根结点的权值之和。3、从T中将刚才所选的两棵二叉树删除，填入新二叉树。4、重复2、3步骤直至T中只有一棵二叉树为止，即得到最优二叉树。2最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树，并计算其带权路径长度。34568101218第一步{}2最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树，并计算其带权路径长度。第二步345681012187{}2最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树，并计算其带权路径长度。第三步56810121811347{}2最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树，并计算其带权路径长度。第四步5681012181134715{}2最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树，并计算其带权路径长度。第五步568101218113471521{}2最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树树，并计算其带权路径长度。第六步18568101211347152127{}2最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树，并计算其带权路径长度。第七步1156810121834715212739}{2最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树，并计算其带权路径长度。第八步568101218113471521273966}{2最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树，并计算其带权路径长度。则带权路径长度WPL为：（3＋4＋5＋6）×4＋（8＋10）×3＋（12＋18）×2＝66＋39＋27＋21＋15＋11＋7＝1862最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树，并计算其带权路径长度。哈夫曼二叉树的过程：Procedurecreatehuffmantree(f,t,a,n){已知n个权值a[i]，构造Vari:Integer；哈夫曼树f，且根结点地址为t}BeginFori:=1TonDoBegin{初始化}f[i].data:=a[i].data；f[i].lchild:=0；f[i].rchild:=0；a[i].addr:=iEnd；t:=n+1；｛t指向下一个可利用单元｝i:=n；｛当前森林中的二叉树是i｝2最优二叉树2.1问题描述及求解方法例2.1以集合{3,4,5,6,8,10,12,18}为叶子结点的权值构造最优二叉树，并计算其带权路径长度。Whilei=2DoBegininsert(a,i)；｛对a的前i个元素按data域进行排序｝f[t].data:=a[1].data+a[2].data；｛生成新的二叉树｝f[t].lchild:=a[1].addr；f[t].rchild:=a[2].addr；a[1].data:=f[t].data；｛修改森林｝a[1].addr:=t；a[