数据结构（十七） -- C语言版 -- 树 - 二叉树的线索化及遍历 -- 先序线索化、中序线索化、后序线索化

心已赠人 2023-02-15 05:25 2阅读 0赞

### 内容预览 ###

*  零、读前说明
 *  一、线索化概述
 *  二、中序线索化及其遍历
 *   *  2.1、线索化过程说明
     *  2.2、遍历过程说明
     *  2.3、线索化及遍历的代码实现
     *  2.4、线索化的测试
     *   *  2.4.1、测试案例工程结构
         *  2.4.2、测试案例代码
         *  2.4.3、测试效果图
 *  三、先序线索化及其遍历
 *   *  3.1、线索化过程说明
     *  3.2、遍历过程说明
     *  3.3、线索化及遍历的代码实现
     *  3.4、线索化的测试
 *  四、后序线索化及其遍历
 *   *  4.1、线索化过程说明
     *  4.2、遍历过程说明
     *  4.3、线索化及遍历的代码实现
     *  4.4、线索化的测试
 *  五、总结

# 零、读前说明 #

*  本文中所有设计的代码均通过测试，并且在功能性方面均实现应有的功能。
 *  设计的代码并非全部公开，部分无关紧要代码并没有贴出来。
 *  如果你也对此感兴趣、也想测试源码的话，可以私聊我，非常欢迎一起探讨学习。
 *  由于时间、水平、精力有限，文中难免会出现不准确、甚至错误的地方，也很欢迎大佬看见的话批评指正。
 *   嘻嘻。。。。 。。。。。。。。收！

既然你已经打开这篇了，那么我还是想推荐再去看看这一篇：

[数据结构（十七） – C语言版 – 树 - 二叉树的线索化及遍历 – 先序线索化、中序线索化、后序线索化][_ C_ _ _ - _ _]

上面这个系列已经用**先序线索化**的方式，说明了使用**左指针域线索化**、**链表线索化**、**顺序表线索化**等等的方式。但是在结尾的时候也已经说明比较明显的缺点：

左指针域线索化会修改原本二叉树的结构和逻辑关系 — 物是人非  
  顺序表线索化有内存空间的问题，并且插入删除节点复杂 — 女孩的心思猜不到  
  链表线索化为单向链表，只能确定后继 — 给不了Ta想要的幸福  
  链表线索化为双向链表，占地大 — 你知我深浅，我知你宽窄  
  链表线索化为双向循环链表 ，占地大— 手拉手的幸福甜死狗

下面就开始说明一种将二叉树线索化的常规、主流的方式。

# 一、线索化概述 #

对于一个二叉树来说，其二叉链表表示形式中正好有**两个指针域**，**一个左子树指针域，一个右子树指针域**。并且对于一个有 n 个节点的二叉链表， 每个节点有指向左右孩子的两个指针域，所以共是 2n 个指针域。而 n 个节点的二叉树一共有 n-1 条分支数，也就是说，其实是存在 2n-(n-1) = n+l 个空指针域。（摘自《大话数据结构》 P189 ）。也就是说在上面的这个二叉树中，有 7 个节点（ABCDEFG ），那么就有8个空指针，将这些空指针利用起来（不同于前面提到的做指针域线索化），将其中一个指针用作前驱指针，另一个指针指向后继指针，那么这样的话就不需要额外的空间了。

我们还是以下面的这个二叉树进行说明。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center]

图1.1 二叉树、二叉链表表示示意图

我们已经知道了，二叉树的遍历有四种方式：**先序遍历、中序遍历、后序遍历、层序遍历。**

那么根据遍历来进行线索化的方式也就有四种方式：**先序线索化、中序线索化、后序线索化、层序线索化**，其实严格意义上来说，除了遍历的顺序不同，其他的没什么太大的区别。对于线索化来将也是一样的。

所以，**如果这个节点的左指针域是空的，那么就让其指向前驱，如果这个节点的右指针域为空，那么就让其指向后**继，所以，四种线索化的示意图可以表示为下图这样。(其中 红色线条 表示前驱、 蓝色线条 表示为后继，均称为 **线索**。)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 1]

图1.2 各种不同顺序线索化的示意图

原节点中的为空的指针域都用来表示 **前驱和后继** 了，也就是除了 **遍历顺序中第一个节点** 和 **最后一个节点存在空指针域外**，其余的节点的空指针域已经用来保存线索了。

从上面的示意图中我么可以看出来，每一个节点的左指针域和右指针域都都可以被使用，但是对于**叶子节点**（ GEF ）或者存在一个空子树的节点（ DC ）来说，其**空指针域保存的是线索**，但是对于其他的节点来说（ AB ），不存在空指针域，而我们已知使用**二叉链表表示的二叉树的存储结构**为下面的这样的。

/* 二叉链表表示法的结构模型 */
    typedef struct BiTNode
    { 
        TElemType data;         /* 节点数据 */
        struct BiTNode *lchild; /* 左孩子 */
        struct BiTNode *rchild; /* 右孩子 */
    } BiTNode;

那对于上面的描述，原来的二叉链表的节点中包含了两个指针域（左右指针）、一个数据域，**很难确定节点的两个指针域保存的是子树还是线索**了。那么为了解决这样的问题，我们需要在结构定义的基础上**加入两个标志位**（ lTag、rTag ）分别用来表示当前指针的指向的含义。

那么加入标志位之后其结构可以表示为下图这样。  
    
![在这里插入图片描述][20200611171326935.png_pic_center]

图1.3 加入标志位之后树的数据结构

其中， lTag、rTag 的标志可以总结为：  
    当 lTag = 0 : lchild 指向节点的左孩子  
    当 lTag = 1 : lchild 指向节点的前驱节点

当 rTag = 0 : rchild 指向节点的右孩子  
    当 rTag = 1 : rchild 指向节点的后继节点

所以将上面图示中的节点的二叉树的存储结构表示为下面的这样的。

/* 加入线索标识二叉链表表示法的结构模型 */
    typedef struct BiTNode
    { 
        TElemType data;         /* 节点数据 */
        struct BiTNode *lchild; /* 左孩子 */
        struct BiTNode *rchild; /* 右孩子 */
        int lTag;				/* 左孩子-线索标识 */
        int rTag;				/* 右孩子-线索标识 */
    } BiTNode;

那么下面我们就开始按照先序线索化、中序线索化、后序线索化分别来进行说明表示。

# 二、中序线索化及其遍历 #

好，首先来说明一下**中序线索化**的过程及其遍历吧。  
  啊你说我为什么要先进行中序线索化而不是其他的？  
  哈哈哈，当然是因为爱情啊(\*▔＾▔\*) 。。。。。  
  好了，都三百斤的人了，稳重点好！这个主要是因为呀，**中序线索化比较简单，而且线索化也比较完善**。所以先说明中序线索化。然后在**对比性的说明先序线索化和后序线索化**。

## 2.1、线索化过程说明 ##

开始中序线索化：在中序遍历的基础上进行线索化，  
  首先在中序线索化之前，先定义两个指针变量，用来辅助我们说明。

current :  为当前访问的节点  
     prev  :  为之前访问的最后一个节点，也就是 current 之前访问的节点。

对于中序遍历，我们首先传入输的根节点，然后开始遍历，那么中序遍历的第一个节点为 D 节点。所以此时：

current 指针指向节点 D ， prev 指针为 NULL ，如下图所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_4_color_000000_t_10_pic_center]

图2.1 中序线索化的示意图1

在当前节点 D 下，其**左子树指针域为空，所以需要将其线索化为前驱节点**，但是节点 D 为遍历中的**第一个节点，是没有直接前驱**的，所以，应该(图中 翠绿色 表示)。

current->lTag = 1;   
    current->lchild = prev = NULL;

根据中序遍历，接下来应该是节点 D 的**右子树的判断并遍历**，明显节点 D 存在右子树。所以访问 G 节点。  
  但是在访问我们将 prev 指向 current 指针，让 prev 指针跟上 current 指针(下图中 天蓝色虚线 表示)。  
    
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 2]

图2.2 中序线索化的示意图2

继续遍历，将在当前指针 current 移动到第二个节点 G 下，其**左子树指针域为空，所以需要将其线索化为前驱节点**，而其前驱节点为 D ，正**好保存在** prev **指针**中，所以应该(下图中 天蓝色 表示)：

current->lTag = 1;  
    current->lchild = prev;

然后判断 prev 的**右子树不为空，不需要进行相关操作**。  
  操作完成，我们将 prev 指向 current 指针，让 prev 指针跟上 current 指针(图中 草绿色 表示)。  
    
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 3]

图2.3 中序线索化的示意图3

继续遍历，将在当前指针 current 移动到第三个节点 B 下，其**左子树指针域不为空，所以不需要将其线索化。**  
  然后判断 prev 的**右子树为空**，那么需要进行线索化了。将此指针线索化成节点 G 的**后继节**点 B ，此时（下图中用 草绿色 表示）。

prev->rTag = 1;  
    prev->rchild = current;

操作完成，我们将 prev 指向 current 指针，让 prev 指针跟上 current 指针(图中 橙色虚线 表示)。  
    
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 4]

图2.4 中序线索化的示意图4

继续遍历，将当前指针 current 移动到下个节点 B 右子树 E 下，节点 E 和节点 G 都是**叶子节点，所以既需要线索化前驱也需要线索化后继节点。**

首先来进行前驱线索化，那么前驱线索化可以表示为（下图中 橙色 表示）。

current->lTag = 1;  
    current->lchild = prev;

然后将 prev 指针跟上 current 指针，即可完成前驱线索化（用 紫色虚线 表示）。

然后 current 指针移动到 A 节点，且节点 A 的**左右子树均存在**，**所以也就不需要线索化了**（用 紫色 表示），直接过去即可。

由中序遍历的顺序， current 移动到 F 节点， F 节点为**叶子节点，所以需要线索化**，根据前面的描述可以将节点 F 的**左指针域线索化成其前驱节点** — A 节点（用 紫红色 表示）。

然后移动到 C 节点，进行 C 节点的线索化， prev \->rchild指针为空，所以对齐进行线索化，也就是节点 F 的后继节点为节点 C （下图中 粉色 表示）。

然后对节点 C 的**右子树进行线索化**，**可以看见此为空，并且中序遍历到此结束**，所以最后一个节点**也是没有后继节点**，所以，节点 C 的有指针域指向 NULL （下图中 蓝色 表示）。  
    
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 5]

图2.5 中序线索化的示意图5

感觉这个图比较乱，但是由于后面这部分其实就是前面三张图中的重复过程，所以弄明白那前面的三个过程，后面这个图片只要对应好颜色，还是比较明显能看出来的。

所以，前面线索化完成后的示意图可以表示为下图这样。  
    
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 6]

图2.6 中序线索化后的示意图

至此，中序线索化的过程已经说明完成了。

## 2.2、遍历过程说明 ##

说起遍历，那就是找到后继节点，一个一个遍历就是了，那么中序遍历也是，那么应该如何才能在线索化后找到对应的后继节点呢？  
  在上图2.6中，我们可以清楚地看到：

1、节点 A 的后继节点是节点 F ，但是节点 A 的 rTag 为 0 ，**右指针域指向的是其右子树**，那么怎么才能确定其后继接单就是节点 F 呢，我们在看看节点 F ，为节点 C 的**左子树**，所以节点 F 跟节点 A 的关系就是：

**节点** A **的右子树的最左下角的节点（最左的节点）**。

2、节点 G 的后继节点是节点 B ，而此时节点 G 的 rTag 为 1 ，是为**后继节点的线索**。包括节点 E 也是一致的。

## 2.3、线索化及遍历的代码实现 ##

综上所述，中序线索化的算法过程可以描述为：

在中序遍历的基础上，将原本遍历函数中输出的语句修改成线索化的代码即可。

具体线索化的部分代码为：

1、如果当前节点 current 左指针域为空，则需要将其做指针域加上前驱线索  
    2、如果当前节点的上一次访问的节点（ prev 指针）右子树为空，则需要为 prev 指针指向后继节点  
    3、使 prev 指针跟上当前节点指针

所以线索化代码代码可以这样编写。

/** * 功 能： * 线索化二叉树 -- 中序线索化 * 参 数： * root：要线索化的树的根节点 * ptmp：用于保留前驱节点 * 返回值： * 无 **/
    void in_thread(BiTNode *root, BiTNode **ptmp)
    { 
        if ((root == NULL)) goto END;
    
        in_thread(root->lchild, ptmp);
    
        if (root->lchild == NULL)
        { 
            root->lchild = *ptmp;
            root->lTag = 1;
        }
        if (*ptmp != NULL && (*ptmp)->rchild == NULL)
        { 
            (*ptmp)->rchild = root;
            (*ptmp)->rTag = 1;
        }
    
        (*ptmp) = root;
        in_thread(root->rchild, ptmp);
    END:
        return;
    }
    
    /** * 功 能： * 中序线索化二叉树的后继节点 * 参 数： * root：要查找的节点 * 返回值： * 成功：节点的后继节点 * 失败：NULL **/
    BiTNode *in_thread_nextNode(BiTNode *root)
    { 
        BiTNode *ret = NULL;
    
        if (root == NULL) goto END;
    
        if (root->rTag == 1) // 右标志位 1，可以直接得到后继节点
        { 
            ret = root->rchild;
        }
        else // 右标志位0，则要找到右子树最左下角的节点
        { 
            ret = root->rchild;
            while (ret->lTag == 0) // 查找最左下节点的位置
            { 
                ret = ret->lchild;
            }
        }
    
    END:
        return ret;
    }
    
    /** * 功 能： * 遍历线索化二叉树 - 中序正常顺序 * 参 数： * root：要遍历的线索二叉树的根节点 * 返回值： * 无 **/
    void in_thread_Older_next(BiTNode *root)
    { 
        if (root == NULL) goto END;
    
        while (root->lTag == 0) // 查找中序遍历的第一个节点，当lTag == 0的话
            root = root->lchild;
    
        printf("%c ", root->data); // 访问第一个节点
    
        while (root->rchild != NULL) // 当root存在后继，依次访问后继节点
        { 
            root = in_thread_nextNode(root);
            printf("%c ", root->data);
        }
    
    END:
        printf("\n");
        return;
    }

至于上面代码中为什么将 prev 指针作为**二级指针传入**，**是因为递归过程冲需要改变** prev **指针指向的地址中的值，想要修改一级指针的话就需要传入一级指针的地址，也就是二级指针**。如果还是想不明白的，请移步看看指针的内容。

## 2.4、线索化的测试 ##

### 2.4.1、测试案例工程结构 ###

为了兼容 **unix** 和 **windows** 系统以及方便进行工程管理，特意使用 **Cmake** 工具进行编译等，目前测试工程的目录结构如下所示。

biTree-threaded-in/
    ├── CMakeLists.txt
    ├── README.md
    ├── image
    │   └── image.jpg
    ├── main
    │   └── main.c
    ├── runtime
    └── src
        ├── biTree
        │   ├── biTree.c
        │   └── biTree.h
        └── thread
            ├── thread.c
            └── thread.h
    
    6 directories, 8 files

### 2.4.2、测试案例代码 ###

前面已经说明整体工程的结构，以及需要的文件，下面是测试底层功能函数的测试**demo**，详细代码如下。

#include "../src/thread/thread.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    //ABDH#K###E##CFI###G#J##
    
    int main(int argc, const char *argv[])
    { 
        int ret = 0;
        BiTNode *tree = NULL;
    
        printf("请按照先序输入二叉树(空节点用#表示)：");
        tree = fBiTree.create();
    
        if (tree != NULL)
        { 
            printf("\n二叉树创建成功！\n");
        }
        else
        { 
            printf("\n二叉树创建出现异常！\n");
            ret = -1;
            goto ERROR_END;
        }
    
        printf("中序遍历输出：");
        fBiTree.inOrder(tree);
        printf("\n\n");
    
        int leaf = 0;
        fBiTree.leafNum(tree, &leaf);
        printf("节点的个数 = %d 叶子节点的个数 = %d, 树的深度/高度 = %d\n\n", fBiTree.nodeNum(tree), leaf, fBiTree.depth(tree));
    
        BiTNode *copyTree = fBiTree.copy(tree);
    
        BiTNode *tmp = NULL;
        fthread.in(copyTree, &tmp);
    
        printf("\ncopy树中序线索化遍历输出：");
        fthread.inNextOlder(copyTree);
        printf("\n");
    
        tmp = NULL;
    
    ERROR_END:
        // 释放二叉树
        fBiTree.release(tree);
        /* copyTree已经在线索化的过程中被修改，此时按照原先的释放方式释放的话出现异常 */
        // fBiTree.release(copyTree);
    
        printf("system exit with return code %d\n", ret);
    
        return ret;
    }

### 2.4.3、测试效果图 ###

本次测试是在 **windows** 环境下进行，其他系统等详细说明在 **README.md** 中查看。  
  使用 **Cmake** 编译，经过**cmake**编译之后，配置**cmake**将**可执行文件放在固定目录runtime**下，可以使用在当前目录下使用指令 **`./../runtime/biTree.exe`来运行可执行程序，也可以进入到目录runtime**中，然后使用指令 **`./biTree.exe`** ，即可运行测试程序。

cd build
    cmake -G"MinGW Makefiles" .. # 注意 .. ,表示上级目录
    make
    ./../runtime/biTree.exe

实际测试的结果如下图所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 7]

图2.7 中序线索化后的示意图

# 三、先序线索化及其遍历 #

## 3.1、线索化过程说明 ##

开始先序线索化：在先序遍历的基础上进行线索化，  
  首先在中序线索化之前，先定义两个指针变量，用来辅助我们说明。

current :  为当前访问的节点  
     prev  :  为之前访问的最后一个节点，也就是 current 之前访问的节点。

对于先序遍历，从根节点开始遍历，所以此时，current 指针指向节点 A ， prev 指针为 NULL （下图 黑色 表示）。

1、在当前节点 A 下，其**左子树指针域不为空，所以不需要进行线索化操作**。并且此时 prev 指针指向 NULL ，所以也无需线索化。然后让 prev 跟上 current 指针（下图中用 粉色虚线 表示）。

然后继续遍历，将 current 指针移动到节点 B 上，此时 B 节点同样左子树不为空，也不需要进行线索化（下图中用 粉色 表示）。并且此时 prev 指针指向节点 A ，其右子树不为空，所以也无需线索化。然后让 prev 跟上 current 指针（下图中用 紫红色虚线 表示）。

2、然后继续遍历，将 current 指针移动到节点 D 上，此时节点 D 左子树为空，所以需要进行**线索化为前驱**，此时需要（下图中用 紫红色 表示，代码连接部分用 红色 表示）。

current->lTag = 1;   
    current->lchild = prev;

此时 prev 指针指向节点 B ，其右子树不为空，所以也无需线索化。  
  然后让 prev 跟上 current 指针（下图中用 紫色虚线 表示）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 8]

图3.1 先序线索化后的示意图1

3、然后继续遍历，按照之前递归遍历来说，此时应该去遍历访问节点 D 的**左子树**，但是因为之前我们已经将节点 D 的**左指针域线索化成前驱节点**了，那么在这个地方无法分辨，所以我们还需要告知遍历程序，此时这个**左指针域为节点本身的左子树还是前驱节点**。另外在线索化的时候同时修改了 lTag 域，用 lTag 来分辨是**左子树还是前驱节点**。所以，在线索化左子树之前需要加一个判断条件：  
    if(lTag == 1)   
  同样地、对于右子树同样也需要判断。  
    if(rTag == 1)

4、然后继续遍历，此时一判断， current->lTag == 1 , 说明**左指针域保存的是前驱节点**，应该去判断节点 D 的右子树了，然后去判断 current->rTag ，所以将 current 指针移动到节点 G 上，此时节点 G 的**左子树为空**，所以**需要进行线索化为前驱**，此时需要（下图中用 紫色 表示，代码连接部分用 红色 表示）。

current->lTag = 1;   
    current->lchild = prev;

此时 prev 指针指向节点 D ，其右子树不为空，所以也无需线索化。

然后让 prev 跟上 current 指针（下图中用 天蓝色虚线 表示）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 9]

图3.2 先序线索化后的示意图2

5、然后继续遍历，由递归遍历顺序，此时 current 应该去遍历节点 E ，但在递归返回的过程中到达节点 B 时候，判断节点B的右标志 current->rTag == 0 ，所以此时一判断，说明**右指针域保存的是右子树，需要继续便利线索化**，因为节点 E 为**叶子节点，左右指针与均为空**，所以经过条件判断，将节点 E 的**左指针域线索化为前驱**（下图中 天蓝色 表示，线索化用 红色 表示）。

然后判断 prev->rchild  不为空，所以说明需要将 prev 的**右指针域线索化为后继**，所以就有（下图中用 蓝色 表示线索化）。

prev->rchild = current;  
    prev->rTag = 1;

然后让 prev 跟上 current 指针（下图中用 草绿色虚线 表示）。

6、继续遍历， current 指针移动到节点 C ，此时节点 C 存在左子树，所以不予线索化。  
  然后因为此时 prev 指向节点 E ，其**右指针域为空，所以需要线索化为后继**，所以应该线索化（下图中 蓝色 表示）。  
  然后让 prev 跟上 current 指针（下图中用 橙色虚线 表示）。

7、继续遍历， current 指针移动到节点 F ，此时节点 F **左指针域为空，需要进行线索化**（线索化用下图 红色 表示）。  
  然后因为此时 prev 指向节点 C ，其**右指针域为空，所以需要线索化为后继**，所以应该线索化（线索化下图中 蓝色 表示）。  
  然后让 prev 跟上 current 指针（下图中用 绿色虚线 表示）。

8、节点 F **不存在左右子树**，所以递归遍历返回，此时 current 指针移动到节点 C （下图中 绿色 表示），此时节点 C 的 rTag 为 1 ，**右指针域为后继线索**，所以不需要再次操作。再次直接返回，遍历线索化过程结束。  
  此时， F 的**右指针域**没有进行操作，那么按照原来的定义，节点 F 的右指针域还是指向为 NULL 。所以整个过程可以用下图表示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 10]

图3.3 先序线索化后的示意图3

可以看出来，上述图中的线索化的表示与上面图中1.2中的表示一致（点我可以查看图1.2。。）。

## 3.2、遍历过程说明 ##

遍历，最主要的就是在知道的开头的时候怎么找到下一个该出现的节点。那么对于先序线索化，想要找到某个节点的后继节点还是非常容易的，主要可以：

1、如果节点的 lTag 为 0 ，那就说明是当前节点的左孩子，直接就是应该的后继节点  
    2、如果节点的 lTag 不为 0 ，那么其后继节点就是其有孩子。

所以、后序线索化的遍历还是比较简单的可以实现的。

## 3.3、线索化及遍历的代码实现 ##

综上所述，那么这个实现的代码就可以这样写了。

/** * 功 能： * 线索化二叉树 -- 先序线索化 * 参 数： * root：要线索化的树的根节点 * ptmp：用于保留前驱节点 * 返回值： * 无 **/
    void prev_thread(BiTNode *root, BiTNode **ptmp)
    { 
        if ((root == NULL)) goto END;
    
        if (root->lchild == NULL)
        { 
            root->lchild = *ptmp;
            root->lTag = 1;
        }
        if (*ptmp != NULL && (*ptmp)->rchild == NULL)
        { 
            (*ptmp)->rchild = root;
            (*ptmp)->rTag = 1;
        }
    
        (*ptmp) = root;
    
        // 如果不判断就会造成死循环,因为在程序一开始就对其左右孩子为NULL时就做了前驱后继的处理，同时改了标志位，所以此处可根据标志位判断是子树还是前驱后继
        if (root->lTag == 0)
            prev_thread(root->lchild, ptmp);
        //同上
        if (root->rTag == 0)
            prev_thread(root->rchild, ptmp);
    END:
        return;
    }
    
    /** * 功 能： * 遍历线索化二叉树 - 使用先序线索化的标识 * 参 数： * root：要遍历的线索二叉树的根节点 * 返回值： * 无 **/
    void prev_thread_Older_normal(BiTNode *root)
    { 
        if (root == NULL) goto END;
    
        BiTNode *p = root;
        while (p != NULL)
        { 
            while (p->lTag == 0)
            { 
                printf("%c ", p->data);
                p = p->lchild;
            }
            printf("%c ", p->data);
            p = p->rchild;
        }
    
    END:
        printf("\n");
        return;
    }

## 3.4、线索化的测试 ##

在前面我们已经详细的说明了**测试工程的结构、Cmake相关编译的指令**等，此处也不再赘述。详细结构可以 点我查看详细结构与指令。

这里面也包含测试案例的代码，只是将其中线索化和遍历部分的代码换成了先序线索化相关的代码，此处也不再赘述。详细结构可以 点我查看详细代码。

详细的先序线索化的测试效果如下图所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 11]

图3.4 先序线索化的测试效果

# 四、后序线索化及其遍历 #

## 4.1、线索化过程说明 ##

我们已经非常清楚了，**线索化是建立在遍历的基础上**。那么在后续遍历中，**首先遍历访问的是左子树和右子树，然后才会访问到根节点**，所以在线索化的时候也就没有先来后到的说法了，类似于退着走路就不需要管前面的路了。

那么根据线索化的特点，后续线索化的过程可以总结这样：

当前节点 current 的 **左指针域为空** 的时候，将 **左指针域线索化为其前驱**。  
  当前节点 current 的 **右指针域为空** 的时候，将 **右指针域线索化为其后继**。

所以，后序线索化后的效果图如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 12]

图4.1 后序线索化后的效果图

在前面我们已经详细的说明了**测试工程的结构、Cmake相关编译的指令**等，此处也不再赘述。详细结构可以 点我查看详细结构与指令。

## 4.2、遍历过程说明 ##

后续线索化，从上面的线索化过程中，以及本来的后序遍历的过程中，我们已经知道，**后序遍历需要知道其双亲结点**，所以我们在遍历某个节点的时候，需要在某个地方来记录一下其双亲节点，那么也在无形中增加了遍历的复杂度，所以在一定程度上也背离了我们线索化的初衷。并且在二叉链表的结构下，想要找到双亲节点很困难。这里为了演示测试效果我们采用一种方式采用后序来遍历线索化后的二叉树。其主要实现的思路就是：  
    1、先按照 **根节点->右孩子->左孩子** 的方式来遍历访问节点，并且将顺序记录一下  
    2、将刚才记录的顺序翻转即可

详细的思路可以查看博文：[数据结构（十三） – C语言版 – 树 - 二叉树的遍历（递归、非递归）。][_ C_ _ _ -]

## 4.3、线索化及遍历的代码实现 ##

综上所述，那么这个实现的代码就可以这样写了。

/** * 功 能： * 线索化二叉树 -- 后序线索化 * 参 数： * root：要线索化的树的根节点 * ptmp：用于保留前驱节点 * 返回值： * 无 **/
    void post_thread(BiTNode *root, BiTNode **ptmp)
    { 
        if ((root == NULL)) goto END;
    
        post_thread(root->lchild, ptmp);
        post_thread(root->rchild, ptmp);
    
        if (root->lchild == NULL)
        { 
            root->lchild = *ptmp;
            root->lTag = 1;
        }
        if (*ptmp != NULL && (*ptmp)->rchild == NULL)
        { 
            (*ptmp)->rchild = root;
            (*ptmp)->rTag = 1;
        }
        (*ptmp) = root;
    
    END:
        return;
    }
    
    /** * 功 能： * 后序线索化二叉树的前驱节点 * 参 数： * root：要查找的节点 * 返回值： * 成功：节点的后继节点 * 失败：NULL **/
    BiTNode *post_thread_prevNode(BiTNode *root)
    { 
        BiTNode *ret = NULL;
    
        if (root == NULL)
            goto END;
    
        // 如果 lTag 为 1, 就是本应该的前驱节点
        if (root->lTag == 1)
            ret = root->lchild;
        // 如果右孩子存在并且 rTag 不为 1, 那么 rchild 指针域就是前驱节点
        else if (root->rchild && root->rTag != 1)
            ret = root->rchild;
        // 如果 rTag 为 0, 并且同时 rTag 为0， 那么 rchild 指针域就是前驱节点
        // 这是因为在左右子树都存在的情况下，不会去进行线索化，但是其节点总归要前驱
        // 节点和后继节点的其中一个
        else if (root->lTag == 0 && root->rTag == 1)
            ret = root->lchild;
        else
            ret = root->lchild;
    
    END:
        return ret;
    }
    
    /** * 功 能： * 遍历线索化二叉树 - 使用前驱节点 * 参 数： * root：要遍历的线索二叉树的根节点 * 返回值： * 无 **/
    void post_thread_Older_byPrevNode(BiTNode *root)
    { 
        if (root == NULL)
            goto END;
    
        /** * 定义一个缓存区，用于保存 反向 后序遍历的顺序 * 其中这个地方比较推荐使用的栈，省去多余空间的浪费 */
        unsigned char buf[128] = { 0};
    	int i = 0, j = 0;
        while (root)
        { 
            buf[i] = root->data;
            root = post_thread_prevNode(root);
            i++;
        }
    
        for (j = i; j > 0; j--)
            printf("%c ", buf[j - 1]);
    
    END:
        printf("\n");
        return;
    }

## 4.4、线索化的测试 ##

在前面我们已经详细的说明了**测试工程的结构、Cmake相关编译的指令**等，此处也不再赘述。详细结构可以 点我查看详细结构与指令。

这里面也包含测试案例的代码，只是将其中线索化和遍历部分的代码换成了后序线索化相关的代码，此处也不再赘述。详细结构可以 点我查看详细代码。

详细的先序线索化的测试效果如下图所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 13]

图4.2 后序线索化后的测试效果图

# 五、总结 #

根据每一种已经提到过的线索化的方式，进行一下简单的总结，如下图中表格所示。  
  总结的内容为一家之言，不一定准确也不一定全正确，如果您有不同意的观点先请不要抨击，欢迎交流，嘻嘻 ≧◠◡◠≦✌  
    
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 14]

图5.1 线索化总结

好啦，废话不多说，总结写作不易，如果你喜欢这篇文章或者对你有用，请动动你发财的小手手帮忙点个赞，当然关注一波那就更好了，好啦，就到这儿了，么么哒(\* ￣3)(ε￣ \*)。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 15]  
上一篇：[数据结构（十六） – C语言版 – 树 - 二叉树的线索化及遍历 – 左指针域线索化、顺序表线索化、链表线索化 ][_ C_ _ _ - _ _]  
下一篇：[数据结构（十八） – C语言版 – 树 - 二叉树的线索化及遍历 – 线索化后的直接前驱、后继获取 ][_ C_ _ _ - _ _ _]

[_ C_ _ _ - _ _]: https://blog.csdn.net/zhemingbuhao/article/details/106275226
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200611173627379.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200611171304856.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[20200611171326935.png_pic_center]: https://img-blog.csdnimg.cn/20200611171326935.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_4_color_000000_t_10_pic_center]: https://img-blog.csdnimg.cn/2020061511021046.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_4,color_000000,t_10#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200615110855886.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200615111358669.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20200615111425360.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20200615111447602.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20200611171352913.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20200615151650525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20200616100303525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20200616100500640.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/2020061611475313.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20200616154738871.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20200616234801284.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[_ C_ _ _ -]: https://blog.csdn.net/zhemingbuhao/article/details/105644866
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 13]: https://img-blog.csdnimg.cn/20200618130054578.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 14]: https://img-blog.csdnimg.cn/20200618140339220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70_pic_center 15]: https://img-blog.csdnimg.cn/20200618140841791.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw==,size_16,color_FFFFFF,t_70#pic_center
[_ C_ _ _ - _ _ _]: https://blog.csdn.net/zhemingbuhao/article/details/106692759