博客

删除叶子节点，要先确定要删除的叶子是其父节点的左节点还是右节点。

void Delete_leaf_recursion(BiTree &T){
	if(!T) return;
	BiTree p;
    if(T->lchild){
        p=T->lchild;
    	if(!p->lchild&&!p->rchild){
    		free(p);
    		T->lchild=NULL;
		}
	}
	if(T->rchild){
		p=T->rchild;
    	if(!p->lchild&&!p->rchild){
    		free(p);
    		T->rchild=NULL;
		}
	} 
    Delete_leaf(T->lchild);
    Delete_leaf(T->rchild);
} 

void Delete_leaf_nonrecursion(BiTree &T){
	Queue Q;
	InitQueue(Q);
	EnQueue(Q,T);
	BiTree p,q;
	while(!isEmptyQueue(Q)){
		DeQueue(Q,p);
		if(p->lchild){
			q=p->lchild;
			if(!q->lchild&&!q->rchild){
				free(q);
				p->lchild=NULL;
			}
			else EnQueue(Q,q);
		}	
		if(p->rchild){
			q=p->rchild;
			if(!q->lchild&&!q->rchild){
				free(q);
				p->rchild=NULL;
			}
			else EnQueue(Q,q);
		}	
	}
}