定义一下结构体，下面的算法可能和定义有点不一样，但是差不多
eg.这里的"最左下"结点不一定是叶子结点，呃呃呃，没错，最右下也是如此
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
/*先序线索二叉树找前驱*/
1.如果要在先序线索二叉树中找一个结点的前驱结点，那么必须找到它的“双亲节点”
2.我们这里假设通过一个函数找到了结点p的双亲节点f (一定要找到双亲节点)
主要思想：
1.如果p是p的双亲节点f的左孩子，那么x的前驱为f
2.如果p是p的双亲节点f的右孩子，那么x的前驱为f的左子树的“最右下叶节点”
BiThrTree PrePre(BiThrThee p)
{
if(p->Ltag == 1)
pre = p->LChild;
else{
f = findfather(p); //我们假设写好了这样的一个函数
if( f->LChild == p ) pre=f;
else{
//for(q=f->LChild;q->Rtag==0;q=q->RChild)
//pre = q；
pre=p的双亲的右子树的最左下叶结点;
}
}
return pre;
}
/*先序线索二叉树找后继*/
1.如果有线索，使用线索
2.如果没有线索并且左子树不为空树，后继结点是左子树的根结点
3.如果没有线索并且右子树不为空树，后继结点是右子树的根结点
BiThrTree PreNext(BiThrThee p)
{
if(p->Rtag == 1)
next = p->RChild;
else if(p->LChild){
next = p->LChild;
}else{
next = p->RChild;
}
return next;
}
/*中序线索二叉树找前驱*/
1.如果该结点有指向前驱的线索，那么直接使用线索访问
2.如果没有线索，那么说明Ltag==0,即该结点有左子树，那么
前驱结点是他的左子树的最右下结点
BiThrTree InPre(BiThrThee p)
{
if(p->Ltag == 1)
pre = p->LChild;
else{
for(q=p->LChild;q->Rtag==0;q=q->RChild)
pre = q;
}
return pre;
}
/*中序线索二叉树找后继*/
1.如果该结点有指向后继的线索，那么直接使用线索访问
2.如果没有线索，那么说明Rtag==0,即该结点有右子树，那么
前驱结点是他的右子树的最左下结点
BiThrTree InNext(BiThrThee p)
{
if(p->Rtag == 1)
pre = p->RChild;
else{
for(q=p->RChild;q->Ltag==0;q=q->LChild)
pre = q;
}
return pre;
}
/*后序线索二叉树找前驱*/
思路：
1.如果有线索指向前驱，那么使用线索找到前驱
2.如果没有线索，说明左子树不为空（右子树是否为空不清楚，分开讨论一下）
3.后续遍历，根是在遍历完了左右子树之后才可以遍历的，
因此p的前驱一定是两个子树最后遍历结点。
4.如果p的右子树非空，p->RChild一定是前驱
5.如果p的右子树为空，p->LChild一定是前驱
BiThrTree PostPre(BiThrThee p)
{
if(p->Ltag == 1)
pre = p->LChild;
else{
if(p->RChild) pre=p->RChild;
else pre=p->LChild;
}
return pre;
}
/*后序线索二叉树找后继*/
思路：（需要找到双亲结点！！！）
1.若p是根节点，那么它没有后继结点
2.若p有指向后继的线索，使用线索进行访问后继结点
3.若p是其双亲的右孩子,那么双亲结点f就是p后继结点
4.若p是其双亲的左孩子
4.1若p没有右兄弟节点，p的后继结点为f
4.2若p有右兄弟结点，p的后继结点是p的双亲的右子树
中第一个后序遍历到的结点，它是该子树的“最左下叶结点”
BiThrTree PostNext(BiThrThee p)
{
if(p->Rtag == 1)
pre = p->RChild;
else{
f=findFather(p); //找到父节点
if( f->RChild==p ) pre=f;
else if( f->LChild==p ){
if( f->RChild==NULL ) pre=f;
else pre= p的双亲的右子树的最左下叶结点;
}
}
return pre;
}
这是网上找的中序线索化其他的写法：（只是把for改成了while）
BinThrNode *InorderSuccessor(BinThrNode *p)
{
//在中序线索树查找*p的后继
BinThrNode *q;
if(p->rtag==Thread)
return p->rchlid;//返回其所指的后继
else
{
q = p->rchild;//从*p的右孩子开始查找
while(q->ltag==Link)
q = q->lchild;//左子树为空，沿左链往下查找
return q;
}
}
BinThrNode *Inorderpre(BinThrNode *p)
{//在中序线索树中找结点*p的中序前趋，设p非空
BinThrNode *q；
if (p->ltag==Thread) //*p的左子树为空
return p->lchild； //返回左线索所指的中序前趋
else{
q=p->lchild； //从*p的左孩子开始查找
while (q->rtag==Link)
q=q->rchild； //右子树为空时，沿右链往下查找
return q； //当q的右子树为空时，它就是最右下结点
} //end if
}
