线索二叉树

线索二叉树实质上就是将一颗二叉树转化成二叉链表的过程，将二叉树的一些空指针给利用起来，为了达到这个目的，我们使用中序遍历线索化的办法。

也就是要将每个节点的指针全部存储一个值，为了区分线索和真正的子节点，我们就需要一个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;
    }
}

其实线索二叉树的建立过程，就是一次中序遍历的过程，在遍历过程中，对每一个节点进行线索化，如果有能利用到的空指针，就可以用来存放前驱后继。