二叉树删除节点 c++

硅谷探秘者 2008 0 0

二叉树删除节点 c++

先看一个简单的树图


image.png

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

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

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

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


情况1

image.png

情况2

image.png

情况3

image.png

附代码:

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;
}


猜你喜欢
数据结构与算法 4036 基本操作c++classnode{public: intdata; node*left; node*right; node(); node(intdata); node(intdata
weblog 1443 因为需求需要,所以直接写一个数据结构 直接上代码: usingSystem; usingSystem.Collections.Generic; usingSystem.Linq; usingSystem.Text; usingSystem.Threading.Tasks; namespaceConsoleApplication2 { classProgram { staticvoidMai
weblog 3062 什么是的前驱和后继?某的前驱的val值小于该的val值并且值是最大的那个。某的后继的val值大于该的val值并且值是最小的那个。下面给出一个
official 135 请编写一个函数,使其可以某个链表中给定的(非末尾)。传入函数的唯一参数为要被。现有一个链表--head=[4,5,1,9],它可以表示为:示例1:输入:head=[4,5,1,9],n
数据结构与算法 7268 )java代码实现importjava.util.LinkedList;/***类*@author硅谷探秘者(jia)*/classNode{ publicintdata; publicNodele
official 203 。本题中,一棵高度平衡定义为:一个每个的左右两个子的高度差的绝对值不超过1。示例1案例输入:root=[3,9,20,null,null,15,7],输出:true示例2案例输入:r
数据结构与算法 1147 简单双向链表得增改查c++描述classnode{public:intdata;node*next;node*prev;};#include"node.h"classrelink
其他 2118 在.NET程序中,因为运行中的程序是受系统保护的,不能自己自身的,所以自的思路是:在关闭本程序之前启动新的进程打开另一个程序,调用这个程序来原程序。然后再完成外部进程的销毁。代码如下
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议
目录
祝愿神州十三飞行乘组平安归来