1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5  6 using namespace std; 7  8 struct TREE{ 9     int    val;10     TREE *ch[2];11     TREE *thread;//该节点的线索的下一个节点 12     TREE(){}13     TREE(int val){14         this->val = val;15         ch[0] = ch[1] = NULL;16         thread = NULL;17     }18 };19 20 void buildT(TREE * &T){21     int x;22     scanf("%d", &x);23     if(x == -1) return ;24     25     T = new TREE(x);26     buildT(T->ch[0]);27     buildT(T->ch[1]);28 }29 30 31 void postThread(TREE *T, TREE *pre){//感觉后序线索二叉树的思路和中序及前序的思路完全不一样啊 32     if(!T) return;33     postThread(T->ch[0], T);34     postThread(T->ch[1], T);35     if(pre){36         if(pre->ch[0] == T && pre->ch[1])//T是左子树 37             T->thread = pre->ch[1]; //T的下一个节点就是它的兄弟节点 38         else //T是右子树39             T->thread = pre;//T的下一个节点就是它 的父亲节点             40     }41 }42 43 void printT_pre(TREE *T){//前序打印 44     if(!T) return ;45     printf("%d ", T->val);46     printT_pre(T->ch[0]);47     printT_pre(T->ch[1]);48 }49 50 void printT_Thread(TREE *T){//后序线索打印 51     TREE *root = T;52     bool flag = true;//表明T所在的字数没有访问过 53     while(1){54         while(flag && T->ch[0]) T = T->ch[0];55         printf("%d ", T->val);56         if(T->thread->ch[0] == T || T->thread->ch[1] == T)57             flag = false;//如果 T没有兄弟节点了，就一直沿着它的父节点向上走 58         else flag = true;59         T = T->thread;60         if(T == root){//再次回到最顶端父节点时， 结束！ 61            printf("%d ", T->val);           62            break;63         }64     }65 }66 67 int main(){68     TREE *T = NULL;69     buildT(T);70     printT_pre(T);71     printf("\n");72     postThread(T, NULL);73     printT_Thread(T);74     printf("\n");75     return 0;76 }