先序

二叉树先序线索化

二叉树先序线索化采用递归的方式实现，与二叉树先序遍历过程相似，需要注意的是需要事先设置一个指针指向前一个访问的节点，代码如下：

//预先定义一个全局变量pre指向NUll
void prethreading(bithrtree p)
{
  if(p)
  {
  if(!p->lchild)
  {
  p->ltag=thread;
  p->lchild=pre;
  }//若p没有左子树则线索化
  if(!pre->rchild)
  {
  pre->rtag=thread;
  pre->rchild=p;
  }//若pre没有右子树则线索化
  pre=p;//每次循环后不要忘记更新pre指针
  prethreading(p->lchild);
  prethreading(p->rchild);
  }
}

先序线索二叉树遍历

先序遍历较为简单，我们从找节点的后继着手，
：进入循环->访问当前节点->寻找后继节点->后继节点进入下一层循环，可以看到问题主要在与如何寻找后继节点

这里提供两种寻找后继节点的思路

第一种，如果当前节点rtag为thread则后继为它的rchild，否则，如果有左孩子且ltag为link，后继为左孩子，否则后继为右孩子
代码如下：

void InorderTraverse_Thr(bthrtree p)
{
 while(p)
 {
 printf("%d",p->data);
  if(p->rtag==thread)
     p=p->rchild;
  else
  {
   if(p->ltag==link&&p->lchild!=NULL)
     p=p->lchild;
   else p=p->rchild;
  }
 }
}

第二种，如果当前节点有左孩子且ltag为link则优先访问左孩子，否则如果右节点为空则无后继，若右节点不为空则后继为rchild（此时有rtag为thread和link两种情况，但后继都为rchild）
代码如下

void InorderTraverse_Thr(bthtree p)
{
  while(p)
  {
   printf("%d",p->data);
   if(p->lchild!=NULL&&p->ltag==link)
   p=p->lchild;
   else
   {
     if(p->rchild==NULL)
     break;
     else p=p->rchild;
   }//这条语句直接写成p=p->rchild也可以
   
  }
}

中序

二叉树中序线索化

中序线索化与前序类似，只是将判断模块移至中位
代码如下：

void inthreading(bithrtree p)
{
  inthreading(p->lchild);
  if(p)
  {
  if(!p->lchild)
  {
  p->ltag=thread;
  p->lchild=pre;
  }//若p没有左子树则线索化
  if(!pre->rchild)
  {
  pre->rtag=thread;
  pre->rchild=p;
  }//若pre没有右子树则线索化
  pre=p;//每次循环后不要忘记更新pre指针
  inthreading(p->rchild);
  }
}

中序线索二叉树遍历

中序遍历需要先找到遍历开始点，找到之前所有经过的节点都不能访问，那么如何找到遍历的开始点呢？首先找到最左下的节点。我们会发现这个节点有两种情况，一种是无右孩子，那么它即为遍历开始点，另一种情况是有右孩子，此时由中序遍历的特点可知此节点仍为遍历开始点且它的后继为rchild，可见遍历开始点始终为最左下的点。找到遍历开始点后就开始进行遍历，如果rtag为thread且没有到达结尾时就一直遍历rchild。rtag不为thread时则根据中序遍历性质得知后继为rchild。
代码如下:

void InorderTraverse_Thr(bithrtree p)
{
  while(p)
  {
    while(p->ltag==link)
      p=p->lchild;
      printf("%d",p->data);//访问最左下节点
     while(p->rtag==thread&&p->rchild!=NULL)
     {
       p=p->rchild;
       printf("%d",p->data);
     }//遍历后继节点
     p=p->rchild;
  }
}