//线索二叉树存储结构
typedef struct TBTNode
{
int data;
int lTag;
int rTag;
TBTNode* lChild;
TBTNode* rChild;
}TBTNode;
//中序线索化
//pre指向p的前驱结点,对比二叉树遍历的代码
void inThread(TBTNode *p, TBTNode *&pre)
{
if (p != NULL)
{
inThread(p->lChild, pre);
if (p->lChild == NULL)//上一层循环条件已经判断过p不为空
{
p->lChild = pre;
p->lTag = 1;
}
if (pre != NULL && pre->rChild == NULL)
{
pre->rChild = p;
pre->rTag = 1;
}
pre = p;
inThread(p->rChild, pre);
}
}
//先序线索化
void preThread(TBTNode *p, TBTNode *&pre)
{
if (p != NULL)
{
if (p->lChild == NULL)//上一层循环条件已经判断过p不为空
{
p->lChild = pre;
p->lTag = 1;
}
if (pre != NULL && pre->rChild == NULL)
{
pre->rChild = p;
pre->rTag = 1;
}
pre = p;
if (p->lTag == 0)//先线索化会导致p指针在线索分支打转，增加的判断条件
inThread(p->lChild, pre);
if (p->rTag == 0)
inThread(p->rChild, pre);
}
}
//遍历先序线索二叉树
void preOrderTra(TBTNode *tbt)
{
if(tbt != NULL)
{
TBTNode *p = tbt;
while(p != NULL)
{
while(p->lTag == 0)
{
visit(p);
p = p->lChild;
}
visit(p);
p = p->rChild;
}
}
}
//后序线索化
void postThread(TBTNode *p, TBTNode *&pre)
{
if (p != NULL)
{
inThread(p->lChild, pre);
inThread(p->rChild, pre);
if (p->lChild == NULL)//上一层循环条件已经判断过p不为空
{
p->lChild = pre;
p->lTag = 1;
}
if (pre != NULL && pre->rChild == NULL)
{
pre->rChild = p;
pre->rTag = 1;
}
pre = p;
}
}
