基本思想：
第一个访问的结点应该是最左下角的结点
假设刚才访问的结点是p
然后P的后继是谁？
若p->rchild是指针，说明P有右子树，下一个结点应该是P右子树中最左下角的结点
若p->rchild是线索，直接访问p->rchild
如此循环往复...
1 #include <iostream>
2 #include <stdio.h>
3
4 using namespace std;
5
6 typedef char TElemType;
7 enum PointerTag{ Link,Thread };//Link == 0 :指针，Thread == 1 :线索
8 typedef struct BiThrNode
9 {
10 TElemType data;
11 struct BiThrNode *lchild,*rchild;
12 PointerTag LTag,RTag;
13 }BiThrNode,*BiThrPtr;
14
15 BiThrPtr pre=NULL;//定义全局变量
16
17 //默认按前序遍历的顺序输入，尾结点用#表示
18 int Create_BiThrTree(BiThrPtr& T)
19 {
20 TElemType c;
21 //cout << "请输入当前节点元素值：" << endl;
22 cin>>c;
23 if(c == '#') T=NULL;
24 else
25 {
26 T = new BiThrNode;
27 T->data=c;
28 T->LTag=Link;
29 T->RTag=Link;
30 Create_BiThrTree(T->lchild);
31 Create_BiThrTree(T->rchild);
32 }
33 return 0;
34 }
35
36 //中序遍历输入各节点
37 int InOrderDisplay(BiThrPtr& T)
38 {
39 if(T)
40 {
41 InOrderDisplay(T->lchild);
42 cout << T->data <<" ";
43 InOrderDisplay(T->rchild);
44 }
45 return 0;
46 }
47
48
49 int InOrderTraverse(BiThrPtr& T)
50 {
51 extern BiThrPtr pre;//声明全局变量
52 if(T)
53 {
54 InOrderTraverse(T->lchild);
55 if(!T->lchild)
56 {
57 T->LTag = Thread;
58 T->lchild = pre;
59 }
60 if(!pre->rchild)
61 {
62 pre->RTag = Thread;
63 pre->rchild = T;
64 }
65 pre = T;
66 InOrderTraverse(T->rchild);
67 }
68 return 0;
69 }
70
71 int InOrderThreading(BiThrPtr &H,BiThrPtr& T)
72 {
73 H = new BiThrNode;//额外添加的头结点
74 H->data = '#';
75 H->LTag = Link;
76 H->RTag = Thread;
77 H->rchild = H;
78 if(!T)
79 {
80 H->lchild = H;
81 }
82 else
83 {
84 H->lchild = T;
85 pre = H;
86 InOrderTraverse(T);
87 pre->RTag = Thread;
88 pre->rchild = H;
89 H->rchild = pre;
90 }
91 return 0;
92 }
93
94
95 int InOrderTraverse_Thr(BiThrPtr H) //T为头节点
96 {
97 BiThrPtr p;
98 p = H->lchild; //p指向树根
99 while(p != H) //p等于T则说明已经遍历完毕
100 {
101 while(p->LTag == Link) //p->lchild为指针
102 p = p->lchild; //则向左下走到底
103 cout << p->data << " ";
104 while(p->RTag == Thread && p->rchild != H) //p->rchild为线索
105 {
106 p = p->rchild; //访问p->rchild
107 cout << p->data << " ";
108 }
109 p = p->rchild; //向右走
110 }
111 return 0;
112 }
113
114 int main()
115 {
116 freopen( "input.txt", "r", stdin );//从input.txt中读取输入数据
117 BiThrPtr T=NULL,H=NULL;
118 Create_BiThrTree(T);//前序遍历创建二叉树
119 InOrderDisplay(T);//用于验证下面的线索中序遍历输出结果是否正确
120 cout << endl;
121 InOrderThreading(H,T);
122 InOrderTraverse_Thr(H);
123 cout << endl;
124 fclose(stdin);
125 return 0;
126 }
txt中的测试数据：
ABC##D##E#F##
输出结果：C B D A E F
