二叉搜索树的插入与删除(详细解析)
题目:创建一个类,类中的数据成员时一棵二叉搜索树,对外提供的接口有添加结点和删除结点这两种方法。用户不关注二叉树的情况。要求我们给出这个类的结构以及实现类中的方法。
思路
添加结点:
添加结点其实很容易,我们只需要找到结点所行对应的位置就可以了,而且没有要求是平衡的二叉搜索树,因此每次添加结点都是在叶子结点上操作,不需要修改二叉搜索树整体的结构。要找出添加节点在二叉搜索树中的位置,可以用一个循环解决。判断插入结点与当前头结点的大小,如果大于头结点则继续搜索右子树,如果小于头结点则继续搜索左子树。直到搜索到叶子结点,此时进行插入结点操作。如果插入的结点等于二叉搜索树中当前某一结点的值,那么退出插入操作,并告知用户该结点已经存在。
删除结点:
删除结点比较麻烦,因为需要调整树的结构,这是因为删除结点并不一定发生在叶子结点。如果删除的是叶子结点,那么操作非常简单,只是做相应的删除就可以了,但如果删除的是非叶子结点,那么就需要调整二叉搜索树的结构。调整的策略有两个。假设当前需要删除的结点为A,
1.找出A结点左子树中的最大值结点B,将B调整到原先A的位置。
2.找出A结点右子树中的最小值结点C,将C调整到原先A的位置。
这其中涉及到许多复杂的指针操作,在下面的代码示例中并没有完成结点删除操作,等有空再补充研究一下。
代码示例
#include<iostream>
#include<stdlib.h>
#include<cassert>
using namespace std;
//二叉树结点
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
class BST
{
public:
BST(int value);//构造函数
~BST();//析构函数
void AddNode(int value);//添加结点
void DeleteNode(int value);//删除结点
BinaryTreeNode* CreateBinaryTreeNode(int value);//创建一个二叉树结点
void InOrderPrintTree();//中序遍历
void InOrderPrintTree(BinaryTreeNode* pRoot);//中序遍历
BinaryTreeNode* GetMaxNode(BinaryTreeNode* pNode);//求二叉搜索树最大值
BinaryTreeNode* GetMinNode(BinaryTreeNode* pNode);//求二叉搜索树最小值
private:
BinaryTreeNode* pRoot;
};
//构造函数
BST::BST(int value)
{
pRoot=CreateBinaryTreeNode(value);
}
//析构函数
BST::~BST()
{
delete pRoot;
pRoot=NULL;
}
//创建二叉树结点
BinaryTreeNode* BST::CreateBinaryTreeNode(int value)
{
BinaryTreeNode* pNode=new BinaryTreeNode();
pNode->m_nValue=value;
pNode->m_pLeft=NULL;
pNode->m_pRight=NULL;
return pNode;
}
//求二叉搜索树最大值
BinaryTreeNode* BST::GetMaxNode(BinaryTreeNode* pNode)
{
assert(pNode!=NULL); // 使用断言,保证传入的头结点不为空
//最大值在右子树上,因此一直遍历右子树,让pNode等于其右子树;如果只有一个结点则直接返回pNode
while(pNode->m_pRight!=NULL)
{
pNode=pNode->m_pRight;
}
return pNode;
}
//求二叉搜索树最小值
BinaryTreeNode* BST::GetMinNode(BinaryTreeNode* pNode)
{
assert(pNode!=NULL); // 使用断言
//最小值在左子树上,整体思路跟求最大值相同。
while(pNode->m_pLeft!=NULL)
{
pNode=pNode->m_pLeft;
}
return pNode;
}
//二叉搜索树添加结点
void BST::AddNode(int value)
{
BinaryTreeNode* pInsertNode=CreateBinaryTreeNode(value);//初始化需要创建的结点。
BinaryTreeNode* pNode=pRoot;
while(true)
{
//如果插入的值在二叉搜索树中已经存在,则不进行插入操作,跳出循环。
if(pNode->m_nValue==value)
{
cout<<"结点值已经存在"<<endl;
break;
}
//寻找结点插入的位置,如果待插入结点小于当前头结点,则继续搜索左子树
else if(pNode->m_nValue > value)
{
if(pNode->m_pLeft==NULL)//如果当前头结点是叶子结点了,那么直接将待插入结点插入到左子树中,然后跳出循环
{
pNode->m_pLeft=pInsertNode;
break;
}
else//否则继续遍历其左子树
pNode=pNode->m_pLeft;
}
//思路跟上述相同
else if(pNode->m_nValue < value)
{
if(pNode->m_pRight==NULL)
{
pNode->m_pRight=pInsertNode;
break;
}
pNode=pNode->m_pRight;
}
}
}
//未完成
void BST::DeleteNode(int value)
{
BinaryTreeNode* pNode=pRoot;
while(true)
{
if(pRoot->m_nValue==value)//如果是头结点
{
if(pRoot->m_pLeft!=NULL)
{
BinaryTreeNode* pLeftMaxNode=GetMaxNode(pRoot->m_pLeft);
}
else if(pRoot->m_pRight!=NULL)
{
}
else
{
delete pRoot;
pRoot=NULL;
}
}
if(pNode->m_nValue==value)
{
if(pNode->m_pLeft!=NULL)
{
}
else if(pNode->m_pRight!=NULL)
{
}
else
{
}
}
}
}
void BST::InOrderPrintTree(BinaryTreeNode* pRoot)//中序遍历
{
if(pRoot!=NULL)
{
//如果左子树不为空,则遍历左子树
if(pRoot->m_pLeft!=NULL)
InOrderPrintTree(pRoot->m_pLeft);
//遍历左子树的叶子结点
cout<<"value of this node is "<<pRoot->m_nValue<<endl;
//如果右子树不为空,遍历右子树
if(pRoot->m_pRight!=NULL)
InOrderPrintTree(pRoot->m_pRight);
}
else
{
cout<<"this node is null."<<endl;
}
}
//因为需要使用递归来进行中序遍历,所以还需要调用一个带参数的中序遍历函数
void BST::InOrderPrintTree()//中序遍历
{
InOrderPrintTree(pRoot);
}
void main()
{
BST* b=new BST(10);//初始化类的时候定义了二叉搜索树的头结点,这样省去了头结点为空的判断
b->AddNode(6);
b->AddNode(14);
b->InOrderPrintTree();
system("pause");
}
相关文章
- 下面小编来给大家演示几个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
- 伪造跨站请求介绍伪造跨站请求比较难以防范,而且危害巨大,攻击者可以通过这种方式恶作剧,发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
- 最近由于项目的需要,需要动态的添加和删除table中的tr,感觉用JS可以实现,但是在网上找了一下,单纯的自己写JS,感觉太麻烦,而且也不好维护。于是想到了最近学的jQuery。这篇文章给大家用实例介绍了jQuery动态添加与删除tr行的方法,有需要的朋友们可以参考借鉴。...2016-10-20
- 这篇文章主要介绍了mybatis-plus getOne和逻辑删除,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-08-26
- 这篇文章主要介绍了C# 复制与删除文件的实现方法的相关资料,希望通过本文能帮助到大家,让大家理解掌握这部分内容,需要的朋友可以参考下...2020-06-25
- 这篇文章主要为大家详细介绍了js实现上传文件添加和删除文件选择框 ,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2016-10-25
- 这篇文章主要介绍了C#删除UL LI中指定标签里文字的方法,涉及C#针对页面HTML元素进行正则匹配与替换的相关操作技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了MybatisPlus实现逻辑删除功能,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-12-25
- 这篇文章主要介绍了C++递归删除一个目录的实现方法,涉及到目录的操作及递归算法的应用,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了c# 用Dictionary实现日志数据批量插入的步骤,帮助大家更好的理解和使用c#中的Dictionary类,感兴趣的朋友可以了解下...2021-02-01
JQuery EasyUI学习教程之datagrid 添加、修改、删除操作
这篇文章主要介绍了JQuery EasyUI datagrid 添加、修改、删除操作的相关资料,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2016-07-25- 这篇文章主要介绍了jQuery中DOM节点的删除方法,文中介绍的很相信,内容包括empty()的基本用法、remove()的有参用法和无参用法、empty和remove区别、保留数据的删除操作detach()以及detach()和remove()区别,需要的朋友可以参考借鉴。...2017-01-26
- 本文实例讲述了MySQL查看、创建和删除索引的方法。分享给大家供大家参考。具体如下:1.索引作用在索引列上,除了上面提到的有序查找之外,数据库利用各种各样的快速定位技术,能够大大提高查询效率。特别是当数据量非常大,查询...2015-10-21
- 在本篇文章里小编给大家分享了关于C#删除Excel中的图片的实例代码内容,有兴趣的朋友们参考学习下。...2020-06-25