线索二叉树（中序）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef int ElemType;
 4 
 5 typedef struct ThrNode{
 6     ElemType data;
 7     ThrNode* lson;
 8     ThrNode* rson;
 9     int ltag;
10     int rtag;
11     ThrNode(ElemType data, ThrNode* lson, ThrNode* rson) {
12         this->ltag=0;
13         this->rtag=0;
14         this->data = data;
15         this->lson = lson;
16         this->rson = rson;
17     }
18 }*ThrTree;
19 
20 void inThread(ThrTree &p,ThrTree &pre){
21     if(p){
22         //printf("%d ",p->data);
23         inThread(p->lson,pre);
24         if(p->ltag){
25             p->ltag=1;
26             p->lson=pre;
27         }
28         if(pre&&!pre->rtag){
29             pre->rtag=1;
30             pre->rson=p;
31         }
32         pre=p;
33         inThread(p->rson,pre);
34     }
35 }
36 
37 void dfs(ThrTree T){
38     if(T){
39         printf("%d ",T->data);
40         dfs(T->rson);
41     }
42 }
43 
44 
45 int main(){
46     ThrNode* v7 = new ThrNode(7, NULL, NULL);
47     ThrNode* v1 = new ThrNode(1, NULL, NULL);
48     ThrNode* v3 = new ThrNode(3, NULL, NULL);
49     ThrNode* v2 = new ThrNode(2, v1, v3);
50     ThrNode* v5 = new ThrNode(5, NULL, NULL);
51     ThrNode* v6 = new ThrNode(6, v5, v7);
52     ThrNode* v4 = new ThrNode(4, v2, v6);
53 
54     ThrTree T=v4,pre=NULL;
55     ThrTree p=T;
56     p=p->lson;
57     printf("%d
",p->data);
58     inThread(T,pre);
59     p=T;
60     p=p->lson;
61     printf("%d
",p->data);
62     p=p->lson;
63     //dfs(p);
64     //printf("%d",get_kth_number(T,4));
65 }