河池学院：《数据结构》课程电子教案（PPT教学课件）第7章 树和二叉树 7.6 线索二叉树 7.7 哈夫曼树 7.8 二叉树与树、森林之间的转换

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域。 利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点 的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。 线索二叉树分为先序、中序和后序线索二叉树。 对二叉树以某种方式遍历使其变为线索二叉树的过程称为线索化。 1/38

图中虚线为线索。 A B D C E F 二叉树 A B D C E F 先序序列：ABDCEF 先序线索二叉树 2/38

在原二叉链中增加了ltag和rtag两个标志域。 ltag= 0 表示lchild指向结点的左孩子 1 表示lchild指向结点的前驱结点即为线索 rtag= 0 表示rchild指向结点的左孩子 1 表示rchild指向结点的后继结点即为线索 ltag lchild data rchild rtag 3/38

A B C D E F G 以中序线索二叉树为例 4/38 1 A 1 1 B 1 1 C 1 1 D 1 1 G 1 1 E 1 1 F 1 0 1 root 头结点

class ThNode //线索二叉树结点类型 { char data; //存放结点值 ThNode lchild,rchild; //左、右孩子或线索的指针 int ltag,rtag; //左、右标志 public ThNode() //默认构造方法 { lchild=rchild=null; ltag=rtag=0; } public ThNode(char d) //重载构造方法 { data=d; lchild=rchild=null; ltag=rtag=0; } } 5/38

public class ThreadClass { ThNode b; //二叉树的根结点 ThNode root; //线索二叉树的头结点 ThNode pre; //用于中序线索化,指向中序前驱结点 String bstr; public ThreadClass() { root=null; } //中序线索二叉树的基本运算 } 中序线索化二叉树类ThreadClass 6/38

public void CreateThread() //建立以root为头结点的中序线索二叉树 { root=new ThNode(); //创建头结点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; //根结点右线索化 } } 7/38

∧ pre p (a) 将结点p的左空指针改为线索 ∧ pre p (b) 将结点pre的右空指针改为线索 采用中序遍历进行中序线索化 在整个算法中p总是指向当前访问的结点，pre指向其前驱结点。 8/38

中序序列： D G B A E C F A B C D E F G 9/38

private void Thread(ThNode p) //对以p为根结点的二叉树进行中序线索化 { if (p!=null) { Thread(p.lchild); //左子树线索化 if (p.lchild==null) //前驱线索 { p.lchild=pre; //给结点p添加前驱线索 p.ltag=1; } else p.ltag=0; if (pre.rchild==null) { pre.rchild=p; //给结点pre添加后继线索 pre.rtag=1; } else pre.rtag=0; pre=p; //置p结点为下一次访问结点的前驱结点 Thread(p.rchild); //右子树线索化 } } 10/38