線索二叉樹實質(zhì)上就是將一顆二叉樹轉(zhuǎn)化成二叉鏈表的過程，將二叉樹的一些空指針給利用起來，為了達(dá)到這個目的，我們使用中序遍歷線索化的辦法。

也就是要將每個節(jié)點的指針全部存儲一個值，為了區(qū)分線索和真正的子節(jié)點，我們就需要一個flag，將線索和子節(jié)點區(qū)分開來，具體代碼如下。

#define thread 1
#define child 0

//我們將原本的節(jié)點擴(kuò)充一下，來區(qū)分指針存儲的是什么
struct treeNode
{
    int data;
    treeNode* lChild;
    treeNode* rChild;
    int lTag;
    int rTag;
};

//定義一個全局變量，指向上一次遍歷過的節(jié)點
//我們需要在每次遞歸線索化的時候改變這個值
//也可以不需要全局變量，改用引用
treeNode* preNode;

//中序線索化二叉樹
void cueingTree(treeNode* node)
{
    if(node != NULL)
    {
        cueingTree(node->lChild);
//如果當(dāng)前節(jié)點的左子樹節(jié)點是為NULL，則說明它可以用來存放這個節(jié)點的前驅(qū)
//即上次遍歷過的節(jié)點
        if(node->lChild == NULL)
        {
            node->lTag = thread;
            node->lChild = preNode;
        }
//如果上個節(jié)點的右子樹為NULL，說明可以存放這個節(jié)點的后繼
//只有在知道了后繼之后才能為前一個節(jié)點賦值
        if(preNode->rChild == NULL)
        {
            preNode->rTag = thread;
            preNode->rChild = node;
        }
//更新上次遍歷過的節(jié)點
        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;
    }
}

其實線索二叉樹的建立過程，就是一次中序遍歷的過程，在遍歷過程中，對每一個節(jié)點進(jìn)行線索化，如果有能利用到的空指針，就可以用來存放前驅(qū)后繼。