《数据结构》—— 遍历线索二叉树

左手的ㄟ右手 2022-08-28 07:50 255阅读 0赞

### 遍历线索二叉树 ###

*   *  一、中序线索二叉树的遍历查找：DGBEAFC
     *  二、先序线索二叉树的遍历查找：ABDGECF
     *  三、后序线索二叉树的遍历查找：GDEBFCA
     *  四、算法：遍历中序线索二叉树

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_18_color_FFFFFF_t_70_g_se_x_16]  
以上图为参考：

*  中序遍历（左根右）：DGBEAFC；
 *  先序遍历（根左右）：ABDGECF；
 *  后序遍历（左右根）：GDEBFCA；

讨论如何在线索二叉树查找结点的前驱与后继？

## 一、中序线索二叉树的遍历查找：DGBEAFC ##

**① 查找p指针所指结点的前驱：**

*  若 p->Ltag==1，则p的左链指向其前驱；
 *  若 p->Ltag==0，说明有左子树，结点的前驱是遍历左子树时最后访问的一个结点（左子树中最右下结点）。

例如：左根右 --> ((左根右)根右) --> (((左根右)根右)根右)；  
我们对根结点A进行中序遍历，可以发现，它的左子树是B为根节点，按中序遍历结果是先返回 `D-G-B-E-A` 满足(左子树最后访问的一个结点)。

**② 查找p指针所指结点的后继：**

*  若 p->Rtag==1，则p的左链指向其前驱；
 *  若 p->Rtag==0，说明有右子树，结点的后继是遍历右子树时第一个访问的结点（右子树中最左下结点）。

例如：左根右 --> (左根(左根右))；  
我们对根结点A进行中序遍历，可以发现，它的右子树是C为根节点，第一个访问是F结点，满足中序遍历结果。  
![在这里插入图片描述][736ee60e4c844fed86129c941e102dc9.png]

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

## 二、先序线索二叉树的遍历查找：ABDGECF ##

**① 查找p指针所指结点的前驱：**

*  若 p->Ltag==1，则p的左链指向其前驱；
 *  若 p->Ltag==0，说明有左子树，若 \*p 结点为根结点，则找不到它的前驱，因为由于(根左右)，推不出它的前驱；若 \*p 结点为左孩子 || (右孩子&兄弟节点)为NULL，则 \*p 结点的前驱是它的父节点； 否则若 \*p 结点为右孩子，它的前驱是兄弟节点。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]  
**② 查找p指针所指结点的后继：**

*  若 p->Rtag==1，则p的左链指向其前驱；
 *  若 p->Rtag==0，说明有右子树，由遍历规则知则先序后继为左孩子，若p没有左孩子，则先序后继为右孩子。

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

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

## 三、后序线索二叉树的遍历查找：GDEBFCA ##

**① 查找p指针所指结点的前驱：**

*  若 p->Ltag==1，则p的左链指向其前驱；
 *  若 p->Ltag==0，若p有右孩子，则后序前驱为右孩子，若p没有右孩子，则后序前驱为左孩子。

**② 查找p指针所指结点的后继：**

*  若 p为根节点，则没有后继；若p为左孩子，它的后继结点是它的兄弟结点或者是p的父节点；若p为右孩子，它的后继是父节点。

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

## 四、算法：遍历中序线索二叉树 ##

#include<iostream>
    using namespace std;
    
    //二叉树的二叉线索类型存储表示
    typedef struct BiThrNode{
        
    	char data;
    	struct BiThrNode *lchild,*rchild;	//左右孩子指针
    	int LTag,RTag;
    }BiThrNode,*BiThrTree;
    
    BiThrNode *pre=new BiThrNode;  // 全局变量pre
    
    void CreateBiTree(BiThrTree &T){
        
    	//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
    	char ch;
    	cin >> ch;
    	if(ch=='#')  T=NULL;			//递归结束，建空树
    	else{
        
    		T=new BiThrNode;
    		T->data=ch;//生成根结点
    		CreateBiTree(T->lchild);	//递归创建左子树
    		CreateBiTree(T->rchild);	//递归创建右子树
    	}
    }
    
    // 结点P为根的子树中序线索化
    void InThreading(BiThrTree p){
        
    	//pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索
    	if(p){
        
    		InThreading(p->lchild);             			//左子树递归线索化
    		if(!p->lchild){
            //p的左孩子为空
    			p->LTag=1;   	//给p加上左线索
    			p->lchild=pre; 			//p的左孩子指针指向pre（前驱）
    		}
    		else
    			p->LTag=0;
    		if(!pre->rchild){
        		//pre的右孩子为空
    			pre->RTag=1;    		//给pre加上右线索
    			pre->rchild=p;      	//pre的右孩子指针指向p（后继）
    		}
    		else
    			pre->RTag=0;
    		pre=p;        			//保持pre指向p的前驱
    		InThreading(p->rchild);	//右子树递归线索化
        }
    }
    
    // 带头结点的中序线索化
    void InOrderThreading (BiThrTree &Thrt,BiThrTree T){
        
    	//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点
    	Thrt=new BiThrNode;           //建头结点
    	Thrt->LTag=0;  		   		 //头结点有左孩子，若树非空，则其左孩子为树根
    	Thrt->RTag=1;				//头结点的右孩子指针为右线索
    	Thrt->rchild=Thrt;            	//初始化时右指针指向自己
    	if(!T)  Thrt->lchild=Thrt;      //若树为空，则左指针也指向自己
    	else{
        
    	  Thrt->lchild=T;  pre=Thrt;   //头结点的左孩子指向根，pre初值指向头结点
    	  InThreading(T);             //调用算法，对以T为根的二叉树进行中序线索化
    	  pre->rchild=Thrt;          //算法，结束后，pre为最右结点，pre的右线索指向头结点
    	  pre->RTag=1;
    	  Thrt->rchild=pre;        //头结点的右线索指向pre
    	}
    }
    
    void InOrderTraverse_Thr(BiThrTree T){
        
        //T指向头结点，头结点的左链lchild指向根结点，可参见线索化算法5.8。
        //中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出
    	BiThrTree p;
    	p=T->lchild;              //p指向根结点
        while(p!=T){
        			  //空树或遍历结束时，p==T
    		while(p->LTag==0)	  //沿左孩子向下
    			p=p->lchild;	 //访问其左子树为空的结点
    		cout<<p->data;
    		while(p->RTag==1&&p->rchild!=T){
        
    			p=p->rchild;	//沿右线索访问后继结点
    			cout<<p->data;
    		}
    		p=p->rchild;
        }
    }
    
    int main(){
        
    	pre->RTag=1;
    	pre->rchild=NULL;
    	BiThrTree tree,Thrt;
    
    	cout<<"请输入建立二叉链表的序列，例如(ABD#G##E##CF###):\n";
    	CreateBiTree(tree);
    	InOrderThreading(Thrt,tree);
    	cout<<"中序遍历线索二叉树的结果为：\n";
    	InOrderTraverse_Thr(Thrt);
    	cout<<endl;
    }

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

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c305c81ab1914a2680187abd9bf0905f.png
[736ee60e4c844fed86129c941e102dc9.png]: /images/20220828/d67f3c30052344b784671d285084410a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/2689ac3953d642ec8e6f278d008041eb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/0c59574898a0453a8a0e6aec22928cd9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/41818dc2480a4c62ac53c38b7edaf3cb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/094f0a4dc5c34c118d35b6dfe4dff438.png
[4a9f277b0a344a69b9bc342e4a776911.png]: /images/20220828/442224efb2fb4c0cbb1cd2cf02d6d700.png