C语言数据结构学习笔记(12)-线索二叉树的创建和遍历

# include
# include
typedef enum {link, Thread} PointerTag;//link为0表示指向左右孩子结点,Thread为1表示设置前驱或后继结点
# define ElemType char
typedef struct BiThrNode{
    ElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag lTag, rTag;
}BiThrNode, *BiThrTree;
BiThrTree pre;//定义全局变量始终指向前一个访问的结点
void CreateBiThrTree(BiThrTree * proot);//创建线索二叉树
void InOrderThreading(BiThrTree root, BiThrTree * H);//中序线索化二叉树并加入头结点
void InThreading(BiThrTree p);//中序线索化二叉树
void InOrderTree(BiThrTree H);//中序遍历二叉树
void ReverseInOrderTree(BiThrTree H);//中序遍历二叉树逆序
int main(void)
{    
    BiThrTree root, H;
    CreateBiThrTree(&root);
    InOrderThreading(root, &H);
    printf("中序遍历：");
    InOrderTree(H);
    printf("n");
    printf("中序遍历逆序：");
    ReverseInOrderTree(H);
    printf("n");
    system("pause");
    return 0;
}
void CreateBiThrTree(BiThrTree * proot)//创建线索二叉树
{
    ElemType elem;
    scanf("%c", &elem);
    if('#' == elem)
        *proot = NULL;
    else
    {
        *proot = (BiThrTree)malloc(sizeof(BiThrNode));
        if(NULL == *proot)
            exit(-1);
        (*proot)->data = elem;
        CreateBiThrTree(&(*proot)->lchild);
        if((*proot)->lchild)
            (*proot)->lTag = link;
        CreateBiThrTree(&(*proot)->rchild);
        if((*proot)->rchild)
            (*proot)->rTag = link;
    }
}
void InOrderThreading(BiThrTree root, BiThrTree * H)//中序线索化二叉树并加入头结点
{
    *H = (BiThrTree)malloc(sizeof(BiThrNode));//建立头结点
    if(NULL == *H)
        exit(-1);
    (*H)->lTag = link;
    (*H)->rTag = Thread;
    (*H)->rchild = *H;//右指针回指
    if(root == NULL)
        (*H)->lchild = *H;//若二叉树空,则左指针回指
    else
    {
        (*H)->lchild = root;
        pre = *H;
        InThreading(root);
        pre->rchild = *H;
        pre->rTag = Thread;
        (*H)->rchild = pre;
    }
}
void InThreading(BiThrTree p)//中序线索化二叉树
{    
    if(NULL == p)
        return;
    InThreading(p->lchild);
    if(!p->lchild)
    {
        p->lTag = Thread;
        p->lchild = pre;
    }
    if(!pre->rchild)
    {    
        pre->rTag = Thread;
        pre->rchild = p;
    }
    pre = p;
    InThreading(p->rchild);
}
void InOrderTree(BiThrTree H)//中序遍历二叉树
{    
    BiThrTree p;
    p = H->lchild;
    while(p != H)
    {    
        while(p->lTag == link)
            p = p->lchild;
        printf("%c ", p->data);
        while(p->rTag == Thread && p->rchild != H)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }
        p = p->rchild;
    }
}
void ReverseInOrderTree(BiThrTree H)//中序遍历二叉树逆序
{
    BiThrTree p;
    p = H->rchild;
    while(p != H)
    {    
        while(p->rTag == link)
            p = p->rchild;
        printf("%c ", p->data);
        while(p->lTag == Thread && p->lchild != H)
        {
            p = p->lchild;
            printf("%c ", p->data);
        }
        p = p->lchild;
    }
}