二叉树中序线索化详细图解

二叉树是数据结构中常见的一种，通过遍历二叉树我们可以得到我们需要的信息。在二叉树中，我们可以通过中序遍历的方式来获得有序的数据，但是对于庞大的二叉树，这种方式效率较低。因此，中序线索化就成了一种优化的方法。本文将从多个角度分析二叉树中序线索化，并提供详细的图解。

一、什么是中序线索化？

线索化是指将某些节点的指针利用起来，不仅指向其左右节点，同时还指向其前驱和后继节点的过程。而中序线索化则是在中序遍历的基础上进行的，通过这种方式我们可以在不遍历整棵二叉树的情况下，直接找到我们需要的数据。

二、中序线索化的方法：

中序线索化的方法可以使用递归或非递归的方式实现。在这里我们将介绍递归方式。

1. 定义一个节点结构体，包括左右指针、左右线索标志位和数据域。

typedef struct Node {

struct Node *lChild; // 左指针

struct Node *rChild; // 右指针

int lTag; // 左线索标志位，0为指向左孩子，1为指向前驱

int rTag; // 右线索标志位，0为指向右孩子，1为指向后继

int data; // 数据域

}Node;

2. 定义递归函数，并传入当前节点作为参数，将当前节点与前驱、后继节点相连。

void inOrderThread(Node *p, Node *&pre) {

if (p) {

inOrderThread(p->lChild, 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; // pre指向当前节点

inOrderThread(p->rChild, pre); // 递归右子树

}

}

三、中序线索化的图解：

下面我们通过一个图示进行中序线索化过程的详细介绍，图中的线代表指针。

1. 初始化一个二叉树

```

1

/ \

2 3

/ \ \

4 5 6

/ \

7 8

```

2. 遍历二叉树

通过中序遍历的方式遍历整个二叉树。

3. 线索化节点

通过中序遍历得到的节点序列为 7 4 8 2 5 1 3 6。

我们以节点4为例，可以发现其左右指针均不为空，因此将它与其前驱节点7相连，并给节点4的左线索标志位lTag赋值1，表示左指针指向前驱节点。

当处理到节点2时，可以发现其左子树为叶子节点4，因此将节点2与其前驱节点4相连，并给节点2的左线索标志位lTag赋值1。

同理，处理节点6时可以找到其后继节点为NULL，因此只将节点3与其前驱节点6相连，并给节点6的右线索标志位rTag赋值1。

4. 中序线索化之后的二叉树

```

7

▲

4 8

▲

2

▲

5 → 1 ↑ ← 3

▲

6

```

中序线索化之后，二叉树中保存了前驱和后继节点的信息，我们就可以在不遍历整棵树的情况下，通过前驱和后继节点找到我们需要的数据，大大提高了遍历效率。