数据结构考研笔记（十一）——线索二叉树

快来打我* 2022-12-15 14:11 115阅读 0赞

# 线索二叉树的概念 #

线索化  
若无左子树，则将左指针指向其前驱结点;  
若无右子树，则将右指针指向其后继结点。  
![在这里插入图片描述][20201017162404985.png_pic_center]  
![在这里插入图片描述][20201017162504358.png_pic_center]

typedef struct ThreadNode {
        
    	ElemType data;
    	struct ThreadNode *lchild,*rchild;
    	int ltag, rtag;
    }ThreadNode，*ThreadTree;

这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]

前驱结点
     若左指针为线索，则其指向结点为前驱结点
     若左指针为左孩子，则其左子树的最右侧结点为前驱结点
     后驱结点
     若右指针为线索，则其指向结点为后驱结点
     若右指针为右孩子，则其右子树的最左侧结点为后驱结点

中序线索二叉树线索化

void InThread(ThreadTree &p，ThreadTree &pre) {
        
    	if(p! == NULL){
        
    		inrhread (p -> lchild,pre);
    		if(p->lchild == NULL){
        
    			p->lchild = pre;
    			p->ltag = 1;
    		}
    		if(pre!=NULL && pre->rchild==NULL){
        
    			pre->rchild = p;
    			pre->rtag = 1;
    		}
    		pre = p;
    	
    		InThread(p->rchild, pre);
    	}
    }

void createInThread(ThreadTree T){
        
    	ThreadTree pre = NULL;
    	if(T!=NULL)[
    		InThread(T, pre);
    	 pre->rchild = NULL;
    	pre->rtag = l;

中序线索二叉树遍历  
找最左

ThreadNode *Firstnode (ThreadNode *p){
        
      while(p->ltag  o)
       p= p->lchild;
      return p;

找后继

ThreadNode *Nextnode (ThreadNode *p){
        
      if(p->rtag == o)
        return Firstnode (p->rchild) ;
      else
        return p->rchild;

循环的后继

void Inorder (ThreadNode *T){
        
      for(ThreadNode *p=Firstnode(T); p!=NULL;p=Nextnode (p))//空遍历结束
      visit(p);
    )

[20201017162404985.png_pic_center]: /images/20221123/3355db53cca94d3287afc1722f4184d6.png
[20201017162504358.png_pic_center]: /images/20221123/30b1cb712323482b8ac051fd1f07f3f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/8855221d3f784fe4bd15a876008a28ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/763c9c3ea9ee40debfcda361d85474e7.png