线索二叉树的构造与遍历C/C++代码实现

- 日理万妓 2023-02-16 09:28 7阅读 0赞

## 线索二叉树： ##

线索二叉树分成三种：对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树，包括先 序线索二叉树、 中序线索二叉树和后序线索二叉树。  
![在这里插入图片描述][20200609154247518.png]  
如果有左孩子则lchild指向左孩子，否则指向前驱，  
如果有右孩子则rchild指向右孩子，否则指向后继，  
即：  
LTag为0：lchild域指向左孩子，为1：指向遍历前驱。  
RTag为0：rchild域指向右孩子，为1：指向遍历后继。

## 带头结点的二叉树中序线索化： ##

在二叉树的线索链表上也添加一个头结点，并令其 lchild 域的指针指向二叉树的根结点，其rchild 域的指针指向中序遍历时访问的最后一个结点；同时，令二叉树中序序列中第一 个结点的 lchild域指针和最后一个结点 rchild 域的指针均指向头结点。这好比为二叉树建立了一 个双向线索链表，，既可从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

## 中序线索二叉树的遍历： ##

**寻找第一个遍历的结点**：最左下的结点。  
**寻找后继**：如果若RTag为1则右孩子指针域指示其后继，若RTag为0 则说明有右子树。根据中序遍历的规律可知，结点的后继应是遍历其右子树时访间的第一个结点，即右子树中最左下的结点。

## 代码如下： ##

#include<stdio.h>
    #include<iostream>
    
    typedef int TElemType;
    
    //线索二叉树的存储结构
    typedef struct BiThrNode
    {
        
    	TElemType data;
    	struct BiThrNode *lchild, *rchild;
    	int LTag, RTag;
    }BiThrNode,*BiThrTree;
    BiThrTree pre;		//全局变量，结点前驱
    
    //先序遍历建立二叉树
    void CreateBiThrTree(BiThrTree &T)
    {
        
    	char ch;
    	scanf("%c", &ch);
    	if (ch == '#')
    	{
        
    		T = NULL;
    	}
    	else
    	{
        
    		T=new BiThrNode;
    		T->data = ch;
    		CreateBiThrTree(T->lchild);
    		CreateBiThrTree(T->rchild);
    	}
    }
    
    //以p为根的子树中序线索化（被下面算法调用使用）
    void InThreading(BiThrTree p)
    {
        
    	if (p)
    	{
        
    		//左
    		InThreading(p->lchild);
    
    		//中
    		if (!p->lchild)				//左孩子为空，改左孩子指针域
    		{
        
    			p->LTag = 1;		
    			p->lchild = pre;		//指向前驱
    		}
    		else p->LTag = 0;
    		if (!pre->rchild)				//右孩子为空，改右孩子指针域
    		{
        
    			pre->RTag = 1;
    			pre->rchild = p;			//指向后继，根
    		}
    		else p->RTag = 0;
    		pre = p;
    
    		//右
    		InThreading(p->rchild);
    	}
    }
    //带头结点的二叉树中序线索化
    void InOrderThreading(BiThrTree &Thrt, BiThrTree T)
    {
        
    	Thrt = new BiThrNode;		//建立头结点
    	Thrt->LTag = 0;				//头结点有左孩子，若树非空，则其左孩子为树根 
    	Thrt->RTag = 1;				//其rchild域的指针指向中序遍历时访问的最后一个结点
    	Thrt->rchild = Thrt;		//初始化暂时指向自己
    
    	if (!T)
    	{
        
    		Thrt->lchild = Thrt;	//若树为空，则左指针也指向自己
    	}
    	else
    	{
        
    		Thrt->lchild = T;
    		pre = Thrt;
    
    		InThreading(T);			//线索化
    
    		pre->rchild = Thrt;		//最后一个结点右孩子指向头结点
    		pre->RTag = 1;
    		Thrt->rchild = pre;		//头结点其rchild域的指针指向中序遍历时访问的最后一个结点
    	}
    }
    
    //遍历中序线索二叉树
    void InOrderTraverse_Thr(BiThrTree Thrt)
    {
        
    	BiThrTree p = Thrt->lchild;
    	while (p != Thrt)
    	{
        
    		while (p->LTag == 0) p = p->lchild;
    		printf("%c", p->data);
    		while (p->RTag == 1 && p->rchild != Thrt)
    		{
        
    			p = p->rchild;
    			printf("%c", p->data);
    		}
    		p = p->rchild;			//有右子树，则后继为右子树中最左下的结点
    	}
    }
    
    int main()
    {
        
    	BiThrTree T;
    	BiThrTree Thrt;		//头指针
    
    	//创建
    	printf("请输入要建立的二叉树的先序序列，用#表示空树（单个字符表示结点）:");
    	CreateBiThrTree(T);
    
    	//线索化
    	InOrderThreading(Thrt, T);		
    
    	//遍历
    	printf("中序遍历序列:");
    	InOrderTraverse_Thr(Thrt);
    	printf("\n");
    	
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]

[20200609154247518.png]: https://img-blog.csdnimg.cn/20200609154247518.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200609155020726.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200609155509162.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70