数据基础教程24

7.6.1线索二叉树的定义7.6线索二叉树对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域。利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。线索二叉树分为先序、中序和后序线索二叉树。对二叉树以某种方式遍历使其变为线索二叉树的过程称为线索化。1/38图中虚线为线索。ABDCEF二叉树ABDCEF先序序列：ABDCEF先序线索二叉树2/38在原二叉链中增加了ltag和rtag两个标志域。ltag=0表示lchild指向结点的左孩子1表示lchild指向结点的前驱结点即为线索rtag=0表示rchild指向结点的左孩子1表示rchild指向结点的后继结点即为线索ltaglchilddatarchildrtag3/38ABCEFDG以中序线索二叉树为例4/38A00B10C00D01G11E11F1110root头结点7.6.2线索化二叉树classThNode{

//线索二叉树结点类型chardata; //存放结点值ThNodelchild,rchild; //左、右孩子或线索的指针intltag,rtag; //左、右标志publicThNode(){ //默认构造方法lchild=rchild=null;ltag=rtag=0;}publicThNode(chard){ //重载构造方法data=d;lchild=rchild=null;ltag=rtag=0;}}5/38publicclassThreadClass{ThNodeb; //二叉树的根结点

ThNoderoot;

//线索二叉树的头结点

ThNodepre;

//用于中序线索化,指向中序前驱结点Stringbstr;publicThreadClass(){root=null;}//中序线索二叉树的基本运算}中序线索化二叉树类ThreadClass6/38publicvoidCreateThread(){ //建立以root为头结点的中序线索二叉树root=newThNode(); //创建头结点rootroot.ltag=0;root.rtag=1; //头结点域置初值if(b==null){ //b为空树时root.lchild=root;root.rchild=null;}else{ //b不为空树时root.lchild=b;pre=root;

//pre是p的前驱结点,用于线索化

Thread(b);

//中序遍历线索化二叉树pre.rchild=root; //最后处理,加入指向根结点的线索pre.rtag=1;root.rchild=pre; //根结点右线索化}}7/38∧prep(a)将结点p的左空指针改为线索∧prep(b)将结点pre的右空指针改为线索采用中序遍历进行中序线索化在整个算法中p总是指向当前访问的结点，pre指向其前驱结点。8/38中序序列：DGBAECFABCEFDG9/38privatevoidThread(ThNodep){//对以p为根结点的二叉树进行中序线索化if(p!=null){Thread(p.lchild); //左子树线索化if(p.lchild==null){ //前驱线索p.lchild=pre; //给结点p添加前驱线索p.ltag=1;}elsep.ltag=0;if(pre.rchild==null){pre.rchild=p; //给结点pre添加后继线索pre.rtag=1;}elsepre.rtag=0;pre=p; //置p为下一次访问结点的前驱结点

Thread(p.rchild); //右子树线索化}}10/387.6.3遍历线索化二叉树在该线索二叉树中实现中序遍历的两个步骤是：

（1）求中序序列的开始结点：实际上该结点就是根结点的最左下结点。

（2）对于一个结点p，求其后继结点的过程是：

①如果p结点的rchild指针为线索，则rchild所指为其后继结点。

②否则p结点的后继结点是其右孩子q的最左下结点post。b………p根结点p………postpost结点为q结点的最右下结点q11/38publicvoidThInOrder(){ //中序线索二叉树的中序遍历ThNodep=root.lchild; //p指向根结点while(p!=root){while(p!=root&&p.ltag==0) //找中序开始结点p=p.lchild;System.out.print(p.data+""); //访问p结点while(p.rtag==1&&p.rchild!=root){p=p.rchild; //如果是线索，一直找下去System.out.print(p.data+"");//访问p结点}p=p.rchild; //如果不再是线索，转向其右子树}}该算法是一个非递归算法，算法的时间复杂度为O(n)，空间复杂度为O(1)12/387.7.1哈夫曼树的定义7.7哈夫曼树应用中常给树中的结点赋上一个有着某种意义的数值—权。从树根结点到某个结点之间的路径长度与该结点权的乘积称为结点的带权路径长度。一棵二叉树树中所有叶子结点的带权路径长度之和称为该树的带权路径长度，通常记为：在n0个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树（或最优二叉树）。13/38给定4个叶子结点，设其权值分别为1、3、5、7，形状不同的4棵二叉树。164121357（a）16971835（b）1615127135（c）16941753（d）（a）WPL=1×2+3×2+5×2+7×2=32（b）WPL=1×2+3×3+5×3+7×1=33（c）WPL=7×3+5×3+3×2+1×1=43（d）WPL=1×3+3×3+5×2+7×1=29√14/387.7.2哈夫曼树的构造算法

（1）根据给定的n0个权值W=(w1，w2，…，wn0)，对应结点构成n0棵二叉树的森林T=(T1，T2，…，Tn0)，其中每棵二叉树Ti（1≤i≤n0）中都只有一个带权值为wi的根结点，其左、右子树均为空。

（2）在森林T中选取两棵结点的权值最小的子树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根的权值之和。称为合并，每合并一次T中减少一棵二叉树。

（3）重复（2）直到T只含一棵树为止。这棵树便是哈夫曼树。15/38W=(1，3，5，7)来构造一棵哈夫曼树16941753（d）1357（a）45713（b）941753（c）16/38定理7.3对于具有n0个叶子结点的哈夫曼树，共有2n0-1个结点。证明：从哈夫曼树的构造过程看出，每次合并都是将两棵二叉树合并为一个，所以哈夫曼树不存在度为1的结点，即n1=0。

由二叉树的性质1可知n0=n2+1，即n2=n0-1

则结点总数n=n0+n1+n2=n0+n2=n0+2n0-1=2n0-1。17/38

构造哈夫曼树中采用静态数组ht存储哈夫曼树，即每个数组元素存放一个结点。设计哈夫曼树中结点类如下：classHTNode{ //哈夫曼树结点类chardata; //结点值,假设为单个字符doubleweight; //权值publicHTNodeparent; //双亲结点HTNodelchild; //左孩子结点HTNoderchild; //右孩子结点booleanflag; //标识是双亲的左或者右孩子publicHTNode(){ //构造方法parent=null;lchild=null;rchild=null;}publicdoublegetw(){ //取结点权值的方法returnweight;}}18/38dataweightlchildrchildparentflag结点：i413210aba,1,null,null,2,trueb,3,null,null,2,false*,4,0,1,null,*19/38publicclassHuffmanClass

//哈夫曼树类{finalintMAXN=100; //最多结点个数double[]w; //权值数组Stringstr; //存放字符串intn0; //权值个数

HTNode[]ht;

//存放哈夫曼树String[]hcd;

//存放哈夫曼编码publicHuffmanClass(){ //构造方法ht=newHTNode[MAXN];hcd=newString[MAXN];w=newdouble[MAXN];}publicvoidSetdata(intn0,double[]w,Stringstr){//设置初始值this.n0=n0;for(inti=0;i<n0;i++)this.w[i]=w[i];this.str=str; }publicvoidCreateHT(){…} //构造哈夫曼树publicvoidCreateHCode(){…} //根据哈夫曼树求哈夫曼编码publicvoidDispHuffman(){…} //输出哈夫曼编号}哈夫曼树类HuffmanClass20/38publicvoidCreateHT(){

//构造哈夫曼树Comparator<HTNode>priComparator

//定义priComparator=newComparator<HTNode>(){publicintcompare(HTNodeo1,HTNodeo2){//用于创建小根堆return(int)(o1.getw()-o2.getw());//按weight越小越优先

}};PriorityQueue<HTNode>pq=newPriorityQueue<>(MAXN,priComparator);

//定义优先队列for(inti=0;i<n0;i++){ //建立n0个叶子结点并进队ht[i]=newHTNode(); //建立ht[i]结点ht[i].parent=null; //双亲设置为空ht[i].data=str.charAt(i);ht[i].weight=w[i];pq.offer(ht[i]); //进队}ht[0..n0-1]存放叶子结点21/38for(inti=n0;i<(2*n0-1);i++){ //n0-1次合并操作HTNodep1=pq.poll(); //出队两个权值最小的结点p1和p2HTNodep2=pq.poll();ht[i]=newHTNode(); //建立ht[i]结点p1.parent=ht[i];

//设置p1和p2的双亲为ht[i]p2.parent=ht[i];

ht[i].weight=p1.weight+p2.weight;//求权值和ht[i].lchild=p1;

//p1作为双亲ht[i]的左孩子

p1.flag=true;

ht[i].rchild=p2;

//p2作为双亲ht[i]的右孩子

p2.flag=false;pq.offer(ht[i]); //ht[i]结点进队}}产生ht[n0..2n0-2]的n0-1个分支结点22/387.7.3哈夫曼编码构造一棵哈夫曼树。规定哈夫曼树中的左分支为0，右分支为1。从根结点到每个叶子结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。16941753abcd010011a:000b:001c:01d:1哈夫曼编码的实质就是使用频率越高的采用越短的编码。23/38privateStringreverse(Strings){ //逆置字符串sStringt="";for(inti=s.length()-1;i>=0;i--)t+=s.charAt(i);returnt;}

只有ht[0..n0-1]叶子结点才对应哈夫曼编码，用hcd[i]（0≤i≤n0-1）表示ht[i]叶子结点的哈夫曼编码。24/38publicvoidCreateHCode(){ //根据哈夫曼树求哈夫曼编码for(inti=0;i<n0;i++){ //遍历下标从0到n0-1的叶子结点hcd[i]="";HTNodep=ht[i]; //从ht[i]开始找双亲结点while(p.parent!=null){if(p.flag) //p结点是双亲的左孩子hcd[i]+='0';else //p结点是双亲的右孩子hcd[i]+='1';p=p.parent;}System.out.println("hcd:"+hcd[i]);hcd[i]=reverse(hcd[i]); //逆置得到正向的哈夫曼编码}}叶子结点ht[0..n0-1]向根结点的方向求编码，再逆置25/38输出所有叶子结点的哈夫曼编码的算法publicvoidDispHuffman()

//输出哈夫曼编码{for(inti=0;i<n0;i++)System.out.println(ht[i].data+""+hcd[i]);}26/38提个醒在一组字符的哈夫曼编码中，任一字符的哈夫曼编码不可能是另一字符哈夫曼编码的前缀。6．5个字符有如下4种编码方案，不是前缀编码的是（）。A．01,0000,0001,001,1B．011,000,001,010,1C．000,001,010,011,100D．0,100,110,1110,11002014年全国硕士研究生入学统一考试题示例27/387.8.1树到二叉树的转换及还原7.8二叉树与树、森林之间的转换一棵树二叉树转换还原28/381.树到二叉树的转换加线：在各兄弟结点之间加一连线，将其隐含的“兄－弟”关系以“双亲－右孩子”关系显示表示出来。抹线：对任意结点，除了其最左子树之外，抹掉该结点与其他子树之间的“双亲－孩子”关系。调整：以树的根结点作为二叉树的根结点，将树根与其最左子树之间的“双亲－孩子”关系改为“双亲－左孩子”关系，且将各结点按层次排列，形成二叉树。一棵树可以按照以下规则转换为二叉树：29/38A（a）一棵树BCDEFGHIA（b）加线BCDEFGHIA（c）抹线BCDEFGHIA（d）调整BCDEFGHI转换成的二叉树特点根结点只有左子树而没有右子树。左分支不变（左分支为最左孩子），兄弟变成右分支（右分支实为双亲的兄弟）。30/38A一棵树BCDEFGHIA二叉树BCDEFGHI树中分支结点个数为m，则二叉树中无右孩子的结点个数为m+1。这里m=4。扩展31/382.一棵由树转换的二叉树还原为树加线：在各结点的双亲与该结点右链上的每个结点之间加一连线，以“双亲－孩子”关系显示表示出来。抹线：抹掉二叉树中所有双亲结点与其右孩子之间的“双亲－右孩子”关系。调整：以二叉树的根结点作为树的根结点，将各结点按层次排列，形成树。一棵二叉树（由一棵树转换的）可以按照以下规则还原为一棵树：32/38（a）一棵二叉树ABCDEFGHI（b）加线ABCDEF