C语言-数据结构-树的索引化

我就是我 2022-05-16 01:05 160阅读 0赞

/*
        Name: 二叉树的线索化 
        Copyright: 2015117350
        Author: 莫 
        Date: 13/08/18 18:32
        Description: 
            (1)首先动态建立树,使用空格为NULL    先序
            (2)对新建的树进行遍历加入索引       中序遍历加入索引
            (3)遍历索引后的树                 中序
    
            由于本人考研有考到这方面,所以使用dev C++, 使用语言是C语言 
        在网上看了很多比如小甲鱼的视频(其中一些函数的定义和参数传递上面不太合适C语言)
        西安电子科技大学的视频重在解释原理,所以本人在网上又找了一下. 
        感谢 CSDN博主 小与米 二叉树的线索化 (理论部分非常详细,连我这个笨鸟都看懂了) 
        https://blog.csdn.net/c18219227162/article/details/50188579
        对于小与米的程序改进后, 成功实现功能,且程序加以注释后基本可以看懂  
    */
    
    /*
    
    由于线索二叉树构造的实质是将二叉链表中的空指针改为指向前驱
    和后继的线索，而前驱和后继的信息只有在遍历时才能得到
    
     LTag=0时，lchild域指示结点的左孩子 LTag=1时，lchild域指示结点的前驱。
     RTag=0时，rchild域指示结点的右孩子 RTag=1时，rchild域指示结点的后继。
    
    线索化过程: 
    1)左子树线索化
    2)对空指针线索化：
      ①如果p的左孩子为空，则给p加上左线索，将其LTag置为1，让p的左孩子指针指向pre(前驱);
      ②如果pre的右孩子为空，则给pre加上右线索，将其RTag置为1，让pre的右孩子指针指向p(后继);
    3)将pre指向刚访问过的结点p，即pre = p;
    4)右子树线索化。
    
    */

#include "stdio.h"
    #include "stdlib.h"
    #include "malloc.h"
    #include "stdbool.h"
    
    /* 变量体声明区 */
    typedef char elemType; 
    
    /* 结构体声明: */
    typedef struct BTNode  //binary tree
    {
        elemType data;
        struct BTNode *pLchild; // p是指针 L是左 child 孩子
        struct BTNode *pRchild; 
        int lTag,rTag; 
    } *PThrBiTr,ThrBiTrN;
    
    /* 全局变量声明区 */ 
    PThrBiTr pre; //用于一直指向树结点的上一个结点地址 
    
    /* 函数声明区 */
    void CreateBiTr(PThrBiTr *T);   //先序遍历创建二叉树
    void InThreading( PThrBiTr *P );    //以结点P为根的线索化
    //因为主函数中未用到 InThreading函数,在声明中可以不加 
    
    void InOrderThreading(PThrBiTr *T);//添加头结点的二叉树线索化 
    void InOrderTraverse_Thr(PThrBiTr T);   //遍历线索化后的二叉树 
    
    
    
    void main()
    {
        PThrBiTr T = NULL;
        CreateBiTr( &T ); // 先序遍历顺序新建二叉树 
        InOrderThreading( &T ); // 中序线索二叉树 
        InOrderTraverse_Thr( T );   //线索二叉树的中序遍历 
    
        printf("\nHello world!!\n");
        return;
    } 
    
    
    
    
    
    /* 按先序次序输入二叉树中结点的值(一个字符)， 创建二叉链表 表示的二叉树T */
    void CreateBiTr(PThrBiTr *T)
    {
        char ch;
        scanf("%c",&ch); 
        if(' ' == ch) 
        {
            *T=NULL;
            return;
        }
        else
        {
            *T = (PThrBiTr)malloc(sizeof(ThrBiTrN));
            (*T)->data = ch;
            CreateBiTr( &(*T)->pLchild );
            CreateBiTr( &(*T)->pRchild );
        }
        return;
    }
    
    
    /* 以结点p为根的子树中序线索化 */
    void InThreading( PThrBiTr *P )
    {
        if( *P )    
        {
            InThreading( &(*P)->pLchild );  /*第一步 左子树递归线索化*/
    
    // if(!(P->pLchild) ) /*p的左孩子为空*/
            if(NULL == (*P)->pLchild)
            {                  
                (*P)->lTag = 1;     /*给p加上左线索*/
                (*P)->pLchild = pre;    /*p的左孩子指针指向pre(前驱)*/
            }
            else
            {
                (*P)->lTag=0;   //不是空则lTag为0 
            }
    
            if(!(pre->pRchild) )        /*pre的右孩子为空*/
            {
       //开始时pre的右孩子指向head不为空 
                pre->rTag = 1;          /*给pre加上右线索*/
                pre->pRchild = *P;      /*pre的右孩子指针指向p(后继)*/
            }
            else
            {
                pre->rTag=0;
            }
    
            pre = *P;                            /*保持pre指向p的前驱*/
            InThreading( &(*P)->pRchild );           /*右子树递归线索化*/
        }
    }
    
    
    /*添加 头结点的中序线索化*/
    void InOrderThreading(PThrBiTr *T)//BiThrTree &Thrt,BiThrTree T)
    {
        /*中序遍历二叉树T，并将其中序线索化，Thrt指向头结点*/
        PThrBiTr Head = (PThrBiTr)malloc(sizeof(ThrBiTrN));      /*建头结点*/
        Head->data = '0';
        Head->lTag = 0; //头结点的左孩子指向根结点, 头结点的右孩子指向它本身 
        Head->rTag = 1;
        Head->pRchild = Head;   //初始化时 头结点右孩子指向自己
    
        if( !(*T) )//如果树为空, 头结点的左结点指向自己 
        {
            Head->pLchild = Head;  
        } 
        else
        {
            Head->pLchild = *T;  //头结点的左孩子指向根结点 
    
            pre = Head; //pre初始指向头结点
    
            InThreading( &(*T) ); //这里只使用pre的左部分作为寻找前驱结点的标识 
    
            pre->rTag = 1;  //最终程序结束后 pre代表最后一个元素,既最后一个元素的右孩子指向头结点 
            pre->pRchild = Head;
            Head->pRchild = pre;
            *T = Head;      
        }
        return;
    }  
    
    /*遍历中序 已经添加头结点的线索二叉树*/
    void InOrderTraverse_Thr(PThrBiTr Head)  
    {
        /*T指向头结点，头结点的左链pLchild指向根结点*/
        /*中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出*/
        PThrBiTr P = Head->pLchild;    /*P指向根结点*/        
        while( P != Head )      
        //头结点和根结点只有在 空树或者遍历到根结点的时候 才会相等 
        {
            while(P->lTag == 0)      /*沿左孩子向下*/
            {
                 P = P->pLchild;    //直到找到最后一个左孩子(叶子) 
            }
    
            printf("%c ",P->data);           /*访问其左子树为空的结点*/
    
            while(P->rTag == 1 && P->pRchild != Head)  /*沿右线索访问后继结点, 且右孩子并没有指向根结点*/
            {
                P = P->pRchild;
                printf("%c ",P->data); 
            }
    
            P = P->pRchild;
        }
    }