中序线索化二叉树类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