数据结构（特殊二叉树－线索二叉树）

一、线索二叉树

• 规律：在有n个节点的链式二叉树中必定存在 n+1 个空指针

• 链式二叉树中有很多的空指针，可以让这些空指针指向前一个节点\后一个节点，从而在有序遍历（中序遍历）二叉树时，不需要使用递归而通过循环即可以完成，并且效率要比递归快得多

• 一定是搜索二叉树

线索二叉树的结构

typedef struct TreeNode
{
    int data;   //  数据域
    struct TreeNode* left;
    bool lflag;     //  左子树是否是线索  为真时，左子树是线索 指向前一个节点
    struct TreeNode* right;
    bool rflag;     //  右子树是否是线索  为真时，右子树是线索 指向下一个节点
}TreeNode;

构建线索二叉树

• 首先需要有一颗搜索二叉树，然后通过中序遍历并生成线索，通过检查右子树是否为空来决定是否生成线索，让右子树指向下一个节点。

• 当构成线索二叉树后 ，可以通过循环遍历的方式有序遍历二叉树，不需要中序递归遍历也可以

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
typedef struct TreeNode
{
    int data;	//	数据域
    struct TreeNode* left;
    struct TreeNode* right;
    bool rflag;		//	右子树是否是线索  为真时，右子树是线索 指向下一个节点
}TreeNode;
 
TreeNode* create_tree_node(int data)
{
	TreeNode* node = malloc(sizeof(TreeNode));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	node->rflag = false;	//	默认非线索
	return node;
}
 
void _insert_tree(TreeNode** root,TreeNode* node)
{
	if(NULL == *root)
	{
		*root = node;
		return;
	}
 
	if(node->data < (*root)->data)
		_insert_tree(&((*root)->left),node);
	else
		_insert_tree(&((*root)->right),node);
}
 
//	添加还是按照搜索二叉树的规则
void insert_tree(TreeNode** root,int val)
{
	TreeNode* node = create_tree_node(val);
	_insert_tree(root,node);
}
 
void ldr_show(TreeNode* root)
{
	if(NULL == root) return;
	ldr_show(root->left);
	printf("%d ",root->data);
	ldr_show(root->right);
}
 
 
//	按中序遍历时，当前root节点的前一个节点
TreeNode* prev = NULL;
//	按照中序进行遍历 并创建线索
void create_clue(TreeNode* root)
{
	if(NULL == root) return;
 
	//	给左子树创建线索
	create_clue(root->left);
 
	//	检查prev是否要创建线索
	//	当prev指向树节点 且prev的右子树为空 可以创建线索 指向下一个节点root
	if(NULL != prev && NULL == prev->right)
	{
		prev->right = root;
		prev->rflag = true;
	}
	prev = root;
 
	//	给右子树创建线索
	create_clue(root->right);
}
 
//	按照线索进行循环遍历 无需递归
void clue_show(TreeNode* root)
{
	while(root)
	{
		//	让root走到最小值节点位置
		while(root->left) root = root->left;
 
		printf("%d ",root->data);
 
		//	root右子树是线索 指向下一个节点 直到root的右子树不是线索
		while(root->rflag)
		{
			root = root->right;
			printf("%d ",root->data);
		}
		root = root->right;
	}
}
 
int main(int argc,const char* argv[])
{
	TreeNode* root = NULL;
	for(int i=0; i<10; i++)
	{
		int num = rand()%100;
		insert_tree(&root,num);
		printf("%d ",num);
	}
	printf("\n");
	ldr_show(root);
	printf("\n");
 
	create_clue(root);
	clue_show(root);
}