目录

⚽1.问题

🏐2.线索化

🏀 3.线索化带来的问题与解决

🥎4.完整代码

⚽1.问题

我们的二叉树学到现在，会产生两个问题：

• 在n个结点的二叉树中，必定有n+1个空链域（叶子结点的左右子树空间浪费了）
• 二叉树的遍历，无论是递归还是非递归算法，效率都不算高。

那我们能不能利用原本浪费掉的空间，来解决第二个问题呢？

倘若对下图二叉树进行中序遍历，可以得到1、3、6、8、10，我们可以知道3的前驱结点为1，后驱结点为6。但是，这种关系的建立是在完成遍历后得到的，那么，可不可以在建立二叉树的同时记录下前驱后继的关系，这样我们在寻找前驱后继结点时的效率将会大大提升！

我们的前辈们给出了答案：线索化 

🏐2.线索化

现将某结点的空指针域指向该结点的前驱后继，定义规则如下：

• 若结点的左子树为空，则该结点的左孩子指针指向其前驱结点
• 若结点的右子树为空，则该结点的右孩子指针指向其后继结点

这种指向前驱和后继的指针称为线索，将一棵普通的二叉树以某种次序遍历，并添加线索的过程称为线索化。

🏀 3.线索化带来的问题与解决

此时新的问题又产生了：我们如何区分一个lchild指针是指向左孩子还是前驱结点呢？

为了解决这个问题，我们需要添加标志位ltag和rtag,并定义以下规则

• ltag==0，指向左孩子；ltag==1，指向前驱结点
• rtag==0，指向右孩子；rtag==1，指向后继结点

🥎4.完整代码

中序线索化

void inOrderThreadTree(Node* node)
{
//如果当前结点为NULL 直接返回
if (node == NULL) {
return;
}
//先处理左子树
inOrderThreadTree(node->left_node);
if (node->left_node == NULL)
{
//设置前驱结点
node->left_type = 1;
node->left_node = pre;
}
//如果结点的右子节点为NULL 处理前驱的右指针
if (pre !=NULL && pre->right_node == NULL)
{
//设置后继
pre->right_node = node;
pre->right_type = 1;
}
//每处理一个节点 当前结点是下一个节点的前驱
pre = node;
//最后处理右子树
inOrderThreadTree(node->right_node);
}

遍历

void inOrderTraverse(Node* root)
{
//从根节点开始先找到最左边
if (root == NULL)
{
return;
}
Node* temp = root;
//先找到最左边结点 然后根据线索化直接向右遍历
while (temp != NULL && temp->left_type == 0)
{
temp = temp->left_node;
}
while (temp != NULL)
{
//输出
temp = temp->right_node;
}
}

完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct Thread {
struct Thread* left_node, *right_node;//左右指针
int data;//需要存放的数据
/*默认0代表左右孩子 1代表前驱或者后继*/
int left_type;//类型标志
int right_type;//类型标志
}Node;
 
Node* pre;//前驱结点的变量
Node* head;//头指针 指向某种遍历的第一个结点
 
void inOrderThreadTree(Node* node)
{
//如果当前结点为NULL 直接返回
if (node == NULL) {
return;
}
//先处理左子树
inOrderThreadTree(node->left_node);
if (node->left_node == NULL)
{
//设置前驱结点
node->left_type = 1;
node->left_node = pre;
}
//如果结点的右子节点为NULL 处理前驱的右指针
if (pre !=NULL && pre->right_node == NULL)
{
//设置后继
pre->right_node = node;
pre->right_type = 1;
}
//每处理一个节点 当前结点是下一个节点的前驱
pre = node;
//最后处理右子树
inOrderThreadTree(node->right_node);
}
 
void inOrderTraverse(Node* root)
{
//从根节点开始先找到最左边
if (root == NULL)
{
return;
}
Node* temp = root;
//先找到最左边结点 然后根据线索化直接向右遍历
while (temp != NULL && temp->left_type == 0)
{
temp = temp->left_node;
}
while (temp != NULL)
{
//输出
temp = temp->right_node;
}
 
}