struct tnode
{
int flag;//有左孩的为0,没有左孩的为1;
tnode* parent;
char data;
int ltag;
int rtag;
tnode* right;
tnode* left;
};
void postthread(tnode* t, tnode* post) {
if (t != nullptr) {
if (t->right == nullptr)//当前节点的后继线索化
{
t->right = post;
t->rtag = 1;
}
else
t->ltag = 0;
if (post != nullptr && post->ltag == 1)//后继节点的前驱线索化
post->left = t;
if (t->left == nullptr)//判断当前节点是否需要前驱线索化
t->ltag = 1;
else
t->ltag = 0;
post = t;
if (t->rtag == 0) postthread(t->right, post);
if (t->ltag == 0)postthread(t->left, post);
if (t->rtag == 1 && t->ltag == 1)
{
while (t->parent->flag == 1)
t = t->parent;
postthread(t->parent->left, post);
}
}
}
void postThreading(TriTree p){
if(p){
postThreading(p->lChild);
postThreading(p->rChild);
if(!p->lChild){
p->lTag=1;
p->lChild=pre;
}
if(!pre->rChild){
pre->rTag=1;
pre->rChild=p;
}
pre=p;
}
}
bool postThreadTree(TriTree T,TriTree &head){
if(!(head=new TriTNode)) return false;
head->lTag=0;
head->rTag=1;
head->parent=NULL;
if(!T){head->lChild=head;head->rChild=head;}
else{
pre=head;
head->lChild=T;
head->rChild=T;
T->parent=head;
postThreading(T);
if(!pre->rChild){
pre->rTag=1;
pre->rChild=head;
}
}
return true;
}