C语言-数据结构-线索二叉树-生成、遍历源代码

小咪咪 2022-07-15 00:08 174阅读 0赞

**1. 目标**

按前序遍历的顺序生成一个二叉树（如下图1所示），然后按照中序遍历的顺序进行线索化，利用空余的左节点指向前驱节点，空余的右节点指向后续节点。最有利用迭代的方式将其输出。

![Center][]

**2. 运行示例**

![Center 1][]

其中函数HDThreadTree（）后，二叉树的情形如下：

![Center 2][]

**3. 源代码**

程序流程图及代码如下。

**![Center 3][]**

<span style="font-size:14px;">#include <stdio.h>
    #include <stdlib.h>
    #define title "------------------------------Life is a fight!------------------------------------"
    
    typedef char elemtype;
    
    /*标识是指向孩子还是存储线索*/
    /*0-指向孩子， 1-存储线索*/
    typedef enum {link, thread} flag;
    
    typedef struct Tree{
         flag lflag, rflag;
         struct Tree *lchild, *rchild;
         elemtype data;
         } treenode, *ptrtree;
    
    ptrtree pre; //该全局变量用于记录刚刚访问过的前驱节点
    
    /*按照前序遍历输入并创建二叉树，如果没有子节点用空格代替*/
    void CrtTree(ptrtree *t)
    {
        elemtype c;
        c=getchar();
        if(' '==c)
        {
           *t=NULL;
        }
        else
        {
            *t=(ptrtree)malloc(sizeof(treenode));
            (*t)->data=c;
            (*t)->lflag=link;//默认flag 为link, 即指向自己的子节点
            (*t)->rflag=link;
            CrtTree(&((*t)->lchild));
            CrtTree(&((*t)->rchild));
        }
    }
    
    /*按中序遍历的顺序访问二叉树，如果该节点的左孩子为空，则将其指向前驱节点，如果该节点的右孩子为空，则将其指向后继节点*/
    void ThreadTree(ptrtree t)
    {
        if(t)//如果指针为零则不进行任何操作
        {
           ThreadTree(t->lchild); //首先递归，直到最左边的左孩子为止
    
           if(!t->lchild)//指向前驱节点的情况
           {
                t->lflag=thread;
                t->lchild=pre;//pre的初始值在HDThreadTree()函数中赋值，此后pre按中序遍历的顺序依次记录遍历的足迹
           }
           if(!pre->rchild)//指向后继节点的情况
           {
               pre->rflag=thread;
               pre->rchild=t;
           }
           pre=t; //pre 变量的初始化，pre获得的第一个值是最左边的节点
           ThreadTree(t->rchild);
        }
    }
    
    /**********************************************************************/
    /*该函数为线索化后的二叉树加上头指针，使其成为一个环，方便后续迭代访问*/
    /*t-传入的二叉树；h-给二叉树加上的头指针*/
    /**********************************************************************/
    void HDThreadTree(ptrtree t, ptrtree *h)
    {
        *h=(ptrtree)malloc(sizeof(treenode));
        (*h)->lflag=link;
        (*h)->rflag=thread;
        (*h)->rchild=*h;//头指针的右孩子指向头指针自身
        if(!t)//如果t为0，则左孩子也指向头指针自身
        {
           (*h)->lflag=thread;
           (*h)->lchild=*h;
        }
        else
        {
            (*h)->lchild=t;//头指针的左孩子指向二叉树
            pre=*h;//进入ThreadTree()函数之前，给pre初始值，指向头指针所指向的内存空间
            ThreadTree(t);
            pre->rflag=thread;//运行ThreadTree()函数后，pre=最右边的节点
            pre->rchild=*h;
            (*h)->rchild=pre;
        }
    }
    
    void VisitNode(elemtype c)
    {
        printf("%c", c);
    }
    
    /************************************************************************************/
    /*输入一个二叉树的头节点，通过迭代的方式按中序遍历的方式访问并打印节点的数据        */
    /*首先找到最最左端的左节点，然后依靠右线索访问后续节点，如果不存在线索，则访问右孩子*/
    /*由于是中序遍历，所以没有指向后续节点的线索的情况下，访问右孩子也是正确的访问顺序                */
    /************************************************************************************/
    void InorderTraverse(ptrtree h)
    {
        ptrtree p;
        p=h->lchild;
    
        while(p!=h)//如果尚未遍历完一圈，接着往下执行
        {
            while(p->lflag==link)//先找到最左边左节点，也是中序遍历的第一个节点
            {
                p=p->lchild;
            }
            VisitNode(p->data);
    
            while(p->rflag==thread&&p->rchild!=h)//由于右线索记录的是后续节点，所以如果该节点的右孩子为线索，可以直接访问该线索，找到后续节点并打印
            {
                p=p->rchild;
                VisitNode(p->data);
            }
    
            p=p->rchild;//向右移动
        }
    }
    
    
    int main(void)
    {
        ptrtree h, t=NULL;
        printf("%s\n\n",title);
        printf("Please enter the data:\n");
        CrtTree(&t);
        HDThreadTree(t, &h);
        printf("\nThe result of inorder traverse is: ");
        InorderTraverse(h);
        printf("\n");
        return 0;
    }</span>

[Center]: /images/20220715/a2b207f593e44de28c70e1d704678ade.png
[Center 1]: /images/20220715/930310f45d75429c803830ba14b8310e.png
[Center 2]: /images/20220715/5f3fd6014e4441fda00d414dbb663c1e.png
[Center 3]: /images/20220715/0c58a94179cc41eb8cb5829455925642.png