二叉查找树的插入,删除,查找
二叉查找树是满足以下条件的二叉树：
1、左子树上的所有节点值均小于根节点值，
2、右子树上的所有节点值均不小于根节点值，
3、左右子树也满足上述两个条件。
二叉查找树的插入过程如下：
1.若当前的二叉查找树为空，则插入的元素为根节点，
2.若插入的元素值小于根节点值，则将元素插入到左子树中，
3.若插入的元素值不小于根节点值，则将元素插入到右子树中。
二叉查找树的删除，分三种情况进行处理：
1.p为叶子节点，直接删除该节点，再修改其父节点的指针（注意分是根节点和不是根节点），如图a。
2.p为单支节点（即只有左子树或右子树）。让p的子树与p的父亲节点相连，删除p即可；（注意分是根节点和不是根节点）；如图b。
3.p的左子树和右子树均不空。找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点。如图c。
插入节点的代码：
struct node
{
int val;
pnode lchild;
pnode rchild;
};
pnode BT = NULL;
//递归方法插入节点
pnode insert(pnode root, int x)
{
pnode p = (pnode)malloc(LEN);
p->val = x;
p->lchild = NULL;
p->rchild = NULL;
if(root == NULL){
root = p;
}
else if(x < root->val){
root->lchild = insert(root->lchild, x);
}
else{
root->rchild = insert(root->rchild, x);
}
return root;
}
//非递归方法插入节点
void insert_BST(pnode q, int x)
{
pnode p = (pnode)malloc(LEN);
p->val = x;
p->lchild = NULL;
p->rchild = NULL;
if(q == NULL){
BT = p;
return ;
}
while(q->lchild != p && q->rchild != p){
if(x < q->val){
if(q->lchild){
q = q->lchild;
}
else{
q->lchild = p;
}
}
else{
if(q->rchild){
q = q->rchild;
}
else{
q->rchild = p;
}
}
}
return;
}
查找节点的代码：
pnode search_BST(pnode p, int x)
{
bool solve = false;
while(p && !solve){
if(x == p->val){
solve = true;
}
else if(x < p->val){
p = p->lchild;
}
else{
p = p->rchild;
}
}
if(p == NULL){
cout << "没有找到" << x << endl;
}
return p;
}
删除节点的代码
bool delete_BST(pnode p, int x) //返回一个标志，表示是否找到被删元素
{
bool find = false;
pnode q;
p = BT;
while(p && !find){ //寻找被删元素
if(x == p->val){ //找到被删元素
find = true;
}
else if(x < p->val){ //沿左子树找
q = p;
p = p->lchild;
}
else{ //沿右子树找
q = p;
p = p->rchild;
}
}
if(p == NULL){ //没找到
cout << "没有找到" << x << endl;
}
if(p->lchild == NULL && p->rchild == NULL){ //p为叶子节点
if(p == BT){ //p为根节点
BT = NULL;
}
else if(q->lchild == p){
q->lchild = NULL;
}
else{
q->rchild = NULL;
}
free(p); //释放节点p
}
else if(p->lchild == NULL || p->rchild == NULL){ //p为单支子树
if(p == BT){ //p为根节点
if(p->lchild == NULL){
BT = p->rchild;
}
else{
BT = p->lchild;
}
}
else{
if(q->lchild == p && p->lchild){ //p是q的左子树且p有左子树
q->lchild = p->lchild; //将p的左子树链接到q的左指针上
}
else if(q->lchild == p && p->rchild){
q->lchild = p->rchild;
}
else if(q->rchild == p && p->lchild){
q->rchild = p->lchild;
}
else{
q->rchild = p->rchild;
}
}
free(p);
}
else{ //p的左右子树均不为空
pnode t = p;
pnode s = p->lchild; //从p的左子节点开始
while(s->rchild){ //找到p的前驱，即p左子树中值最大的节点
t = s;
s = s->rchild;
}
p->val = s->val; //把节点s的值赋给p
if(t == p){
p->lchild = s->lchild;
}
else{
t->rchild = s->lchild;
}
free(s);
}
return find;
}
相关文章
- 下面小编来给大家演示几个php操作zip文件的实例，我们可以读取zip包中指定文件与删除zip包中指定文件，下面来给大这介绍一下。 从zip压缩文件中提取文件 代...2016-11-25
- 复制代码 代码如下: <td> <a href="/member/life/edit_ppt/<?php echo $v->id;?>" class="btn">编辑</a> <a href="javascript:;" onclick="if(confirm('您确定删除这条记录？')){location.href='/member/life/d...2014-06-07
- 这篇文章主要介绍了mybatis-plus 处理大数据插入太慢的解决，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-12-18
- 最近由于项目的需要，需要动态的添加和删除table中的tr，感觉用JS可以实现，但是在网上找了一下，单纯的自己写JS，感觉太麻烦，而且也不好维护。于是想到了最近学的jQuery。这篇文章给大家用实例介绍了jQuery动态添加与删除tr行的方法，有需要的朋友们可以参考借鉴。...2016-10-20
- 伪造跨站请求介绍伪造跨站请求比较难以防范，而且危害巨大，攻击者可以通过这种方式恶作剧，发spam信息，删除数据等等。...2013-10-01
- 在debian环境下，彻底解决mysql无法插入和显示中文的问题Linux下Mysql插入中文显示乱码解决方案mysql -uroot -p 回车输入密码进入mysql查看状态如下：默认的是客户端和服务器都用了latin1，所以会乱码。解决方案:mysql>use...2013-10-04
Centos中彻底删除Mysql（rpm、yum安装的情况）
我用的centos6，mysql让我整出了各种问题，我想重装一个全新的mysql，yum remove mysql-server mysql之后再install并不能得到一个干净的mysql，原来的/etc/my.cnf依然没变，datadir里面的数据已没有任何变化，手动删除/etc/my.cn...2015-03-15- 当unique列在一个UNIQUE键上插入包含重复值的记录时，我们可以控制MySQL如何处理这种情况：使用IGNORE关键字或者ON DUPLICATE KEY UPDATE子句跳过INSERT、中断操作或者更新旧记录为新值。mysql> create table menus(id t...2015-11-08
- 数据库中的数据删除会分为两种：物理删除 和 逻辑删除，接下来通过本文给大家介绍MyBatis-Plus的物理删除和逻辑删除使用场景分析，感兴趣的朋友一起看看吧...2021-09-25
- 这篇文章主要为大家详细介绍了js实现上传文件添加和删除文件选择框 ,具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2016-10-25
- 这篇文章主要介绍了mybatis-plus getOne和逻辑删除,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2020-08-26
- 这篇文章主要介绍了C# 复制与删除文件的实现方法的相关资料,希望通过本文能帮助到大家，让大家理解掌握这部分内容，需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#删除UL LI中指定标签里文字的方法,涉及C#针对页面HTML元素进行正则匹配与替换的相关操作技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了MybatisPlus实现逻辑删除功能，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-12-25
- 二分查找是一种在已经过排序的数组中搜索指定元素用的算法,这里我们就来看一下Ruby实现二分搜索(二分查找)算法的简单示例:...2020-06-30
- 这篇文章主要介绍了C++递归删除一个目录的实现方法,涉及到目录的操作及递归算法的应用,需要的朋友可以参考下...2020-04-25
JQuery EasyUI学习教程之datagrid 添加、修改、删除操作
这篇文章主要介绍了JQuery EasyUI datagrid 添加、修改、删除操作的相关资料,非常不错，具有参考借鉴价值，需要的朋友可以参考下...2016-07-25- 这篇文章主要介绍了jQuery实现查找最近父节点的方法,涉及jQuery针对元素节点操作的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2016-06-24
- 这篇文章主要介绍了c# 用Dictionary实现日志数据批量插入的步骤，帮助大家更好的理解和使用c#中的Dictionary类，感兴趣的朋友可以了解下...2021-02-01
- 这篇文章主要介绍了jQuery中DOM节点的删除方法,文中介绍的很相信，内容包括empty()的基本用法、remove()的有参用法和无参用法、empty和remove区别、保留数据的删除操作detach()以及detach()和remove()区别，需要的朋友可以参考借鉴。...2017-01-26