1 #include <iostream>
 2 #include<cstdio>
 3 #define size 50
 4 using namespace std;
 5 /************线索二叉树的主要的地方在于利用剩余的空闲结点来指引节点的前驱和后继********************/
 6 typedef struct InThread
 7 {
 8     char Data;
 9     struct InThread* lchild, * rchild;
10     int ltag, rtag;
11 }InThread,*InThread1;
12 InThread1 pre = NULL;
13 void InitInThread(InThread1& T)//线索标志初始化；
14 {
15     T->ltag = 0;
16     T->rtag = 0;
17 }
18 void CreatePreOrder(InThread1& T)//先序创建二叉树
19 {
20     char ch[size];
21     int i = 0;
22     cin >> ch;
23     if (ch[i] == ‘*‘) T = NULL;
24     else {
25         T = new InThread;
26         T->Data = ch[i++];
27         CreatePreOrder(T->lchild);
28         CreatePreOrder(T->rchild);
29     }
30 }
31 void Visit(InThread1& T)//二叉树的线索化
32 {
33     if (T->lchild == NULL)
34     {
35         T->lchild = pre;
36         T->ltag = 1;
37     }
38     if (pre != NULL && pre->rchild == NULL)
39     {
40         pre->rchild = T;
41         pre->rtag = 1;
42     }
43     pre = T;
44 }
45 void InThreadOrder(InThread1& p)//中序遍历，同时边遍历边线索化；
46 {
47     if (p) {
48         InThreadOrder(p->lchild);
49         Visit(p);
50         InThreadOrder(p->rchild);
51     }
52 }
53 void PreThreadOrder(InThread1& p)//先序遍历，同时边遍历边线索化；
54 {
55     if (p) {
56         Visit(p);
57         if (p->ltag == 0) InThreadOrder(p->lchild);//处理“爱的魔力转圈圈”问题；
58         InThreadOrder(p->rchild);
59     }
60 }
61 void InThreadOrder(InThread1& p)//后序遍历，同时边遍历边线索化；
62 {
63     if (p) {
64         InThreadOrder(p->lchild);
65         InThreadOrder(p->rchild);
66         Visit(p);
67     }
68 }
69 int main()
70 {
71     InThread* T;
72     CreatePreOrder(T);
73     InitInThread(T);
74     InThreadOrder(T);
75     if (pre->rchild = NULL)//最后一个节点的处理
76         pre->rtag = 1;
77     return 0;
78 }