7.6.3遍历线索化二叉树在该线索二叉树中实现中序遍历的两个步骤是：（1）求中序序列的开始结点：实际上该结点就是根结点的最左下结点。（2）对于一个结点p，求其后继结点的过程是：如果p结点的rchild指针为线索，则rchild所指为其后继结点。福否则p结点的后继结点是其右孩子g的最左下结点post。根结点post结点为q结点的最右下结点pos11/38
在该线索二叉树中实现中序遍历的两个步骤是： （1）求中序序列的开始结点：实际上该结点就是根结点的最左下结点。 （2）对于一个结点p，求其后继结点的过程是： ① 如果p结点的rchild指针为线索，则rchild所指为其后继结点。 ② 否则p结点的后继结点是其右孩子q的最左下结点post。 b . . . p 根结点 p . . . post post结 点为q结 点的最右 下结点 q 11/38
public void ThInorder()1/中序线索二叉树的中序遍历//p指向根结点ThNode p=root.lchild;while (p!=root)t1/找中序开始结点while(p!=root&&p.ltag==o)p=p.lchild;1/访问p结点System.out.print(p.data+"");while(p.rtag==1&&p.rchild!=root)//如果是线索，一直找下去{ p=p.rchild;1/访间p结点System.out.print(p.data+"");7//如果不再是线索，转向其右子树p=p.rchild;该算法是一个非递归算法，算法的时间复杂度为0(n），空间复杂度为0（1）12/38
public void ThInOrder() //中序线索二叉树的中序遍历 { ThNode p=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/38
哈夫曼树7.77.7.1哈夫曼树的定义应用中常给树中的结点赋上一个有着某种意义的数值-权。从树根结点到某个结点之间的路径长度与该结点权的乘积称为结点的带权路径长度。一棵二叉树树中所有叶子结点的带权路径长度之和称为该树的带权no路径长度WPL=Wixli，通常记为：=1在ne个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树（或最优二叉树）。13/38
应用中常给树中的结点赋上一个有着某种意义的数值—权。 从树根结点到某个结点之间的路径长度与该结点权的乘积称为结点 的带权路径长度。 一棵二叉树树中所有叶子结点的带权路径长度之和称为该树的带权 路径长度 ，通常记为： 在n0个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小 的二叉树称为哈夫曼树（或最优二叉树）。 13/38