【数据结构】（二叉树）二叉树删除结点值为x的子树

川长思鸟来 2021-11-13 14:46 399阅读 0赞

## 删除结点值为x的子树（包含结点本身） ##

**方法一递归:**

> **算法思想：** 递归的思想就是在前序遍历的过程中查找值为x的元素找到后将其释放

void Release(BiTree *&T){
        
    	if(!T)
    		return;
    	Release(T->lchild);
    	Release(T->rchild);
    	free(T);
    }
    
    void Delete_X(BiTree *&T,char x){
        
    	if(T==NULL)
    		return;
    
    	if(T->data==x){
               //若T的data为想要删除的元素 则进行删除
    			Release(T);   //删除包括根节点
    			T=NULL;		//因为free只是告诉系统这块内存我们不用了而不是物
    						//理上面的释放所以我们要手动赋值NULL;
    	}
    	if(T!=NULL){
        		 //这里再次进行一次判断当T不为空时继续向下执行
    		Delete_X(T->lchild, x);
    		Delete_X(T->rchild, x);
    	}
    }

**方法二层次遍历非递归：**

> **算法思想：** 因为层次遍历容易寻找跟结点我们在层次遍历中寻找要删除的元素x并递归删除它.层次遍历中我使用了二级指针因我在一级指针测试中本没有成功 这里如果有问题还请各位大佬指正

void Delete_X2(BiTree *&T,char x){
        			//层次遍历非递归删除
    	if(!T)
    		return ;
    
    	BiTree **r;
    	BiTree **que[MaxSize];      //数组模拟队列
    	int front=-1,rear=-1;	  //队列指针
    	que[++rear]=&T;			//根节点入队
    	
    	while(front<rear){
            //队列不为空循环继续
    		r=que[++front];
    		if((*r)->data==x){
        
    			Release(*r);
    			*r=NULL;
    		}else{
        
    			if((*r)->lchild){
        
    				que[++rear]=&(*r)->lchild;
    			}
    			if((*r)->rchild){
        
    				que[++rear]=&(*r)->rchild;
    			}
    		}
    	}
    }

***二级指针的解释***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]  
**测试数据：**

char pre[13]={
        '#','A','B','D','F','H','J','M','N','C','E','K','G'};
    	char in[13]={
        '#','D','B','J','H','M','N','F','A','E','K','C','G'};
    	
    	BiTree *p=PreInCreate(pre,in,1,12,1,12);
    	preorder(p);
    	cout<<endl;
    	Delete_X2(p,'B');
    	preorder(p);

**测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70]: /images/20211113/4006fe9334164903a9658b25cff00188.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190801111315916.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTM0NDc4,size_16,color_FFFFFF,t_70