线索二叉树的建立与遍历C语言实现过程详解

线索二叉树

1. 定义

n个结点有n-1个前驱和n-1个后继；一共有2n个链域，其中：n+1个空链域，n-1个指针域；因此, 可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。
用一张简单的图来了解一下线索二叉树与基本的二叉树的区别吧:

普通二叉树(图1)

线索二叉树(图2)

我们可以很清楚的看出,线索二叉树很好的利用了图1中的空指针的空间,使得这些指针能指向以中序遍历二叉树的方式的前驱与后继.不但解决二叉链表找左、右孩子困难的问题，也解决了无法在某个结点中直接找到该结点的前驱与后继的问题。

2. 结点结构

线索二叉树有5个域，比一般的二叉树要多出两个标志位的域：
Data域:存放数据的数据域
RChild域:指向右子结点(或后继结点)的指针
LChild域:指向左子结点(或前驱结点)的指针
RTag域:是一个标志域.当该域为0时,RChild是指向右子结点的指针.当该域为1时,则RChild是指向后继结点的指针.
LTag域:是一个标志域.当该域为0时,LChild是指向左子结点的指针.当该域为1时,则LChild是指向后继结点的指针.

头结点: 图中的Head结点.
根结点: 图中的A结点(二叉树的根结点).

3.二叉树的线索化

有效利用二叉链表中空的存储空间,指定原有的孩子指针为空的域来存放指向前驱和后继的过程,称为线索化.

简单点说:将二叉树变为线索二叉树的过程也就称为线索化.

4.线索二叉树的存储结构

//线索二叉树中的数据域的存储类型,使用宏定义能实现一改全改的效果
typedef char ElemType;

//枚举类型,代表着标志域指示的指针域指向的是子结点还是前驱后继结点,能更加方便直观的看懂代码
typedef enum {
    Link, Thread
} PointerTag;

//结点的存储结构
typedef struct BiThrNode {
    ElemType data;
    struct BiThrNode * lchild, * rchild;
    PointerTag ltag, rtag;
} BiThrNode, *BiThrTree;

5.线索二叉树的中序递归线索化过程

线索化过程看起来挺复杂,但是经过下面几个步骤的分解也就看起来不是那么的难啦~

1. 以前序创建普通二叉树的方式创建一个未初始化的线索二叉树,以递归的形式去创建,其中当输入的字符为’ ‘时,代表该树没有孩子结点.代码如下:

   //前序递归创建一个未线索化的二叉树
   //参数: tree 线索二叉树的根结点指针变量
   void createBiThrTree(BiThrTree * tree) {
       char c;
   
       scanf("%c", &c);
       if (' ' == c) { //若输入的是空格,则不创建该结点,使得递归可以结束
           * tree = NULL;
       } else {
   
           * tree = ((BiThrTree) malloc(sizeof(BiThrNode)));
           //设置其数据域
           (* tree)->data = c;
           //未线索化的过程
           (* tree)->ltag = Link;
           (* tree)->rtag = Link;
   
           //递归生成其左子结点
           createBiThrTree(&(* tree)->lchild);
           //递归生成其右子结点
           createBiThrTree(&(* tree)->rchild);
       }
   }

2. 定义一个全局BiThrNode* 类型的指针变量pre(顾名思义就是上一个创建出来的结点),用于在递归生成结点的时候,记录上次的结点用于让生成的结点的前驱指针指向前驱的结点,然后再通过判断,若该pre结点rchild指针没有所指向,让其指向后继的结点(就是刚刚生成的结点).

   BiThrNode *pre = NULL;

3. 增设一个头结点，令其lchild指向二叉树的根结点，ltag=0、rtag=1；并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；最后用头指针指示该头结点。其rchild域的指针指向中序遍历时访问的最后一个结点；反之，令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点rchild域的指针均指向头结点，这好比为二叉树建立了一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

   //创建头结点.
   //参数: head 作为指向头结点的结点指针变量, tree 线索二叉树的根结点指针变量
   void inOrderThreading(BiThrTree * head, BiThrTree tree) {
       //创建头结点
       * head = (BiThrTree) malloc(sizeof(BiThrNode));
       //设置该头结点的左右标志位分别为非线索与线索
       //递归线索化的过程能使得第一个结点的前驱正确指向该头结点.
       (* head)->ltag = Link;  
       (* head)->rtag = Thread;
       if (!tree) {
           //若根结点不存在,则该二叉树为空,让该头结点指向自身.
           (* head)->lchild = * head;
       } else {
           //令头结点的左指针指向根结点
           (* head)->lchild = tree;
           pre = * head;
           //开始递归输入线索化
           inThreading(tree);
           //此时结束了最后一个结点的线索化了,下面的代码把头结点的后继指向了最后一个结点.
           //并把最后一个结点的后继也指向头结点,此时树成为了一个类似链表的循环.
           pre->rchild = * head;
           pre->rtag = Thread;
           (* head)->rchild = pre;
       }

上述代码即如下图所示的红线内的建立头结点的过程.

1. 补全inThreading函数,使得其依次中序递归线索化子结点,此过程就是上图中红线之外的部分.
   代码如下:

   //中序遍历线索化
   //参数: tree 线索二叉树的根结点指针变量
   void inThreading(BiThrTree tree) {
       if (tree) {
   
           inThreading(tree->lchild); //递归左孩子线索化
   
           //中序遍历处理内容
           if (!tree->lchild) { //如果该结点没有左孩子,设置ltag为Thread,并把lChild指向前驱结点
               tree->ltag = Thread;
               tree->lchild = pre;
           }
   
           if (!pre->rchild) {//处理pre结点(也就是上一个创建的结点),若其无右孩子,则令pre的rChild指向后继结点
               pre->rtag = Thread;
               pre->rchild = tree;
           }
   
           pre = tree;//令pre全局变量指向已经处理完毕的结点,令下个结点继续处理
           //中序遍历处理结束
   
           inThreading(tree->rchild);//递归右孩子线索化
       }
   }

---

经过上面几个并不是很长的代码,我们就把新建的二叉树给线索化啦~
如果感觉并不能很好地了解上面的描述,可以在纸上去一步步地去演算整个递归过程~

6.迭代的形式去中序遍历该线索二叉树

相信大家看到线索二叉树的存储结构也差不多知道怎么利用两个标签位去遍历整个线索二叉树了吧,下面就是代码:

//以迭代的形式去中序遍历线索二叉树.
int inOrderTraverseThr(BiThrTree T) {

    BiThrTree p = T->lchild;    //令p先指向根节点.

    //退出循环的条件是p重新指回了头结点.
    while (p != T) {

        while (p->ltag == Link)
            p = p->lchild;  //迭代令p指向左子树为空的结点.

        visit(p->data);

        //如果该结点没有右子结点,则不执行下面while语句里面的语句,即令下次循环遍历该结点的右子结点.
        //如果下一个节点就是头结点,则也不进入下面while语句的循环体中.
        //下面的语句就是利用Thread的作用直接去判断,从而调用下一个需要遍历的结点(线索化的优点就出来了).
        while (p->rtag == Thread && p->rchild != T) {
            p = p->rchild;
            visit(p->data);
        }

        //令p指向下一个结点,可以是右子结点,也可以是后继结点,取决于此时tag域的信息.
        p = p->rchild;

    }


    return 1;
}

//访问该数据的函数,这里就简单的打印出来.
void visit(ElemType data) {
    printf("%c", data);
}

7. main()函数

过程很简单,先创建二叉树,再进行线索化,最后进行迭代遍历:

int main() {

    BiThrTree tree = NULL, head = NULL;

    //创建二叉树
    createBiThrTree(&tree);
    //线索化二叉树的过程
    inOrderThreading(&head, tree);
    printf("中序遍历的结点为:");
    //遍历整棵线索二叉树
    inOrderTraverseThr(head);

    printf("\n");
    return 1;
}

8. 注意的部分:

1. 如上图所示的测试输入数据部分,我们需要输入(space代表着空格):
   ABC(space)D(space)(space)(space)E(space)FG(space)(space)H(space)(space)
   原因很简单,因为我们在创建二叉树的过程中判断空格是否为标准去结束这个递归过程.
2. 时间复杂度:
   创建二叉树的过程:O(n)
   线索化的过程:O(n)
   中序遍历的过程:O(n)

9. 其他部分

这里安利两个flash动画去让大家更好的理解整个线索化的过程:

1. 动画:中序线索二叉树
2. 动画:寻找中序线索二叉树指定结点的后继

本文的源代码下载:
https://github.com/Crainax/DemoCode/blob/master/C/DataStructures/BinaryThreadTree.c

10. 文章参考

• 【树】线索二叉树概念
• 17、线索二叉树的生成和遍历