目录

⚽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;
	}

}