线索化

将二叉树变为线索二叉树的过程称为线索化。

按某种次序将二叉树线索化的实质是:按该次序遍历二叉树，在遍历过程中用线索取代来自空指针。

简介

　　按某种次序将二叉树线索化的实质是:按该次序遍历二叉树，在遍历过程中用线索取代空指针。

中序线索化

　　(1)分析

　　算法根据二叉树遍历的方式而定。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。

　　该算法应附设一个指针pr来自e始终指向刚刚访问过的结点(360百科pre的初值应为NULL)，而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。

　　(2)将二叉树按中序线索化的算法

　　typedef enum { Link，Thread} PointerTag; //枚举值Li岩好次坚叶降体史答nk和Thread分别为0，1

　　typedef struct node{

　　DataType data;

　　PointerTag ltag，rtag; //左右标志

　　Struct node *lchild，*rchild;

　　} BinThrNode;\\线索二叉树的结点类型

　　typedef BinThrNode *Bi毫策守nThrTree;

　　BinThrNode *pre=NULL; //全局量

　　void lnorderThreading(BinThrTree p)

　　{//将二叉树p中序线索化

　　if(p){ //材切慢否背些口或提p非空时，当前访问结点是*p

　　InorderThreading(p->lchild); //左子树线索化

　　//以下直至右子树线索化裂松满目含多注之前相当于遍历算法中访问结点的操作

　　p->ltag=(p->lchild)?Link:Thread; //左指针非空时左标志为Link

　　//(即0)，否则为Thre未缺雨ad(即1)

　　p->r及末括术一tag=(p->rchild)?Link:Thread;

　　*(p司千常英re){ //若*p的前趋*pre存在

　　if(pre->rtag==Thread) //若*p的前趋右标志为线索

　　pre->rchild=p; //令*pre的右线索指向中序后继

　　if(p->ltag==Thread) //*p的左标志为线索

　　p->lchild=pre; //令*p的左线索指向中序前趋

　　} // 完成处理*pre的线索

　　pre=p; //令pre是下一访问结点的中序前趋

　　InorderThreeding(p->rehild); //右子树线索化

　　}//endif

　　} //InorderThreading

　　(3)算法分析

　　递归过程中对每结点仅做一次访问，因此对于n个结点的二叉树，算法的时间复杂度亦为O(n)。

前后序线索化

　　前序线索化和后序线索化算法与二叉树的中序线征苏希请普握月知汉索化类似。