线索化二叉树的递归算法

// 线索化二叉树的递归算法

#include <stdio.h>
#include <malloc.h>

typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild; // 存储二叉树的左孩子和右孩子
} BiTNode, *BiTree;

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

void createTree(ThreadTree &T)
{
    T = (ThreadTree)malloc(sizeof(ThreadNode));
    T->data = 1;

    T->lchild = (ThreadNode *)malloc(sizeof(ThreadNode));
    T->lchild->data = 2;

    T->lchild->lchild = (ThreadNode *)malloc(sizeof(ThreadNode));
    T->lchild->lchild->data = 4;
    T->lchild->lchild->lchild = NULL;
    T->lchild->lchild->rchild = NULL;

    T->lchild->rchild = (ThreadNode *)malloc(sizeof(ThreadNode));
    T->lchild->rchild->data = 5;

    T->lchild->rchild->lchild = (ThreadNode *)malloc(sizeof(ThreadNode));
    T->lchild->rchild->lchild->data = 7;
    T->lchild->rchild->lchild->lchild = NULL;
    T->lchild->rchild->lchild->rchild = NULL;

    T->lchild->rchild->rchild = (ThreadNode *)malloc(sizeof(ThreadNode));
    T->lchild->rchild->rchild->data = 8;
    T->lchild->rchild->rchild->lchild = NULL;
    T->lchild->rchild->rchild->rchild = NULL;

    T->rchild = (ThreadNode *)malloc(sizeof(ThreadNode));
    T->rchild->data = 3;
    T->rchild->lchild = NULL;

    T->rchild->rchild = (ThreadNode *)malloc(sizeof(ThreadNode));
    T->rchild->rchild->data = 6;
    T->rchild->rchild->lchild = NULL;
    T->rchild->rchild->rchild = NULL;
}

void InThread(ThreadTree &p, ThreadTree &pre) // 中序遍历线索二叉树
{
    if (p != NULL)
    {
        InThread(p->lchild, pre); // 递归线索化左子树
        if (p->lchild == NULL)    // 如果p结点的左孩子为NULL，也就是一个空指针域
        {
            p->lchild = pre; // 将原本指向左孩子的指针指向中序遍历的前驱结点
            p->ltag = 1;     // ltag为0表示指向的是左孩子结点，ltag为1表示指向的是中序遍历的前驱结点
        }
        if (pre != NULL && pre->rchild == NULL) // 判断p的前驱结点是否为空，右孩子指针是否为空
        {
            pre->rchild = p; // 将p的前驱结点pre的右孩子指针指向p
            pre->rtag = 1;   // rtag为0表示指向的是右孩子结点，rtag为1表示指向的是中序遍历的后继结点
        }
        pre = p;                  // 进行下一个结点的线索化
        InThread(p->rchild, pre); // 因为是中序遍历线索化，所以先递归线索化左子树，中间线索化根节点，最后递归线索化右子树
    }
}

ThreadNode *Firstnode(ThreadNode *p)//求中序序列下的第一个结点
{
    while(p->ltag == 0)//判断是否有左孩子 没有左孩子最后返回
    {
        p=p->lchild;
    }
    return p;
}

ThreadNode *Nextnode(ThreadNode *p)//寻找结点p在中序遍历下的后继
{
    if(p->rtag == 0)//如果rtag是0 说明rchild连接的是右孩子，所以将其看做成一个右子树，查询该右子树的中序遍历的第一个结点，得到的就是p的后继
    {
        return Firstnode(p->rchild);
    }
    else
    {
        return p->rchild;//如果rtag是1，说明rchild连接的就是后继结点，直接返回即可
    }
}


int main()
{
    ThreadTree Tree;
    createTree(Tree);
    ThreadNode* pre=NULL;
    InThread(Tree,pre);
    // printf("%d\n",Tree->lchild->rchild->lchild->lchild->data);//求7的前驱结点

    printf("FirstNode: %d \n",Firstnode(Tree)->data);
    printf("Tree->lchild Nextnode: %d \n",Nextnode(Tree->lchild)->data);
    return 0;
}