第7章树和二叉树（5）.pptx

7.6.1线索二叉树的定义;图中虚线为线索。;在原二叉链中增加了ltag和rtag两个标志域。;;7.6.2线索化二叉树;publicclassThreadClass

{ThNodeb; //二叉树的根结点

ThNoderoot; //线索二叉树的头结点

ThNodepre; //用于中序线索化,指向中序前驱结点

Stringbstr;

publicThreadClass()

{

root=null;

}

//中序线索二叉树的基本运算

};publicvoidCreateThread() //建立以root为头结点的中序线索二叉树

{root=newThNode(); //创建头结点root

root.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; //根结点右线索化

}

};;中序序列：DGBAECF;privatevoidThread(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); //右子树线索化

}

};7.6.3遍历线索化二叉树;publicvoidThInOrder() //中序线索二叉树的中序遍历

{ThNodep=root.lchild; //p指向根结点

while(p!=root)

{

while(p!=rootp.ltag==0) //找中序开始结点

p=p.lchild;

System.out.print(p.data+); //访问p结点

while(p.rtag==1p.rchild!=root)

{p=p.rchild; //如果是线索，一直找下去

System.out.print(p.data+); //访问p结点

}

p=p.rchild; //如果不再是线索，转向其右子树

}

};7.7.1哈夫曼树的定义;给定4个叶子结点，设其权值分别为1、3、5、7，可以构造出形状不同的4棵二叉树。;7.7.2哈夫曼树的构造算法;W=(1，3，5，7)来构造一棵哈夫曼树;定理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。;构造哈夫曼树中采用静态数组ht存储哈夫曼树，即每个数组元素存放一个结点。设计哈夫曼树中结点类如下：;data;publicclassHuffmanClass //哈夫曼树类

{finalintMAXN=100; //最多结点个数

double[]w; //权值数组

Stringstr; //存放字符串

intn0; //权值个数

HTNode[]ht;