7.6线索二叉树7.6.1线索二叉树的定义对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域。利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。线索二叉树分为先序、中序和后序线索二叉树。对二叉树以某种方式遍历使其变为线索二叉树的过程称为线索化。138
对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域。 利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点 的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。 线索二叉树分为先序、中序和后序线索二叉树。 对二叉树以某种方式遍历使其变为线索二叉树的过程称为线索化。 1/38
图中虚线为线索。先序线索二叉树F二叉树先序序列：ABDCEF2/38
图中虚线为线索。 A B D C E F 二叉树 A B D C E F 先序序列：ABDCEF 先序线索二叉树 2/38
在原二叉链中增加了ltag和rtag两个标志域。表示1child指向结点的左孩子1tag=表示lchild指向结点的前驱结点即为线索表示rchild指向结点的左孩子rtag=表示rchild指向结点的后继结点即为线索ltaglchildrchilddatartag3/38
在原二叉链中增加了ltag和rtag两个标志域。 ltag= 0 表示lchild指向结点的左孩子 1 表示lchild指向结点的前驱结点即为线索 rtag= 0 表示rchild指向结点的左孩子 1 表示rchild指向结点的后继结点即为线索 ltag lchild data rchild rtag 3/38
以中序线索二叉树为例root头结点4/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 头结点
7.6.2线索化二叉树//线索二叉树结点类型class ThNode//存放结点值char data;//左、右孩子或线索的指针ThNode lchild,rchild;/1左、右标志int itag,rtag;1/默认构造方法public ThNode()lchild=rchild=null;ltag=rtag=0;//重载构造方法public ThNode(char d)data=d;lchild=rchild=null;ltag=rtag=0;5/38
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
中序线索化二叉树类Threadclasspublic class Threadclass{ ThNode b;1/二叉树的根结点//线索二叉树的头结点ThNode root;//用于中序线索化，指向中序前驱结点ThNode pre;String bstr;public Threadclass()froot=null;71/中序线索二叉树的基本运算6/38
public class ThreadClass { ThNode b; //二叉树的根结点 ThNode root; //线索二叉树的头结点 ThNode pre; //用于中序线索化,指向中序前驱结点 String bstr; public ThreadClass() { root=null; } //中序线索二叉树的基本运算 } 中序线索化二叉树类ThreadClass 6/38
//建立以root为头结点的中序线索二叉树public void CreateThread()/创建头结点root(root=new ThNode();//头结点域置初值root.ltag=o; root.rtag=1;if (b==null)/ /b为空树时root.lchild=root;root.rchild=null;7else//b不为空树时root.lchild=b;/ /pre是p的前驱结点，用于线索化pre=root;Thread(b);//中序遍历线索化二叉树1/最后处理，加入指向根结点的线索pre.rchild=root;pre.rtag=1;//根结点右线索化root.rchild=pre;7/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
采用中序遍历进行中序线索化在整个算法中p总是指向当前访问的结点，pre指向其前驱结点。pror（b）将结点pre的右空指针改为线索（a）将结点p的左空指针改为线索8/38
∧ pre p (a) 将结点p的左空指针改为线索 ∧ pre p (b) 将结点pre的右空指针改为线索 采用中序遍历进行中序线索化 在整个算法中p总是指向当前访问的结点，pre指向其前驱结点。 8/38
C中序序列：DＧB 个个杯9/38
中序序列： D G B A E C F A B C D E F G 9/38
//对以p为根结点的二叉树进行中序线索化private void Thread(ThNode p){if (p!=null)1//左子树线索化Thread(p.lchild);//前驱线索if (p.lchild==null)/给结点p添加前驱线索p.lchild=pre;p.ltag=1;7else p.ltag=o;if (pre.rchild==null)//给结点pre添加后继线索pre.rchild=p;pre.rtag=1;7else pre.rtag=0;//置p结点为下一次访问结点的前驱结点pre=p;1/右子树线索化Thread(p.rchild);18/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