线索二叉树实质上就是将一颗二叉树转化成二叉链表的过程，将二叉树的一些空指针给利用起来，为了达到这个目的，我们使用中序遍历线索化的办法。
也就是要将每个节点的指针全部存储一个值，为了区分线索和真正的子节点，我们就需要一个flag，将线索和子节点区分开来，具体代码如下。
#define thread 1
#define child 0
//我们将原本的节点扩充一下，来区分指针存储的是什么
struct treeNode
{
int data;
treeNode* lChild;
treeNode* rChild;
int lTag;
int rTag;
};
//定义一个全局变量，指向上一次遍历过的节点
//我们需要在每次递归线索化的时候改变这个值
//也可以不需要全局变量，改用引用
treeNode* preNode;
//中序线索化二叉树
void cueingTree(treeNode* node)
{
if(node != NULL)
{
cueingTree(node->lChild);
//如果当前节点的左子树节点是为NULL，则说明它可以用来存放这个节点的前驱
//即上次遍历过的节点
if(node->lChild == NULL)
{
node->lTag = thread;
node->lChild = preNode;
}
//如果上个节点的右子树为NULL，说明可以存放这个节点的后继
//只有在知道了后继之后才能为前一个节点赋值
if(preNode->rChild == NULL)
{
preNode->rTag = thread;
preNode->rChild = node;
}
//更新上次遍历过的节点
preNode = node;
if(node->rChild != node)
{
cueingTree(node->rChild);
}
}
}
//在有了线索二叉树之后，我们便可以使用迭代的方式来遍历二叉树
void inOrderTraversal()
{
treeNode* currentNode = this->head->lChild;
while(currentNode != this->head)
{
while(currentNode->lTag == child)
{
currentNode = currentNode->lChild;
}
cout << currentNode->data << " ";
while(currentNode->rTag == thread && currentNode->rChild != this->head)
{
currentNode = currentNode->rChild;
cout << currentNode->data << " ";
}
currentNode = currentNode->rChild;
}
}
其实线索二叉树的建立过程，就是一次中序遍历的过程，在遍历过程中，对每一个节点进行线索化，如果有能利用到的空指针，就可以用来存放前驱后继。
