线索二叉树的构建（数据结构学习笔记）

Bertha 。 2022-12-28 04:23 145阅读 0赞

### 文章目录 ###

*  构建规则
 *  存储结构
 *  类型定义
 *  中序搜索二叉树示意图
 *  构建中序线索二叉树线索
 *   *  构造过程
     *  算法设计
 *  中序遍历线索二叉树
 *   *  遍历规则
     *   *  寻找开始结点算法
     *  遍历过程
     *  遍历算法设计
     *  算法优点

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

> 对于具有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域。  
> 其中只有n-1个结点被有效指针所指向，即有n-1个非空指针域。所以**共有2n-(n-1) = n+1个空链域**。  
> 采用某种方法遍历二叉树的结果是一个结点的线性序列。  
> **修改空链域**改为**存放指向结点的前驱和后继结点的地址**。  
> 这样的指向该线性序列中的“前驱”和“后继”的指针，称作**线索（thread）**。  
> 创建线索的过程称为线索化。线索化的二叉树称为线索二叉树。  
> 显然**线索二叉树与采用的遍历方法相关**，有先序线索二叉树、中序线索二叉树和后序线索二叉树。  
> 线索二叉树的**目的是提高该遍历过程的效率**。

# 构建规则 #

*  每个结点设置**左标志、右标志** ：
 *  左标志 (ltag)：
 *  当 ltag = 0 , 意味着该结点**有左孩子结点**，因此**指向左孩子结点**。
 *  当 ltag = 1 , 意味着该结点**无左孩子结点**，因此**指向前趋结点，即线索**。
 *  右标志 (rtag):
 *  当 rtag = 0 , 意味着该结点**有右孩子结点**，因此**指向右孩子结点**。
 *  当 rtag = 1 , 意味着该结点**无右孩子结点**，因此**指向后继结点，即线索**。
 *  **为了算法的便捷，会再增加一个头结点**。

# 存储结构 #

如下图：

![在这里插入图片描述][20201214172041704.png]

# 类型定义 #

typedef struct node
    {
        
        ElemType data;
        int ltag,rtag;
        struct node *lchild;
        struct node *rchild;
    }TBTNode;

# 中序搜索二叉树示意图 #

如图所示：

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

# 构建中序线索二叉树线索 #

*  CreatThread(b)算法：对以二叉链存储的二叉树b进行中序线索化，并返回线索化后头结点的指针root。
 *  Thread§算法：对以\*p为根结点的二叉树子树的中序线索化。

> p总是指向当前线索化的结点。  
> pre作为全局变量，指向刚刚访问过的结点。  
> \*pre是 \*p的中序前驱结点，\*p是 \*pre的中序后继结点。

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

## 构造过程 ##

![在这里插入图片描述][20201214172155465.gif_pic_center]

## 算法设计 ##

TBTNode *pre;		   		//全局变量
    // b 为二叉树的根结点
    TBTNode *CreatThread(TBTNode *b)     //中序线索化二叉树
    {
           
        TBTNode *root;
        root=(TBTNode *)malloc(sizeof(TBTNode));  //创建头结点
        
        //初始化头结点的各项数据
        root->ltag=0; root->rtag=1;  root->rchild=b;
    
        if (b==NULL)        //空二叉树
            root->lchild=root;	//让头结点的左孩子指向自己
        else    //非空二叉树
        {
                
            root->lchild=b;
    	pre=root;             	//pre是*p的前驱结点，供加线索用
    	Thread(b);   		//中序遍历线索化二叉树
    
            //最后处理，加入指向头结点的线索
    	pre->rchild=root;    	
    	pre->rtag=1;
    	root->rchild=pre;    	//头结点右线索化
        }
        return root;
    } 
    
    //对二叉树b进行中序线索化
    void  Thread(TBTNode *&p)    		
    {
            
        if (p!=NULL)	    //保证所有结点全都线索化
         {
          
            //递归调用左子树线索化
            Thread(p->lchild);           		
            
            //前驱线索化
            if(p->lchild==NULL)          	
            {
             
                //建立当前结点的前驱线索
                p->lchild=pre; 
                p->ltag=1;  
            }	
            else  
                p->ltag=0;
    
            //后继线索化
            if(pre->rchild==NULL)	     	
            {
           
                //建立前驱结点的后继线索
                pre->rchild=p;
                pre->rtag=1;
            }	
            else  
                pre->rtag=0;
            
            pre=p;
            
            //递归调用右子树线索化
            Thread(p->rchild);  		
         }
    }

# 中序遍历线索二叉树 #

遍历某种次序的线索二叉树，就是从该次序下的开始结点出发，反复找到该结点在该次序下的后继结点，直到头结点。

## 遍历规则 ##

以中序线索二叉树为例，开始结点是根结点的最左下结点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]

### 寻找开始结点算法 ###

TBTNode *p=tb->lchild;
    //p指向根结点
    while (p->ltag==0)   
          p=p->lchild;

## 遍历过程 ##

![在这里插入图片描述][20201214172219428.gif_pic_center]

## 遍历算法设计 ##

void ThInOrder(TBTNode *tb)
    {
              
        //p指向根结点
        TBTNode *p=tb->lchild;
    			
        while (p!=tb)       //再次遍历到头结点时，结束遍历
        {
             
            //找开始结点
            while (p->ltag==0)   
                p=p->lchild;		
    
            //访问开始结点
    	printf("%c"，p->data);			
    	while (p->rtag==1 && p->rchild!=tb)
    	{
          
                p=p->rchild;
    	    printf("%c"，p->data);
    	}
    	p=p->rchild;
        }
    }

## 算法优点 ##

中序遍历算法既没有递归也没有用栈，空间效率得到提高。

*  学习数据结构教程（第五版）——李春葆教授主编
 *  图片来源于MOOC，数据结构——武汉大学——李春葆教授
 *  （如若侵权可联系QQ删除）

[20201214172041704.png]: /images/20221120/592aa46b4c854dbc85ac7e45cce1754d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/bf7c35c298d84578b5dd937dc6b2b27f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]: /images/20221120/fd947e5ec2c44dad800c8e9bf01c07ec.png
[20201214172155465.gif_pic_center]: /images/20221120/be74831facd74c7aad90dce581e65c59.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]: /images/20221120/41754d2ccdf44338bc44e8ca738c446b.png
[20201214172219428.gif_pic_center]: /images/20221120/1a5615d2bae34206b09d40276e81eb5d.png