【数据结构——遍历二叉树和线索二叉树】

àì夳堔傛蜴生んèń 2022-12-18 02:55 211阅读 0赞

# 【数据结构——遍历二叉树和线索二叉树】 #

### 目录 ###

*  【数据结构——遍历二叉树和线索二叉树】
 *  一、遍历二叉树
 *   *  （一）遍历的三种规则
     *   *  1、先序遍历
         *  2、中序遍历
         *  3、后序遍历
     *  （二）遍历的相关算法
     *   *  1、先序遍历建立二叉链表
         *  2、统计二叉树中叶子结点的个数
         *  3、求二叉树的深度
         *  4、复制二叉树
         *  5、统计二叉树中结点的个数
 *  二、线索二叉树
 *   *   *  1、相关概念
         *  2、中序线索化算法
         *  3、遍历中序线索二叉树

# 一、遍历二叉树 #

**遍历的定义——指按某条搜索路线遍访每个结点且不重复（又称周游）**

## （一）遍历的三种规则 ##

### 1、先序遍历 ###

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

> 若二叉树为空，则：空操作  
> 否则：  
> 访问根结点（D）;  
> 先序遍历左子树（L）;  
> 先序遍历右子树（R）;

void PreOrderTraverse(BiTree T)
    {
        
    	if (T)  //非空二叉树
    	{
        
    		printf("%d", T->data);  //访问根结点
    		PreOrderTraverse(T->lchild); //递归遍历左子树
    		PreOrderTraverse(T->rchild);  //递归遍历右子树
    	}
    }

### 2、中序遍历 ###

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

> 若二叉树为空，则：空操作  
> 否则：
> 
> > 中序遍历左子树（L）;  
> > 访问根结点（D）;  
> > 中序遍历右子树（R）;

void InOrderTraverse(BiTree T)
    {
        
    	if (T)  //非空二叉树
    	{
        
    		InOrderTraverse(T->lchild); //递归遍历左子树
    		printf("%d", T->data);  //访问根结点
    		InOrderTraverse(T->rchild);  //递归遍历右子树
    	}
    }

### 3、后序遍历 ###

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

> 若二叉树为空，则：空操作  
> 否则：
> 
> > 后序遍历左子树（L）;  
> > 后序遍历右子树（R）;  
> > 访问根结点（D）;

void PostOrderTraverse(BiTree T)
    {
        
    	if (T)  //非空二叉树
    	{
        
    		PostOrderTraverse(T->lchild); //递归遍历左子树
    		PostOrderTraverse(T->rchild);  //递归遍历右子树
    		printf("%d", T->data);  //访问根结点
    	}
    }

## （二）遍历的相关算法 ##

### 1、先序遍历建立二叉链表 ###

**扩充先序序列：先序遍历二叉树时，如果当前要访问的结点不空，就记下这个结点值，如果空，就以“\#”记下来，所得到的遍序序列。**

**例如：下图的先序遍历序列是：ABCDEFG**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]

**扩充先序序列为：ABC\#\#DE\#G\#\#F\#\#\#**

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

//先序遍历建立二叉链表
    void CreateBiTree(BiTree& T)
    {
        
    	scanf_s("%c", ch);
    	if (ch == "#")
    		T = NULL;//递归结束，建立空树
    	else
    	{
        
    		T = new BiTNode;
    		T->data = ch;//生成根结点
    		CreateBiTree(T->lchild);//递归建立左子树
    		CreateBiTree(T->rchild);//递归建立右子树
    	}
    }

### 2、统计二叉树中叶子结点的个数 ###

> 算法基本思想：
> 
> > 1、若二叉树为空，则叶子结点个数为零  
> > 2、若二叉树中左儿子和右儿子均为空，则叶子结点的个数为1  
> > 3、否则，整个二叉树的叶子结点个数等于其左子树中叶子结点个数和其右子树的叶子结点个数之和

//统计二叉树中叶子结点的个数
    int CountLeaf(BiTree T)
    {
        
    	if (!T)
    		return 0;//空树返回0
    	if (!T->lchild && !T->rchild)
    		return 1;//结点无左右孩子返回1
    	else
    	{
        
    		m = CountLeaf(T->lchild);//递归统计左子树的叶子结点
    		n = CountLeaf(T->rchild);//递归统计右子树的叶子结点
    		return m + n;
    	}
    }

### 3、求二叉树的深度 ###

> 算法基本思想：
> 
> > 1、若二叉树为空树，则深度为0  
> > 2、否则，二叉树的深度为左右子树的深度的最大值+1

/*求二叉树的深度*/
    int Depth(BiTree T)
    {
        
    	if (!T) return 0;//空树
    	else  //二叉树的深度应该为左右子树的最大深度+1
    	{
        
    		m = Depth(T->lchild);
    		n = Depth(T->rchild);
    		if (m > n)
    			return (m + 1);
    		else
    			return (n + 1);
    	}
    }

### 4、复制二叉树 ###

> 算法基本思想：
> 
> > 1、若二叉树为空，则复制的二叉树也为空  
> > 2、若二叉树不为空，则首先复制根结点，然后分别复制二叉树根结点的左子树和右子树

/*复制二叉树*/
    void Copy(BiTree T, BiTree& NewT)
    {
        
    	if (!T)
    	{
        
    		NewT = NULL;//空树，递归结束
    		return;
    	}
    	else
    	{
        
    		NewT = new BiTNode;
    		NewT->data = T->data;//复制根结点
    		Copy(T->lchild, NewT->lchild);//递归复制左子树
    		Copy(T->rchild, NewT->rchild);//递归复制右子树
    	}
    }

### 5、统计二叉树中结点的个数 ###

> 算法基本思想：
> 
> > 1、如果是空树，则结点个数为0  
> > 2、结点个数为左子树结点个数加上右子树结点个数再加一

/*统计二叉树中结点的个数*/
    int NodeCount(BiTree T)
    {
        
    	if (!T)
    		return 0;
    	else
    		return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
    }

# 二、线索二叉树 #

### 1、相关概念 ###

**线索：指向前驱或者后继结点的指针称为线索**  
**线索二叉树：加上线索的二叉链表表示的二叉树叫做线索二叉树**  
**线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫做线索化  
——在有n个结点的二叉链表中必定有n+1个空链域  
——在线索二叉树的结点中增加两个标志域  
例如：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]  
**先序、中序、后续线索二叉树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]  
***（1）先序线索化***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 8]  
***（2）中序线索化***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 9]

***（3）后序线索化***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 10]  
*注意：增加一个头结点*

*  头结点（如下图中的中序遍历）：
 *  LTag=0,lchild指向根结点
 *  RTag=1,rchild指向遍历序列中最后一个结点
 *  遍历序列中的第一个结点的lchild域、最后一个结点的rchild域都指向头结点

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

### 2、中序线索化算法 ###

**二叉树的二叉线索存储表示：**

/*二叉树的二叉线索存储表示*/
    typedef struct BiThrNode
    {
        
    	TElemType data;//数据域
    	struct BiThrNode* lchild, * rchild;//左右孩子指针
    	int LTag, RTag;//左右标志
    }BiThrNode,*BiThrTree;

**中序线索化是在已建立好的二叉链表（每个结点5个域）上，按中序遍历的方法在访问根结点时建立线索。**

**算法一：以结点p为根的子树中序线索化**  
*算法步骤*

> 算法中有一全局变量：pre,在主调程序中初值为空，在整个线索化算法中pre始终指向当前结点p的前驱
> 
> > 1、如果p非空，左子树递归线索化  
> > 2、如果p的左子树为空，则给p加上左线索，将其LTag置为1，让p的左孩子指针指向pre（前驱）；否则将p的LTag置为0  
> > 3、如果pre的右孩子为空，则给pre加上右线索，将其RTag置为1.让pre的右孩子指针指向p（后继）；否则将pre的RTag置为0  
> > 4、将pre指向刚访问过的结点P,即pre = p  
> > 5、右子树递归线索化

*算法描述*

/*以结点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 (!p->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
    	}
    }

### 3、遍历中序线索二叉树 ###

> 在中序线索二叉树中找p指针所指结点前驱的方法：
> 
> > 1、若R->LTag = 1;则 lchild 域直接指向其前驱  
> > 2、若R->LTag = 0;则结点的前驱应是其左子树的右链尾（RTag = 1）的结点
> 
> 在中序线索二叉树中找p指针所指结点后继的方法：
> 
> > 1、若R->RTag = 1;则 rchild 域直接指向其后继  
> > 2、若R->RTag = 0;则结点的后继应是其右子树的左链尾（LTag = 1）的结点

/*遍历中序线索二叉树*/
    void InOrderTraverse_Thr(BiThrTree T)
    {
        //T指向头结点，头结点的左链lchild指向根结点
     //中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出
    	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;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/b8de031c04254ab89a5f8f3f4446f596.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221122/ca661bed8dad4d11b33cb982b54bd840.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221122/38f3a4b238a346138c2c5e2ffe71636c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221122/d077018f1cfe44909e1309952000fb89.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221122/a00f6075fead4b14aed61bc5cc36ec44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221122/2db721bb282d4260a5a3878b21f019dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221122/6f048f5e1ec248708e303d778cfa1c3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221122/e4f7ac212d5f4976882b8a54785f40e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221122/bfc62b2c23a747819cef430a9b31bcf1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221122/8b77633e4d2c42cbaee70697617955da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221122/4e584689a5384afca63a822c54ddd9f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221122/08d44484d7d04a538ba202737eb3713c.png