先序，中序，后序线索二叉树

//后序线索，这种方法不容易想到
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

struct TREE{
    int    val;
    TREE *ch[2];
    TREE *thread;//该节点的线索的下一个节点 
    TREE(){}
    TREE(int val){
        this->val = val;
        ch[0] = ch[1] = NULL;
        thread = NULL;
    }
};

void buildT(TREE * &T){
    int x;
    scanf("%d", &x);
    if(x == -1) return ;
    
    T = new TREE(x);
    buildT(T->ch[0]);
    buildT(T->ch[1]);
}


void postThread(TREE *T, TREE *pre){
    if(!T) return;
    postThread(T->ch[0], T);
    postThread(T->ch[1], T);
    if(pre){
        if(pre->ch[0] == T && pre->ch[1])//T是左子树 
            T->thread = pre->ch[1]; //T的下一个节点就是它的兄弟节点 
        else //T是右子树
            T->thread = pre;//T的下一个节点就是它 的父亲节点             
    }
}

void printT_pre(TREE *T){//前序打印 
    if(!T) return ;
    printf("%d ", T->val);
    printT_pre(T->ch[0]);
    printT_pre(T->ch[1]);
}

void printT_Thread(TREE *T){//后序线索打印 
    TREE *root = T;
    bool flag = true;//表明T所在的字数没有访问过 
    while(1){
        while(flag && T->ch[0]) T = T->ch[0];
        printf("%d ", T->val);
        if(T->thread->ch[0] == T || T->thread->ch[1] == T)
            flag = false;//如果 T没有兄弟节点了，就一直沿着它的父节点向上走 
        else flag = true;
        T = T->thread;
        if(T == root){//再次回到最顶端父节点时， 结束！ 
           printf("%d ", T->val);           
           break;
        }
    }
}

int main(){
    TREE *T = NULL;
    buildT(T);
    printT_pre(T);
    printf("\n");
    postThread(T, NULL);
    printT_Thread(T);
    printf("\n");
    return 0;
}

下面是基本按照同样的套路实现二叉树的先序，中序，后序的线索

//先序线索
#include<stdio.h> 
#include<stdlib.h>
#define Thread 1
#define Tlink 0
typedef struct tree
{
   int d;
   struct tree* lchild;
   struct tree* rchild;
   int Ltag, Rtag;
}*TREE;

void build_tree(TREE &T)
{
   int d;
   scanf("%d", &d);
   if(d!=-1)
     {
         T=(TREE)malloc(sizeof(tree));
         T->d=d;
         T->lchild=T->rchild=NULL;
         T->Ltag=T->Rtag=Tlink;
         build_tree(T->lchild);
         build_tree(T->rchild);
     }
} 

TREE pre;

void preThread_tree(TREE p)
{
   if(p)
     {
        if(!p->lchild)
          {
               p->lchild=pre;
               p->Ltag=Thread;
          }
        if(!pre->rchild)
          {
              pre->rchild=p;
              pre->Rtag=Thread;
          }
         pre=p;
         if(p->Ltag==Tlink)//考虑到只有一个结点或两个节点情况， 
            preThread_tree(p->lchild);//如果没有 if语句可能出现死循环 
         if(p->Rtag==Tlink)
            preThread_tree(p->rchild);
     }
}

void print_preThr_tree(TREE T)
{
   TREE p=T;
   while(1)
    { 
       while(p->Ltag==Tlink)
         {
             printf("%d ", p->d);
             p=p->lchild;
         }
       printf("%d ", p->d);
       p=p->rchild;
       if(p==T) break;
       while(p->Rtag==Thread)
         {
             printf("%d ", p->d);
            p=p->rchild;
         }
       
    }
}

void print_tree(TREE T)
{
    if(T)
     {
        printf("%d ", T->d);
        print_tree(T->lchild);
        print_tree(T->rchild);
     }
}


int main()
{
   TREE T=NULL;
   build_tree(T);
   print_tree(T);//递归先序遍历 
   printf("\n");    
   pre=T;
   preThread_tree(T);//非递归先序遍历 
   pre->rchild=T;
   print_preThr_tree(T);
   return 0;
}

//中序线索
#include<stdio.h> 
#include<stdlib.h>
#define Thread 1
#define Tlink 0
typedef struct tree
{
   int d;
   struct tree* lchild;
   struct tree* rchild;
   int Ltag, Rtag;
}*TREE;

void build_tree(TREE &T)
{
   int d;
   scanf("%d", &d);
   if(d!=-1)
     {
         T=(TREE)malloc(sizeof(tree));
         T->d=d;
         T->lchild=T->rchild=NULL;
         T->Ltag=T->Rtag=Tlink;
         build_tree(T->lchild);
         build_tree(T->rchild);
     }
} 

TREE pre;

void inorThread_tree(TREE p)
{
   if(p)
     {
         if(p->Ltag==Tlink)//当只有一个结点的时候，要加上这句话 
           inorThread_tree(p->lchild);
        if(!p->lchild)
          {
               p->lchild=pre;
               p->Ltag=Thread;
          }
        if(!pre->rchild)
          {
              pre->rchild=p;
              pre->Rtag=Thread;
          }
         pre=p;
         if(p->Rtag==Tlink)
           inorThread_tree(p->rchild);
     }
}

/*
上述代码可以简化如下，pre的初值为NULL就好　　
void inorThread_tree(TREE p)
{
   if(p)
     {  
        inorThread_tree(p->lchild);
        if(!p->lchild)
          {
               p->lchild=pre;
               p->Ltag=Thread;
          }
        if(pre && !pre->rchild)
          {
              pre->rchild=p;
              pre->Rtag=Thread;
          }
         pre=p;  
         inorThread_tree(p->rchild);
     }
}
*/

void print_tree(TREE T){
    if(T)
     {
        print_tree(T->lchild);
        printf("%d ", T->d);
        print_tree(T->rchild);
     }
}

void print_inorThr_tree(TREE T)
{
   TREE p=T;
   while(1)
    {
       while(p->Ltag==Tlink)
         p=p->lchild;
       printf("%d ", p->d);
       while(p->Rtag==Thread)
         {
             p=p->rchild;
             printf("%d ", p->d);
         }
       p=p->rchild;
       if(p==T)
         break;
    }
}

int main()
{
   TREE T=NULL;
   build_tree(T);
   print_tree(T);//递归中序遍历 
   printf("\n");    
   pre=T;
   inorThread_tree(T);//非递归中序遍历 
   pre->rchild=T;
   pre->Rtag=0;//保证只有一个结点的情况 
   print_inorThr_tree(T);
   return 0;
}

//后序线索
#include<stdio.h> 
#include<stdlib.h>
#define Thread 1
#define Tlink 0
typedef struct tree
{
   int d;
   struct tree* lchild;
   struct tree* rchild;
   struct tree* rrchild;
   int Ltag, Rtag;
}*TREE;

void build_tree(TREE &T)
{
   int d;
   scanf("%d", &d);
   if(d!=-1)
     {
         T=(TREE)malloc(sizeof(tree));
         T->d=d;
         T->lchild=T->rchild=NULL;
         T->Ltag=T->Rtag=Tlink;
         build_tree(T->lchild);
         build_tree(T->rchild);
     }
} 

TREE pre;

void postThread_tree(TREE p)
{
   if(p)
     {
         if(p->Ltag==Tlink)
            postThread_tree(p->lchild);
         if(p->Rtag==Tlink)
            postThread_tree(p->rchild);
         
         if(!p->lchild)
          {
               p->lchild=pre;
               p->Ltag=Thread;
          }
         if(!pre->rchild )
          {
              pre->rchild=p;
              pre->Rtag=Thread;
          } else {
              pre->rrchild=p;
          }
          pre=p;
     }
}

void print_postThr_tree(TREE T)
{
   TREE p=T;
   while(p->Ltag==Tlink)
      p=p->lchild;
   while(1)
    { 
       printf("%d ", p->d);
       if(p==T)
         break; 
       if(p->Rtag == Thread)
            p=p->rchild;
       else 
               p=p->rrchild;
    }
}

void print_tree(TREE T)
{
    if(T)
     {
        print_tree(T->lchild);
        print_tree(T->rchild);
        printf("%d ", T->d);
     }
}


int main()
{
   TREE T=NULL;
   build_tree(T);
   print_tree(T);//递归后序遍历 
   printf("\n");    
   pre=T;
   postThread_tree(T);//非递归后序遍历 
   pre->rchild=T;
   pre->Rtag = Thread; 
   print_postThr_tree(T); 
   return 0;
}