二叉树删除节点 c++

先看一个简单的树图

删除节点是分以下几种情况：

    1.待删节点为叶子节点：此种情况下直接删除叶子节点即可

    2.待删节点只有左子树，或只有右子树，那么将左子树或右子树的根节点替换该节点即可

    3.待删节点既有左子树，又有右子树，那么就需要先找到该节点的后继节点，用后继节点替换该节点。

情况1

情况2

情况3

附代码：

head为树的根节点，详细情况请看下一个文章

void trytree::del(int data){//删除节点
	node * n=head;
	node * parent;
	while(n!=NULL){//寻找待删除节点
		if(data>n->data){//向右找
			parent=n;
			n=n->right;
		}else if(data<n->data){//向左找
			parent=n;
			n=n->left;
		}else{//相等即待除节点
			if(n->left!=NULL&&n->right==NULL){//左节点不为空右节点为空
				if(parent->left==n){
					parent->left=n->left;
					delete(n);
					return;
				}else{
					parent->right=n->left;
					delete(n);
					return;
				}
			}else if(n->left==NULL&&n->right!=NULL){//右节点不为空左节点为空
				if(parent->left==n){
					parent->left=n->right;
					delete(n);
					return;
				}else{
					parent->right=n->right;
					delete(n);
					return;
				}
			}else if(n->left==NULL&&n->right==NULL){//待删除的节点为叶子节点
				if(parent->left==n){
					parent->left=NULL;
					delete(n);
					return;
				}else{
					parent->right=NULL;
					delete(n);
					return;
				}
			}else{//左右孩子节点都不为空
				node * sub=n->right;
				if(sub->left==NULL){//sub为后继节点
					sub->left=n->left;
					if(parent->left==n){
						parent->left=sub;
						delete(n);
						return;
					}else{
						parent->right=sub;
						delete(n);
						return;
					}
				}else{
					node * p=sub;//后继节点的父节点
					while(sub->left!=NULL){//寻找后继节点
						p=sub;
						sub=sub->left;
					}
					p->left=NULL;
					if(parent->left==n){
						sub->left=n->left;
						sub->right=n->right;
						parent->left=sub;
						delete(n);
						return;
					}else{
						sub->left=n->left;
						sub->right=n->right;
						parent->right=sub;
						delete(n);
						return;
					}	
				}
			}
		}
	}
	cout<<"没有找到"<<endl;
	return;
}