学步园

二叉树(n个节点)有2n个指针域、n-1个分支，故有n+1个空指针域：空指针域=2n个指针域-(n-1个分支). 线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继;
空指针域如果为左指针域则应将其指向该节点的前驱、左标志域更新为线索化标志thread;空指针域如果为右指针域则应将其指向该节点的后继、右标志域更新为线索化标志。前驱与后继具体是谁与线索化的方式有关、如果按照先序线索化图1二叉树那么节点C、D、F、G的左指针域为空则应将他们的左指针域分别指向B、C、E、F；节点B、D、F、G的右指针域为空则应将他们的右指针域分别指向C、E、G、Thrt(见图2).因此线索化的过程即为在遍历过程中修改空指针的过程.

                         图1图2

typedef  char PointerTag;
typedef enum PointerTag
{
	link,
	thread;
};
typedef struct ThBTNode
{
   ELEMTYPE data; 	    //节点数据域
   PointerTag lTag;         //左右节点标志域
   PointerTag rTag;
   struct ThBTNode *pLNode; //左右节点指针
   struct ThBTNode *pRNode;
}ThBTNode,*pThBTNode;

下面详细介绍先序线索化二叉树的函数实现：

pThBTNode PreOrderThreadingBTree(pThBTNode pT)
{
	void PreOrderThreading(pThBTNode pT,pThBTNode& pPreNode);
	pThBTNode pThrt = new ThBTNode;	//创建线索化二叉树头节点、其中数据域存放的是垃圾数据
	pThBTNode	pPreNode;//刚刚访问过的节点指针
	if(NULL == pThrt)
	{
		return NULL;
	}
	else
	{
		pThrt->lTag = link;//线索化二叉树头节点的左标志域初始化为孩子标志	
		pThrt->rTag = thread;//线索化二叉树头节点的右标志域初始化为后继标志	
		pThrt->pRNode = pThrt;//线索化二叉树头节点的后继初始化其本身
		if(NULL == pT)//原二叉树根节点为空
		{
		    pThrt->pLNode = pThrt;//线索化二叉树头节点的左指针域指向其本身
		}
		else//原二叉树根节点非空
		{
		    pThrt->pLNode = pT;	//线索化二叉树左指针域指向原二叉树根节点				
		    pPreNode = pT;		//刚刚访问过的节点指针指向为原二叉树根节点
		    PreOrderThreading(pT,pPreNode);//按照先序方法将原二叉树变成线索化二叉树
		    pPreNode->rTag = thread;//刚刚访问过的节点（此时为原二叉树最右下方的分支节点）的右标志域赋值为后继标志					
		    pPreNode->pRNode = pThrt;//刚刚访问过的节点（此时为原二叉树最右下方的分支节点）的后继是线索化二叉树根节点
		    pThrt->pRNode = pPreNode;//线索化二叉树头节点的后继应指向刚刚访问过的节点
		}
	}
	return pThrt;//将原二叉树变成线索化二叉树成功、返回线索化二叉树头节点
}

首先创建线索化二叉树头节点Thrt(其指针为pThrt)，如果原二叉树为空的话其左指针域指向自己，否则指向原二叉树根节点T，将原二叉树根节点赋给PreNode.然后就通过函数void PreOrderThreading(pThBTNode pT,pThBTNode& pPreNode)线索化原二叉树。线索完毕后PreNode就是原二叉树最右下方的分支节点（对应上图中的G），按照图2的方法则应将PreNode节点的右标志域更新为后继标志、后继更新为Thrt、同时Thrt的后继应为PreNode。
下面分析void PreOrderThreading(pThBTNode pT,pThBTNode& pPreNode)的实现

void PreOrderThreading(pThBTNode pT,pThBTNode& pPreNode)
{
	if(NULL == pT)
	{
		return;//原二叉树根节点为空、退出函数	
	}

	if(NULL == pT->pLNode) //二叉树分支节点的左指针域为空则置其左标志域更新为前驱线索标志域、其应指向刚刚访问过的节点					
	{
		pT->lTag = thread;																					
		pT->pLNode = pPreNode;										
	}
	if(NULL == pPreNode->pRNode)//刚刚访问过的节点的右指针域为空则置其右标志域更新为后继线索标志域、其应指向二叉树分支节点
	{
		pPreNode->rTag = thread;
		pPreNode->pRNode = pT;
	}
	pPreNode = pT;	//更新刚刚访问过的节点指针	
	if(link == pT->lTag)//二叉树分支节点的左节点为非叶子节点、递归线索化其左节点 判断不能缺少否则堆栈溢出			
	{
		PreOrderThreading(pT->pLNode,pPreNode);						
	}
	if(link == pT->rTag)//二叉树分支节点的右节点为非叶子节点、递归线索化其右节点 判断不能缺少否则堆栈溢出
	{
		PreOrderThreading(pT->pRNode,pPreNode);								
	}
}

当pT为空时，就退出函数。由于是先序线索化二叉树、应首先判断当前访问的节点的左指针域是否为空，如果为空说明其是叶子节点，就该将节点线索化，其左指针域应指向前驱，因此左指针域有NULL更新为PreNode,左标志域有link跟新为thread。然后要判断PreNode右指针域是否为空，如果为空的话就应将PreNode的左指针域有NULL更新为pT，左标志域有link更新为thread。然后更新刚刚访问的节点PreNode为当前叶子节点T。如果二叉树分支节点的左右节点为非叶子节点，递归线索化左右节点。
下面介绍先序遍历线索化二叉树

void PreOrderTraverseThreadBTree(pThBTNode pThrt)
{
	pThBTNode pT = pThrt->pLNode;//定义一个指针指向线索化的二叉树的根节点					
	if(NULL == pThrt)
		return;
	else
	{
		while(pT != pThrt)//pT还没遍历到根节点									
		{
		     cout<<pT->data;	//输出当前节点的数据域											   
		     while(link == pT->lTag)//当前节点的左标志域为节点标志、则循环遍历左结节点并输出其数据域直到该节点的左标志域为线索标志域
		     {	
			pT = pT->pLNode;
			cout<<pT->data;
		     }
		     if(thread == pT->rTag && pT->pRNode != pThrt)//当前节点的右标志域为线索标志域并且当前节点的右指针域不指向线索化二叉树的头节点	
		     {				  	     	
			pT = pT->pRNode;		 //更新指向当前节点的指针为其后继、并输出其数据域		
			cout<<pT->data;		
		     }
		    if(link == pT->lTag)    		//当前节点的左标志域为节点标志		
		    {
			pT = pT->pLNode;		//更新指向当前节点的指针指向其左节点							
		    }
		    else											
		    {
			pT = pT->pRNode;	      //否则更新指向当前节点的指针其右节点	
		    }
		}
	}
}

由于二叉树线索化是对二叉树非线性结构进行线性化操作，只需知道线索化二叉树的头结点便可对其进行遍历。顺着Thrt的右指针域递归，可以回到Thrt。Thrt类似链表中的头节点不存放有效数据。具体过程见注释。