线索二叉树的存储结构

typedef struct ThreadNode
{
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree;

通过中序遍历对二叉树线索化

void InThread(TBTNode *p, TBTNode *&pre)
{
    if(p != NULL)
    {
        InThread(p->lchild, pre); // 递归，左子树线索化

        if(p->lchild == NULL)
        {
            // 建立当前节点的前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre != NULL && pre->rchild == NULL) // pre != NULL 排除第一个结点前驱为空的情况
        {
            // 建立当前节点的后继线索
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;

        InThread(p -> rchild, pre); // 递归，右子树线索化
    }
}

void createInThread(TBTNode *root)
{
    TBTNode *pre = NULL;
    if(root != NULL)
    {
        InThread(root, pre);
        pre->rchild = NULL; // 非空二叉树，线索化
        pre->rtag = 1; // 后处理中序最后一个结点
    }
}

中序线索二叉树的遍历

ThreadNode *FirstNode(ThreadNode *p) // 中序序列下第一个结点访问算法
{
    while (p->ltag == 0)
        p = p->lchild; // 最左下结点（不一定是叶子结点）
    return p;
}

ThreadNode *NextNode(ThreadNode *p) // 中序序列下后继结点访问算法
{
    if(p->rtag == 0)
        return  FirstNode(p->rchild);
    else
        return p->rchild; // rtage == 1，直接返回后序线索
}

void Inorder(ThreadNode *T)
{
    for(ThradNode *p = FirstNode(root); p != NULL; p = NextNode(p))
       visit(p); // 访问结点
}

前序线索二叉树