C语言数据结构之线索二叉树

我不是女神ヾ 2022-12-02 01:09 214阅读 0赞

## C语言数据结构之线索二叉树 ##

tips：前些天学习了二叉树的相关操作，今天来总结一下线索二叉树的操作。

--------------------

**线索二叉树：对二叉树以某种次序遍历得到序列中的前驱和后继，其中指向结点前驱和后继的指针称为线索，再加上线索的二叉树称之为线索二叉树。**

**线索化：对二叉树以某种次序遍历使其变成线索二叉树的过程称为线索化**  
注意：线索化是要基于一棵二叉树上线索化，所以我们要先建树！

--------------------

**1、线索二叉树的存储结构**

<table> 
 <thead> 
  <tr> 
   <th>lchild</th> 
   <th>ltag</th> 
   <th>data</th> 
   <th>rtag</th> 
   <th>rchild</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

其中，标志域的含义：

**ltag**

*  0：lchild域指示结点的左孩子；
 *  1：lchild域指示结点的前驱；

**rtag**

*  0：rchild域指示结点的右孩子；
 *  1：rchild域指示结点的后继；

对应的线索二叉树结构体：

typedef struct node
    {
        
    	char c;//结点的数据
    	struct node *left;//左指针
    	struct node *right;//右指针
    	int ltag, rtag;//标志域，为0表示有左右孩子，为1表示指向其前趋或后继
    
    }Node, *pNode;

相比普通的二叉树，线索二叉树多了标志域，标志域的值及其含义如上。

--------------------

**2、中序线索二叉树的构建**

思路：

*  按照中序遍历序列，将树结点指针中序线索化；
 *  若结点有左右孩子，则标志域为0，指针域指向左右孩子；
 *  若结点无左右孩子，则标志域为1，指针指向其中序序列的前驱和后继；

这里可以用一个辅助指针pre，来记录递归时正在访问的结点的前驱结点。  
在中序遍历时，若当前正在访问的结点左指针为空，就将其左指针指向pre；  
若pre的右指针为空，则将其右指针指向当前结点；

**注意，这里我们要在子函数修改在主函数声明的tree和pre的值，所以这里我们在子函数中传入tree和pre的地址！**

具体实现：

//二叉树的中序线索化,参数是当前结点及前趋结点
    //二叉树的中序线索化,参数是根结点及前趋结点
    void InThread(pNode *tree,pNode *pre)
    {
        
    	if (*tree != NULL)
    	{
        
    		InThread((&(*tree)->left),pre);//中序遍历先找到最左侧的子树
    		if ((*tree)->left == NULL)//左子树为空，则前趋指向前一个结点（左指针线索化）
    		{
        
    			(*tree)->left = *pre;
    			(*tree)->ltag = 1;//修改左标志域的值
    		}
    		if (*pre != NULL && (*pre)->right == NULL)//右子树为空，则由pre将右指针线索化(这里是返回上一层，现在的根结点就变成了上一层的还未线索化的右指针的后继)（右指针线索化）
    		{
        
    			(*pre)->right = *tree;
    			(*pre)->rtag = 1;//修改右标志域的值
    		}
    		*pre = (*tree);//pre跟着tree走，记录tree的中序前趋结点
    
    		InThread(&((*tree)->right),pre);//中序遍历先找到最右侧的子树
    	}
    }
    
    //创建中序线索化二叉树
    void CreateInThread(pNode *tree)
    {
        
    	pNode pre = NULL;
    
    	if (tree != NULL)
    	{
        
    		//将最右侧的结点右指针手动线索化
    		InThread(tree, &pre);
    		pre->right = NULL;
    		pre->rtag = 1;
    	}
    }

--------------------

**3、中序线索二叉树的遍历**

思路：

*  先寻找中序线索二叉树中序序列第一个结点（最左侧的结点）；
 *  寻找中序线索二叉树结点的后继结点；
 *  循环遍历中序线索二叉树；

具体实现：

//中序线索二叉树的遍历
    pNode Firstnode(pNode tree)//找中序线索化开始的结点（最左侧的结点）
    {
        
    	pNode pcur = tree;
    	while (pcur->ltag == 0)
    		pcur = pcur->left;
    	return pcur;
    }
    pNode Nextnode(pNode p)//找中序线索化条件下，p结点的后继结点
    {
        
    	if (p->rtag == 0)//标记位为0，指向孩子（右子树最左侧的结点）
    			return Firstnode(p->right);
    	else
    		return p->right;//标记位为1，指向后继结点
    }
    void Inorder(pNode tree)//遍历中序线索二叉树
    {
        
    	for (pNode p = Firstnode(tree); p != NULL; p = Nextnode(p))
    		printf("%c", p->c);
    }

--------------------

至此，中序线索二叉树的创建以及遍历已经完成。我们在main()函数中测试一下：

int main()
    {
        
    	//准备建树的元素,0号下标不存元素
    	char c[N] = {
         ' ','A','B','C','D','E','F','G','H','I','J' };
    
    	pNode p[N];//树的结点
    	pNode tree;//根结点
    	InitBiTree(p, c);//初始化树
    	
    	CreateBitree(p);//层次建树
    
    	tree = p[1];//1号结点作为根结点
    
    	printf("二叉树的中序遍历：");
    	midorder(tree);
    	printf("\n");
    	
    	//将二叉树中序线索化
    	CreateInThread(&tree);//创建中序线索二叉树
    	printf("---------------------------------------\n");
    	
    	printf("tree->c=%c\n", tree->c);
    	
    	printf("---------------------------------------\n");
    
    	printf("中序线索二叉树遍历：");
    	Inorder(tree);//遍历中序线索二叉树
    	printf("\n");
    	
    	return 0;
    }

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]  
**可以看到二叉树的中序遍历结果与中序线索二叉树遍历结果相同！**

--------------------

tips：人生就像赛跑，不在乎你是否第一个到达终点，而在乎你有没有跑完全程。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b386d0328ae34b379beca70eccdaa3ec.png