线索二叉树（图解+完整代码）-Toy模板网

这篇具有很好参考价值的文章主要介绍了线索二叉树（图解+完整代码）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

完整代码文章来源地址https://www.toymoban.com/news/detail-436198.html

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

}

到了这里，关于线索二叉树（图解+完整代码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！