【数据结构】（二叉树）线索构造二叉树

朱雀 2021-11-14 13:06 458阅读 0赞

## 中序线索二叉树的构造 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]  
**结构体**

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

**核心代码**

/线索二叉树的中序遍历 递归
    
    void inThread(TBTNode *p,TBTNode *&pre){
        
    	
    	if(p!=NULL){
        
    		inThread(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 preThread(TBTNode *p,TBTNode *&pre){
        
    	
    	if(p!=NULL){
        
    		
    				
    		if(p->lchild==NULL){
        
    			p->lchild=pre;
    			p->ltag=1;
    		}
    		
    		if(pre!=NULL&&pre->rchild==NULL){
        
    			pre->rchild=p;
    			pre->rtag=1;
    		}
    		pre=p;
    		if(p->ltag==0)  //进行判断防止构造线索绕环
    		inThread(p->lchild,pre);
    		if(p->rtag==0)
    		inThread(p->rchild,pre);	
    	}	
    }
     
     //线索二叉树的后序遍历 递归
    void postThread(TBTNode *p,TBTNode *&pre){
        
    	
    	if(p!=NULL){
        
    		inThread(p->lchild,pre);
    		inThread(p->rchild,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;	
    	}	
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]: /images/20211114/09450925e3464cf0a0879fe508abf200.png