//线索二叉树定义
typedef struct ThreadTreeNode{
int data;
int ltag,rtag;
struct ThreadTreeNode *lchild,*rchild,*parent;
}ThreadTreeNode,*ThreadTree;
线索二叉树的基本操作
//带父结点的二叉树的建立
ThreadTree createWP(){
int data;
scanf("%d",&data);
ThreadTree t = NULL;
if(data!=-1){
t = (ThreadTreeNode*)malloc(sizeof(ThreadTreeNode));
t->ltag = t->rtag = 0;
t->data = data;
t->lchild = createWP();
//父节点绑定
if(t->lchild){
t->lchild->parent = t;
}
t->rchild = createWP();
//父节点绑定
if(t->rchild){
t->rchild->parent = t;
}
}else{
return t;
}
}
////对二叉树中序线索化
//递归子函数
void InThreadBiTree(ThreadTree &t,ThreadTree &p){
if(t){
InThreadBiTree(t->lchild,p);
if(t->lchild==NULL){
t->lchild = p;
t->ltag = 1;
}
if(t->rchild==NULL){
t->rchild = p;
t->rtag = 1;
}
p = t;
InThreadBiTree(t->rchild,p);
}
}
//主函数
void CreateInThread(ThreadTree t){
ThreadTree p = NULL;
if(t){
InThreadBiTree(t,p);
p->rchild = NULL;
p->rtag = 1;
}
}
////中序线索二叉树的遍历
//求中序线索二叉树序列中的第一个结点
ThreadTree FirstNode(ThreadTree t){
//寻找最左下的结点
while(t->ltag == 0){
//有左孩子就向左移动
t = t->lchild;
}
return t;
}
//求中序线索二叉树中某个结点的后继
ThreadTree NextNode(ThreadTree t){
if(t->rtag != 1){
return FirstNode(t->rchild); //没有直接后继，就找右子树中最靠左的结点
};
return t->rchild;
}
//遍历中序线索二叉树
void printInThreadTree(ThreadTree t){
for(ThreadTree p=FirstNode(t);p!=NULL;p=NextNode(t)){
printf("%d",p->data);
}
}
////对二叉树的前序线索化
//递归子函数
void PreThreadBiTree(ThreadTree &t,ThreadTree &p){
if(t){
if(t->lchild==NULL){
t->lchild = p;
t->ltag = 1;
}
if(t->rchild==NULL){
t->rchild = p;
t->rtag = 1;
}
p = t;
//一定得有判断条件，防止转圈
//（例如去掉条件，t->ltag是1时没有判断条件，前驱结点与本结点构成一个环，不停循环)
if(t->ltag == 0)PreThreadBiTree(t->lchild,p);
if(t->rtag == 0)PreThreadBiTree(t->rchild,p);
}
}
//主函数
void PreThread(ThreadTree t){
ThreadTree p = NULL;
if(t){
PreThreadBiTree(t,p);
p->rchild = NULL;
p->rtag = 1;
}
}
////前序结果二叉树的遍历
//求前序结点二叉树的某个结点的前驱
ThreadTree PrePNode(ThreadTree t){
if(t->ltag==1){
return t->lchild;
}else{
//分三种情况,需要用到父结点
//如果t是父结点的左结点，根据NLR，其前驱为其父节点
if(t->parent->lchild==t){
return t->parent;
//如果t是父节点的右结点，且父节点无左子结点，则前驱依然是父结点
}else if(t->parent->ltag == 1){
return t->parent;
//前面两个条件都失效，证明该结点为右结点且父结点有左孩子，前驱应该是左孩子的最右下结点
//并且该节点一定是一个叶子节点，所以左右线索都应为1
}else{
ThreadTree p = t->parent->lchild;
//遍历（难点）
while(p->rtag != 1 || p->ltag != 1){
//向右不停查找，直到节点无右子树
while(p->rtag == 0)p = p->rchild;
//找到无右子树的节点，检查是否有左子树
if(p->ltag == 0)
//若有左子树，向左走一步，继续向右走，直到找到最右下节点
p = p->lchild;
}
return p;
}
}
}
//求前序结点二叉树的某个结点的后继
ThreadTree PostPNode(ThreadTree t){
if(t->rtag==1){
//有后继线索，直接返回
return t->rchild;
}else{
//该节点有右孩子，分两种情况讨论
//该节点有左孩子，返回左孩子
if(t->rtag==0)return t->lchild;
//否则该节点无左孩子，返回右孩子为其后继
else return t->rchild;
}
}
//遍历前序结点二叉树
void PrintPTTree(ThreadTree t){
for(ThreadTree p = t;p!=NULL;p = PostPNode(p)){
printf("%d",p->data);
}
}
////对二叉树的后序线索化
//递归子函数
ThreadTree PostThreadBiTree(ThreadTree &t,ThreadTree &p){
if(t){
if(t->ltag==0)
PostThreadBiTree(t->lchild,p);
if(t->rtag==0)
PostThreadBiTree(t->rchild,p);
p = t;
if(t->lchild==NULL){
t->lchild = p;
t->ltag = 1;
}
if(t->rchild == NULL){
t->rchild = p;
t->rtag = 1;
}
}
}
//主函数
void PostThread(ThreadTree t){
ThreadTree p = NULL;
if(t){
PostThreadBiTree(t,p);
p->rchild = NULL;
p->rtag = 1;
}
}
////前序结果二叉树的遍历
//求前序结点二叉树的某个结点的前驱
ThreadTree PrePostNode(ThreadTree t){
if(t->ltag == 1){
//有直接后继
return t->lchild;
}else{
//有左孩子，先看有没有右孩子
if(t->rtag==0)return t->rchild;
else return t->lchild;
}
}
//求前序结点二叉树的某个结点的后继
ThreadTree PostPostNode(ThreadTree t){
if(t->rtag == 1){
//有直接后继
return t->rchild;
}else{
//父节点的右孩子是否为本节点，是的话直接返回父节点
if(t->parent->rchild == t){
return t->parent;
//父节点无右孩子，本节点是左孩子，是的话也直接返回父节点
}else if(t->parent->rtag == 1){
return t->parent;
}else{
//后继节点应为父节点右孩子的最左下节点，且应为叶节点
ThreadTree p = t->parent->rchild;
while(p->ltag == 0 && p->rtag == 0){
while(p->ltag == 0){
p = p->lchild;
}
//是否还有右子节点，有的话则不为叶子节点，向右走一下
if(p->rtag == 0){
p = p->rchild;
}
}
return p;
}
}
}
//后序线索二叉树的打印
void printPost(ThreadTree t){
int stack[MAXSIZE],top=-1;
//由于后续二叉树的特性LRN，打印出来应该是后序节点排列的倒序
//利用栈后进先出的特点，我们选用一个栈来存储数据
for(ThreadTree p = t;t!=NULL;t=PrePostNode(t)){
stack[++top] = p->data;
}
while(top>=0){
printf("%d",stack[top--]);
}
}
