C语言线索二叉树

逃离我推掉我的手 2022-12-17 07:08 178阅读 0赞

**线索二叉树**，我个人的理解是：在创建一个二叉树的基础上，把二叉树中的只有一个孩子或没有孩子的结点中的指向空的指针进行填充，以便于二叉树的遍历。  
**首先**，还是先创建一个二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
还是以上个代码中所表示的样板为例（懒）。画不怎么好看，请见谅！  
**然后**，便是对已经建立的二叉树进行线索化。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]  
上图是对头结点Thrt的初始化，结点pre为全局变量。  
另外需要记住：  
（1）LTag为0时指向该结点的左孩子，为1时指向该结点的前驱；  
（2）RTag为0时指向该结点的右孩子，为1时指向该结点的后继。  
对二叉树的线索化：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 2]  
前：直接前驱；后：直接后继。（图不好看请见谅！）  
**最后**，利用线索遍历二叉树。

代码运行的结果展示图为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 3]  
第一行为输入的（二叉树）数据。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct BiThrNode
    { 
    	char data;//结点的数据域 
    	struct BiThrNode *lchild,*rchild;//左右孩子指针
    	int LTag,RTag;//左右标志 
    }BiThrNode,*BiThrTree;
    
    void CreateTree(BiThrTree &T)//创建二叉树，这里是先序遍历的顺序建立的二叉链表 递归形式 
    { 
    	char ch;
    	scanf("%c",&ch);//输入链表数据 
    	if(ch == '#')//如果出现输入的是#,终止递归。终止递归条件
    		T = NULL;
    	else
    	{ 
    		T = (BiThrNode*)malloc(sizeof(BiThrNode));//申请一个根结点 
    		T->data = ch;//对根结点进行赋值 
    		CreateTree(T->lchild);//递归创建左子树 
    		CreateTree(T->rchild);//递归创建右子树
    	}
    }
    
    BiThrTree pre;//定义全局变量pre 
    
    void InThreading(BiThrTree p)//对二叉树p进行线索化 
    { 
    	if(p)//递归终止条件 
    	{ 
    		InThreading(p->lchild);//左子树递归线索化 
    		if(p->lchild == NULL)//p的左孩子为空 
    		{ 
    			p->LTag = 1;//给p加上左线索 
    			p->lchild = pre;//p的左孩子指针指向pre(前驱) 
    		}
    		else
    			p->LTag = 0;
    		if(pre->rchild == NULL)//pre的右孩子为空 
    		{ 
    			pre->RTag = 1;//给pre加上右线索 
    			pre->rchild = p;//pre的右孩子指针指向p(后继) 
    		}
    		else
    			p->RTag = 0;
    		pre = p;//保持pre指向p的前驱 
    		InThreading(p->rchild);//右子树的递归线索化 
    	}
    } 
    
    void InOrerThreading(BiThrTree &Thrt,BiThrTree T)//创建一个头结点Thrt，并使其连入p的线索化中 
    { 
    	Thrt = (BiThrNode*)malloc(sizeof(BiThrNode));//创建一个头结点 
    	Thrt->LTag = 0;
    	Thrt->RTag = 1;
    	Thrt->rchild = Thrt;//初始化头结点 ，头结点的右指针指向自己 
    	if(T == NULL)//如果二叉树为空，则头结点的左指针指向自己 
    		Thrt->lchild = Thrt; 
    	else
    	{ 
    		Thrt->lchild = T;//头结点的左孩子指向根 
    		pre = Thrt;//pre初值指向头结点
    		InThreading(T);//调用上面的线索化函数 
    		pre->rchild = Thrt;//pre为最右结点，pre的右线索指向头结点
    		pre->RTag = 1;
    		Thrt->rchild = pre;//头结点的右线索指向pre 
    	}
    }
    
    void InOrderTraverse_Thr(BiThrTree Thrt)//遍历并打印线索二叉树 
    { 
    	BiThrTree p;//创建一个指针 
    	p = Thrt->lchild;//p指向根结点 
    	while(p != Thrt)//空树或遍历结束时，p==T; 
    	{ 
    		while(p->LTag == 0)//沿左孩子向下 
    			p = p->lchild;
    		printf("%d %c %d\n",p->LTag,p->data,p->RTag);//打印p结点，及左右标志 
    		while(p->RTag == 1&&p->rchild != Thrt)//沿右线索访问后继结点 
    		{ 
    			p = p->rchild;
    			printf("%d %c %d\n",p->LTag,p->data,p->RTag);
    		}
    		p = p->rchild;//转向p的右子树 
    	}
    }
    
    int main()
    { 
    	BiThrTree Thrt,T;//定义个头结点，和二叉树T 
    	CreateTree(T);//创建二叉树T 
    	InOrerThreading(Thrt,T);//线索化二叉树T 
    	InOrderTraverse_Thr(Thrt);//打印线索二叉树 
    	return 0;
    }

（完）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/23a370120c0646308fd5e6a1a86c2bcf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/2529fc18d04b4730b8418ce1abeed5fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/1293b97962104452997885092fdd405f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/64b9ec6cfc804b189f7a930d77fd40af.png