C语言数据结构——线索二叉树

素颜马尾好姑娘i 2021-12-03 20:23 373阅读 0赞

> **线索二叉树与二叉树的不同在于，线索二叉树多了两个标识域，便于二叉树寻找前驱和后继，使得遍历二叉树的效率大大提高**

typedef struct tree
    {
        char data;
        int Ltag,Rtag;
        struct tree *Lchild,*Rchild;
    }Tree;

> **其中Ltag和Rtag为标识域，其意义为：**
> 
>  *  **如果Ltag = 0，则表示Lchild为指针，指向节点的左孩子；如果Ltag = 1，则表示Lchild为线索，指向节点的直接前驱**
>  *  **如果Rtag = 0，则表示Rchild为指针，指向节点的右孩子；如果Rtag = 1，则表示Rchild为线索，指向节点的直接后继**

**1.创建二叉树**

void CreateTree(Tree *&T)   //先序遍历创建二叉树
    {
        char ch;
        scanf(" %c",&ch);       //输入数据域信息
        if(ch == '#')
            T = NULL;
        else
        {
            T = (Tree*)malloc(sizeof(Tree));    //为新建节点申请堆空间
            T->data = ch;
            T->Ltag = 0;            //标识域初始化为0
            T->Rtag = 0;
            CreateTree(T->Lchild);  //递归创建左子树
            CreateTree(T->Rchild);  //递归创建右子树
        }
    }

**2.创建线索二叉树**

void CreateInThread(Tree *T)    //创建线索二叉树
    {
        Tree *pre = NULL;           //前驱节点指针
        if(T)
        {
            //PreThread(T,pre);       //先序线索化
           InThread(T,pre);        //中序线索化
           // PostThread(T,pre);      //后序线索化
            pre->Rchild = NULL;       //非空二叉树，线索化
            pre->Rtag = 1;            //最后处理最后一个节点
        }
    }

## 线索化 ##

**1.先序线索化**

void PreThread(Tree *p,Tree *&pre)  //先序线索化
    {
        if(p)
        {
            if(p->Lchild == NULL)
            {
                p->Lchild = pre;
                p->Ltag = 1;
            }
            if(pre != NULL && pre->Rchild == NULL)
            {
                pre->Rchild = p;
                pre->Rtag = 1;
            }
            pre = p;
            if(p->Ltag == 0)
            {
                PreThread(p->Lchild,pre);
            }
            if(p->Rtag == 0)
            {
                PreThread(p->Rchild,pre);
            }
        }
    }

**2.中序线索化**

void InThread(Tree *p,Tree *&pre)   //中序线索化
    {
        if(p)
        {
            InThread(p->Lchild,pre);    //左子树递归线索化
            if(p->Lchild == NULL)       //若左孩子为空
            {
                p->Lchild = pre;        //左孩子指向当前节点的前驱节点
                p->Ltag = 1;            //前驱标识域置为1
            }
            if(pre != NULL && pre->Rchild == NULL)  //若前驱节点非空且其右子树为空
            {
                pre->Rchild = p;         //前驱节点的后继指向当前节点
                pre->Rtag= 1;            //后继标识域置为1
            }
            pre = p;                    //pre指向当前的p，作为p将要指向的下一个节点的前驱节点指示节点
            InThread(p->Rchild,pre);    //右子树递归线索化
        }
    }

**3.后序线索化**

void PostThread(Tree *p,Tree *&pre)    //后序线索化
    {
        if(p)
        {
            PostThread(p->Lchild,pre);
            PostThread(p->Rchild,pre);
            if(p->Lchild == NULL)
            {
                p->Lchild = pre;
                p->Ltag = 1;
            }
            if(pre != NULL && pre->Rchild == NULL)
            {
                pre->Rchild = p;
                pre->Rtag = 1;
            }
            pre = p;
        }
    }

# 遍历 #

**1.先序遍历**

void PreOrder(Tree *T)              //先序遍历
    {
        if(T)
        {
            Tree *p = T;                //定义辅助节点指向根节点
            while(p)
            {
                while(p->Ltag == 0)     //依次访问每个节点的左子树，直至左子树为空
                {
                    printf(" %c\t",p->data);
                    p = p->Lchild;
                }
                printf(" %c\t",p->data);    //此时p左指针必为线索，但还没有被访问
                p = p->Rchild;          //此时p左孩子不存在，若右指针非空，则不论是否为线索都指向其后继
            }
        }
    }

**2.中序遍历**

Tree *First(Tree *T)                //返回中序遍历第一个节点
    {
        while(T->Ltag == 0)             //找到第一个左孩子为空的节点，即为中序遍历第一个节点
        {
            T = T->Lchild;
        }
        return T;
    }
    Tree *Next(Tree *T)                 //返回节点的后继节点
    {
        if(T->Rtag == 0)                //若右孩子存在，则返回右子树中序遍历的第一个节点即为节点的后继
        {
            return First(T->Rchild);
        }
        else
        {
            return T->Rchild;
        }
    }
    void InOrder(Tree *T)               //中序遍历
    {
        for(Tree *p = First(T); p != NULL; p =  Next(p))  //从第一个节点开始，依次访问其后继节点
        {
            printf("%c\t",p->data);
        }
    }

# 代码实现 #

> **如果用对二叉树使用先序线索化，遍历时就要用先序遍历线索二叉树，同理，用中序线索化，遍历时就要用中序遍历**

#include <stdio.h>
    #include <stdlib.h>
    typedef char TElemType;
    typedef struct tree
    {
        TElemType data;
        int Ltag,Rtag;
        struct tree *Lchild,*Rchild;
    } Tree;
    void CreateTree(Tree *&T);
    void CreateInThread(Tree *T);
    void InThread(Tree *p,Tree *&pre);
    Tree *First(Tree *T);
    void InOrder(Tree *T);
    Tree *Next(Tree *T);
    void PreThread(Tree *p,Tree *&pre);
    void PostThread(Tree *p,Tree *&pre);
    void PreOrder(Tree *T);
    void InOrder1(Tree *T);
    int main()
    {
        Tree *T;
        printf("请开始创建二叉树:\n");
        CreateTree(T);
        printf("----开始线索化----\n");
        CreateInThread(T);
        printf("----线索化完成!----\n");
        InOrder(T);
       //PreOrder(T);
    }
    void CreateTree(Tree *&T)   //先序遍历创建二叉树
    {
        char ch;
        scanf(" %c",&ch);       //输入数据域信息
        if(ch == '#')
            T = NULL;
        else
        {
            T = (Tree*)malloc(sizeof(Tree));    //为新建节点申请堆空间
            T->data = ch;
            T->Ltag = 0;            //标识域初始化为0
            T->Rtag = 0;
            CreateTree(T->Lchild);  //递归创建左子树
            CreateTree(T->Rchild);  //递归创建右子树
        }
    }
    void CreateInThread(Tree *T)    //创建线索二叉树
    {
        Tree *pre = NULL;           //前驱节点指针
        if(T)
        {
            //PreThread(T,pre);       //先序线索化
           InThread(T,pre);        //中序线索化
           // PostThread(T,pre);      //后序线索化
            pre->Rchild = NULL;       //非空二叉树，线索化
            pre->Rtag = 1;            //最后处理最后一个节点
        }
    }
    void InThread(Tree *p,Tree *&pre)   //中序线索化
    {
        if(p)
        {
            InThread(p->Lchild,pre);    //左子树递归线索化
            if(p->Lchild == NULL)       //若左孩子为空
            {
                p->Lchild = pre;        //左孩子指向当前节点的前驱节点
                p->Ltag = 1;            //前驱标识域置为1
            }
            if(pre != NULL && pre->Rchild == NULL)  //若前驱节点非空且其右子树为空
            {
                pre->Rchild = p;         //前驱节点的后继指向当前节点
                pre->Rtag= 1;            //后继标识域置为1
            }
            pre = p;                    //pre指向当前的p，作为p将要指向的下一个节点的前驱节点指示节点
            InThread(p->Rchild,pre);    //右子树递归线索化
        }
    }
    Tree *First(Tree *T)                //返回中序遍历第一个节点
    {
        while(T->Ltag == 0)             //找到第一个左孩子为空的节点，即为中序遍历第一个节点
        {
            T = T->Lchild;
        }
        return T;
    }
    Tree *Next(Tree *T)                 //返回节点的后继节点
    {
        if(T->Rtag == 0)                //若右孩子存在，则返回右子树中序遍历的第一个节点即为节点的后继
        {
            return First(T->Rchild);
        }
        else
        {
            return T->Rchild;
        }
    }
    void InOrder(Tree *T)               //中序遍历
    {
        for(Tree *p = First(T); p != NULL; p =  Next(p))  //从第一个节点开始，依次访问其后继节点
        {
            printf("%c\t",p->data);
        }
    }
    void PreThread(Tree *p,Tree *&pre)  //先序线索化
    {
        if(p)
        {
            if(p->Lchild == NULL)
            {
                p->Lchild = pre;
                p->Ltag = 1;
            }
            if(pre != NULL && pre->Rchild == NULL)
            {
                pre->Rchild = p;
                pre->Rtag = 1;
            }
            pre = p;
            if(p->Ltag == 0)
            {
                PreThread(p->Lchild,pre);
            }
            if(p->Rtag == 0)
            {
                PreThread(p->Rchild,pre);
            }
        }
    }
    void PostThread(Tree *p,Tree *&pre)    //后序线索化
    {
        if(p)
        {
            PostThread(p->Lchild,pre);
            PostThread(p->Rchild,pre);
            if(p->Lchild == NULL)
            {
                p->Lchild = pre;
                p->Ltag = 1;
            }
            if(pre != NULL && pre->Rchild == NULL)
            {
                pre->Rchild = p;
                pre->Rtag = 1;
            }
            pre = p;
        }
    }
    void PreOrder(Tree *T)              //先序遍历
    {
        if(T)
        {
            Tree *p = T;                //定义辅助节点指向根节点
            while(p)
            {
                while(p->Ltag == 0)     //依次访问每个节点的左子树，直至左子树为空
                {
                    printf(" %c\t",p->data);
                    p = p->Lchild;
                }
                printf(" %c\t",p->data);    //此时p左指针必为线索，但还没有被访问
                p = p->Rchild;          //此时p左孩子不存在，若右指针非空，则不论是否为线索都指向其后继
            }
        }
    }