当前位置：网站首页>二叉查找树的定义，查找，插入，删除
二叉查找树的定义，查找，插入，删除
2022-07-30 23:17:00 【疯疯癫癫才自由】
1.二叉查找树：
1）二叉查找树是一棵空树；
2）二叉查找树由根节点，左子树，右子树组成，且左子树所有结点的数据域全部不大于根结点的数据域，
右子树的所有结点的数据域大于根结点的数据域；
2. 二叉搜索树的操作：
1):Positoion Find(BinTree BST,ElemebtType x);从二叉搜索树BST中查找元素x，返回其所在结点的地址；
2):Position FindMin(BinTree BST);从二叉搜索树中查找最小元素并返回所在结点的地址；
3):Position FindMax(BinTree BST);从二叉搜索树中查找最大元素并返回所在结点地址；
4):BinTree Insert(BinTree BST,ElementType x);向二叉搜索树插入一个数；
5):BinTree Delete(BinTree BST,ElementType x);在二叉搜索树中删除值为x的结点
1)查找元素用递归实现：
/**
1.二叉查找树：
1）二叉查找树是一棵空树；
2）二叉查找树由根节点，左子树，右子树组成，且左子树所有结点的数据域全部不大于根结点的数据域，
右子树的所有结点的数据域大于根结点的数据域；
2. 二叉搜索树的操作：
1):Positoion Find(BinTree BST,ElemebtType x);从二叉搜索树BST中查找元素x，返回其所在结点的地址；
2):Position FindMin(BinTree BST);从二叉搜索树中查找最小元素并返回所在结点的地址；
3):Position FindMax(BinTree BST);从二叉搜索树中查找最大元素并返回所在结点地址；
4):BinTree Insert(BinTree BST,ElementType x);向二叉搜索树插入一个数；
5):BinTree Delete(BinTree BST,ElementType x);在二叉搜索树中删除值为x的结点
1)查找元素用递归实现：
*/
/**
#include <iostream>
using namespace std;
typedef int ElementType;
typedef struct TNode* BinTree;
struct TNode
{
ElementType data;
BinTree lchild;
BinTree rchild;
};
typedef BinTree Position;
Position Find(BinTree BST,ElementType x); //从二叉搜索树BST中查找元素x，返回其所在结点的地址；
Position FindMin(BinTree BST); //从二叉搜索树中查找最小元素并返回所在结点的地址；
Position FindMax(BinTree BST); //从二叉搜索树中查找最大元素并返回所在结点地址；
BinTree Insert(BinTree BST,ElementType x); //向二叉搜索树插入一个数；
BinTree NewNode(ElementType data); //新建一个结点
BinTree Delete(BinTree BST,ElementType x); //在二叉搜索树中删除值为x的结点
void PreTraver(BinTree BT); //前序遍历
int main()
{
int n;
cin >> n;
BinTree BST=NULL; //要初始化为空树
for(int i=0;i<n;++i)
{
int val;
cin >> val;
BST=Insert(BST,val);
if(BST!=NULL)
cout << "BST: " << BST->data << endl;
}
cout << "max: " << FindMax(BST)->data << endl;
cout << "min: " << FindMin(BST)->data << endl;
PreTraver(BST) ;
BST=Delete(BST,1);
cout << endl;
PreTraver(BST) ;
cout << endl;
BST=Delete(BST,100);
cout << endl;
PreTraver(BST) ;
return 0;
}
Position Find(BinTree BST,ElementType x) //从二叉搜索树BST中查找元素x，返回其所在结点的地址；
{
if(!BST)
return NULL;
if(BST->data==x)
return BST;
else if(x>BST->data)
return Find(BST->rchild,x);
else
return Find(BST->lchild,x);
}
Position FindMin(BinTree BST) //从二叉搜索树中查找最小元素并返回所在结点的地址；
{
if(!BST)
return NULL;
else if(!BST->lchild)
return BST;
else
return FindMin(BST->lchild);
}
Position FindMax(BinTree BST) //从二叉搜索树中查找最大元素并返回所在结点地址；
{
if(!BST)
return NULL;
else if(!BST->rchild)
return BST;
else
return FindMax(BST->rchild);
}
BinTree NewNode(ElementType data) //新建一个结点
{
BinTree BT=new TNode;
BT->data=data;
BT->lchild=BT->rchild=NULL;
return BT;
}
//BinTree Insert(BinTree BST,ElementType x) //向二叉搜索树插入一个数；代码与下面个插入函数一样
//{
// if(!BST)
// {
// BST=new TNode;
// BST->data=x;
// BST->lchild=BST->rchild=NULL;
// }
// else
// {
// if(x<BST->data)
// BST->lchild=Insert(BST->lchild,x);
// else if(x>BST->data)
// BST->rchild=Insert(BST->rchild,x);
// }
// return BST;
//}
BinTree Insert(BinTree BST,ElementType x) //向二叉搜索树插入一个数；
{
if(!BST)
BST = NewNode(x);
else
{
if(x<BST->data)
BST->lchild=Insert(BST->lchild,x);
else if(x>BST->data)
BST->rchild=Insert(BST->rchild,x);
}
return BST; //返回的还是数根结点
}
void PreTraver(BinTree BT) //前序遍历
{
if(BT)
{
printf("%d ",BT->data);
PreTraver(BT->lchild);
PreTraver(BT->rchild);
}
}
BinTree Delete(BinTree BST,ElementType x) //在二叉搜索树中删除值为x的结点
{
if(!BST)
cout << "要删除的结点未找到!\n";
else
{
if(x<BST->data)
BST->lchild=Delete(BST->lchild,x);
else if(x>BST->data)
BST->rchild=Delete(BST->rchild,x);
else
{
Position tem;
if(BST->lchild&&BST->rchild)
{
tem=FindMin(BST->rchild);
BST->data=tem->data;
BST->rchild=Delete(BST->rchild,tem->data);
}
else //当结点只有一个孩子结点或者没有孩子结点时，直接将孩子节点赋给父节点，也是满足
{ //二叉搜索树的特性（左孩子比根节点小，右孩子比根节点大，并且把父节点销毁
tem=BST;
if(!BST->lchild)
BST=BST->rchild;
else
BST=BST->lchild;
delete tem;
}
}
}
return BST; //同样返回的也是树根结点
}
*/
1.二叉查找树：
1）二叉查找树是一棵空树；
2）二叉查找树由根节点，左子树，右子树组成，且左子树所有结点的数据域全部不大于根结点的数据域，
右子树的所有结点的数据域大于根结点的数据域；
2. 二叉搜索树的操作：
1):Positoion Find(BinTree BST,ElemebtType x);从二叉搜索树BST中查找元素x，返回其所在结点的地址；
2):Position FindMin(BinTree BST);从二叉搜索树中查找最小元素并返回所在结点的地址；
3):Position FindMax(BinTree BST);从二叉搜索树中查找最大元素并返回所在结点地址；
4):BinTree Insert(BinTree BST,ElementType x);向二叉搜索树插入一个数；
5):BinTree Delete(BinTree BST,ElementType x);在二叉搜索树中删除值为x的结点
1)查找元素用非递归实现：
/**
1.二叉查找树：
1）二叉查找树是一棵空树；
2）二叉查找树由根节点，左子树，右子树组成，且左子树所有结点的数据域全部不大于根结点的数据域，
右子树的所有结点的数据域大于根结点的数据域；
2. 二叉搜索树的操作：
1):Positoion Find(BinTree BST,ElemebtType x);从二叉搜索树BST中查找元素x，返回其所在结点的地址；
2):Position FindMin(BinTree BST);从二叉搜索树中查找最小元素并返回所在结点的地址；
3):Position FindMax(BinTree BST);从二叉搜索树中查找最大元素并返回所在结点地址；
4):BinTree Insert(BinTree BST,ElementType x);向二叉搜索树插入一个数；
5):BinTree Delete(BinTree BST,ElementType x);在二叉搜索树中删除值为x的结点
1)查找元素用非递归实现：
*/
/**
#include <iostream>
using namespace std;
typedef int ElementType;
typedef struct TNode* BinTree;
struct TNode
{
ElementType data;
BinTree lchild;
BinTree rchild;
};
typedef BinTree Position;
Position Find(BinTree BST,ElementType x); //从二叉搜索树BST中查找元素x，返回其所在结点的地址；
Position FindMin(BinTree BST); //从二叉搜索树中查找最小元素并返回所在结点的地址；
Position FindMax(BinTree BST); //从二叉搜索树中查找最大元素并返回所在结点地址；
BinTree Insert(BinTree BST,ElementType x); //向二叉搜索树插入一个数；
BinTree NewNode(ElementType data); //新建一个结点
BinTree Delete(BinTree BST,ElementType x); //在二叉搜索树中删除值为x的结点
void PreTraver(BinTree BT); //前序遍历
int main()
{
int n;
cin >> n;
BinTree BST=NULL; //要初始化为空树
for(int i=0;i<n;++i)
{
int val;
cin >> val;
BST=Insert(BST,val);
if(BST!=NULL)
cout << "BST: " << BST->data << endl;
}
cout << "max: " << FindMax(BST)->data << endl;
cout << "min: " << FindMin(BST)->data << endl;
PreTraver(BST) ;
cout << endl;
BST=Delete(BST,30);
cout << endl;
PreTraver(BST) ;
cout << endl;
BST=Delete(BST,41);
cout << endl;
PreTraver(BST) ;
return 0;
}
Position Find(BinTree BST,ElementType x) //从二叉搜索树BST中查找元素x，返回其所在结点的地址；
{
while(BST)
{
if(BST->data > x)
BST=BST->lchild;
else if(BST->data < x)
BST=BST->rchild;
else
break;
}
return BST;
}
Position FindMin(BinTree BST) //从二叉搜索树中查找最小元素并返回所在结点的地址；
{
if(BST)
while(BST->lchild)
BST=BST->lchild;
return BST;
}
Position FindMax(BinTree BST) //从二叉搜索树中查找最大元素并返回所在结点地址；
{
if(BST)
while(BST->rchild)
BST=BST->rchild;
return BST;
}
BinTree NewNode(ElementType data) //新建一个结点
{
BinTree BT=new TNode;
BT->data=data;
BT->lchild=BT->rchild=NULL;
return BT;
}
BinTree Insert(BinTree BST,ElementType x) //向二叉搜索树插入一个数；
{
if(!BST)
BST = NewNode(x);
else
{
if(x<BST->data)
BST->lchild=Insert(BST->lchild,x);
else if(x>BST->data)
BST->rchild=Insert(BST->rchild,x);
}
return BST; //返回的还是树根结点
}
void PreTraver(BinTree BT) //前序遍历
{
if(BT)
{
printf("%d ",BT->data);
PreTraver(BT->lchild);
PreTraver(BT->rchild);
}
}
BinTree Delete(BinTree BST,ElementType x) //在二叉搜索树中删除值为x的结点
{
if(!BST)
cout << "要删除的结点未找到!\n";
else
{
if(x<BST->data)
BST->lchild=Delete(BST->lchild,x);
else if(x>BST->data)
BST->rchild=Delete(BST->rchild,x);
else
{
Position tem;
if(BST->lchild&&BST->rchild)
{
tem=FindMin(BST->rchild);
BST->data=tem->data;
BST->rchild=Delete(BST->rchild,tem->data);
}
else //当结点只有一个孩子结点或者没有孩子结点时，直接将孩子节点赋给父节点，也是满足
{ //二叉搜索树的特性（左孩子比根节点小，右孩子比根节点大，并且把父节点销毁
tem=BST;
if(!BST->lchild)
BST=BST->rchild;
else
BST=BST->lchild;
delete tem;
}
}
}
return BST; //同样返回的也是树根结点
}
*/1.二叉查找树：
1）二叉查找树是一棵空树；
2）二叉查找树由根节点，左子树，右子树组成，且左子树所有结点的数据域全部不大于根结点的数据域，
右子树的所有结点的数据域大于根结点的数据域；
2. 二叉搜索树的操作：
1):void Find(BinTree BST,ElementType x); //从二叉搜索树BST中查找元素x，并打印信息；
2):Position FindMin(BinTree BST);从二叉搜索树中查找最小元素并返回所在结点的地址；
3):Position FindMax(BinTree BST);从二叉搜索树中查找最大元素并返回所在结点地址；
4):void Insert(BinTree &BST,ElementType x); //向二叉搜索树插入一个数；
5):void Delete(BinTree &BST,ElementType x); //在二叉搜索树中删除值为x的结点；
6):BinTree Create(int *a,int n); //二叉查找树的建立；
1)算法笔记上的查找，插入，删除函数：
他的插入，删除函数的树根节点都是引用，这是因为函数本身定义所决定的，他们的返回类型都是void，而插入，删除是要将添加结点或者删除结点，相应的就要将结点赋给父节点的左右孩子，而函数参数在传递过程中是值传递，并不会改变原树的值，因此要加上引用
/**
1.二叉查找树：
1）二叉查找树是一棵空树；
2）二叉查找树由根节点，左子树，右子树组成，且左子树所有结点的数据域全部不大于根结点的数据域，
右子树的所有结点的数据域大于根结点的数据域；
2. 二叉搜索树的操作：
1):void Find(BinTree BST,ElementType x); //从二叉搜索树BST中查找元素x，并打印信息；
2):Position FindMin(BinTree BST);从二叉搜索树中查找最小元素并返回所在结点的地址；
3):Position FindMax(BinTree BST);从二叉搜索树中查找最大元素并返回所在结点地址；
4):void Insert(BinTree &BST,ElementType x); //向二叉搜索树插入一个数；
5):void Delete(BinTree &BST,ElementType x); //在二叉搜索树中删除值为x的结点；
6):BinTree Create(int *a,int n); //二叉查找树的建立；
1)算法笔记上的查找，插入，删除函数：
他的插入，删除函数的树根节点都是引用，这是因为函数本身定义所决定的，他们的返回类型都是void，
而插入，删除是要将添加结点或者删除结点，相应的就要将结点赋给父节点的左右孩子，而函数参数在传递过程
中是值传递，并不会改变原树的值，因此要加上引用
*/
#include <iostream>
using namespace std;
typedef int ElementType;
typedef struct TNode* BinTree;
struct TNode
{
ElementType data;
BinTree lchild;
BinTree rchild;
};
typedef BinTree Position;
void Find(BinTree BST,ElementType x); //从二叉搜索树BST中查找元素x，并打印信息；
Position FindMin(BinTree BST); //从二叉搜索树中查找最小元素并返回所在结点的地址；
Position FindMax(BinTree BST); //从二叉搜索树中查找最大元素并返回所在结点地址；
void Insert(BinTree &BST,ElementType x); //向二叉搜索树插入一个数；
BinTree NewNode(ElementType data); //新建一个结点
BinTree Create(int *a,int n); //二叉查找树的建立
void Delete(BinTree &BST,ElementType x); //在二叉搜索树中删除值为x的结点
void PreTraver(BinTree BT); //前序遍历
int main()
{
int n;
cin >> n;
int a[n];
for(int i=0;i<n;++i)
scanf("%d",&a[i]);
BinTree BST=Create(a,n);
cout << "max: " << FindMax(BST)->data << endl;
cout << "min: " << FindMin(BST)->data << endl;
PreTraver(BST) ;
cout << endl;
Delete(BST,1);
cout << endl;
PreTraver(BST) ;
cout << endl;
Delete(BST,41);
cout << endl;
PreTraver(BST) ;
return 0;
}
BinTree Create(int *a,int n) //二叉查找树的建立
{
BinTree BST=NULL;
for(int i=0;i<n;++i)
Insert(BST,a[i]);
return BST;
}
void Find(BinTree BST,ElementType x) //从二叉搜索树BST中查找元素x，返回其所在结点的地址；
{
while(BST)
{
if(BST->data > x)
BST=BST->lchild;
else if(BST->data < x)
BST=BST->rchild;
else
break;
}
if(BST==NULL)
printf("search failed\n");
else
printf("%d\n",BST->data);
}
Position FindMin(BinTree BST) //从二叉搜索树中查找最小元素并返回所在结点的地址；
{
if(BST)
while(BST->lchild)
BST=BST->lchild;
return BST;
}
Position FindMax(BinTree BST) //从二叉搜索树中查找最大元素并返回所在结点地址；
{
if(BST)
while(BST->rchild)
BST=BST->rchild;
return BST;
}
BinTree NewNode(ElementType data) //新建一个结点
{
BinTree BT=new TNode;
BT->data=data;
BT->lchild=BT->rchild=NULL;
return BT;
}
void Insert(BinTree &BST,ElementType x) //向二叉搜索树插入一个数；插入函数的根节点必须为引用，否则会插入失败
{
if(!BST) //如果BST为空，说明此节点为插入节点
{
BST = NewNode(x);
return ;
}
else
{
if(x<BST->data)
Insert(BST->lchild,x);
else if(x>BST->data)
Insert(BST->rchild,x);
else //查找成功，不需要插入
return;
}
}
void PreTraver(BinTree BT) //前序遍历
{
if(BT)
{
printf("%d ",BT->data);
PreTraver(BT->lchild);
PreTraver(BT->rchild);
}
}
void Delete(BinTree &BST,ElementType x) //在二叉搜索树中删除值为x的结点
{
if(!BST)
{
cout << "要删除的结点未找到!\n";
return;
}
else
{
if(x<BST->data)
Delete(BST->lchild,x);
else if(x>BST->data)
Delete(BST->rchild,x);
else
{
if(BST->lchild==NULL&&BST->rchild==NULL)
{
BST=NULL;
delete BST;
}
else if(BST->lchild!=NULL)
{
Position pre=FindMax(BST->lchild);
BST->data=pre->data;
Delete(BST->lchild,pre->data);
}
else
{
Position next=FindMin(BST->rchild);
BST->data=next->data;
Delete(BST->rchild,next->data);
}
}
}
}边栏推荐
猜你喜欢
递增三元组
IJCAI2022教程 | 口语语言理解:最新进展和新领域
Py's pdpbox: a detailed introduction to pdpbox, installation, and case application
Computer shortcut icon whitening solution
Reverse linked list - head insertion inversion method
【飞控开发基础教程10】疯壳·开源编队无人机-PID 基础原理
2sk2225 Substitute 3A/1500V Chinese Documentation【PDF Data Book】
Alibaba Cloud video on demand + project combat
# # yyds dry goods inventory interview will brush TOP101: to determine whether there is a part of the list
Go语学习笔记 - gorm使用 - 事务操作 Web框架Gin（十一）
随机推荐
$\text{ARC 145}$
2021GDCPC广东省大学生程序设计竞赛 B.Byfibonacci
Py's pdpbox: a detailed introduction to pdpbox, installation, and case application
DFS question list and template summary
Debezium报错系列之二十：task failed to create new topic.Ensure that the task is authorized to create topics
微软商店出现【0x800706D9】解决方法
2021GDCPC Guangdong University Student Programming Competition B.Byfibonacci
win10重建索引
StoneDB 为何敢称业界唯一开源的 MySQL 原生 HTAP 数据库？
Golang go-redis cluster模式下不断创建新连接，效率下降问题解决
【LeetCode】64. 最小路径和 - Go 语言题解
阿里云视频点播+项目实战
2sk2225 Substitute 3A/1500V Chinese Documentation【PDF Data Book】
Data cleaning - ingest using es
PS Basic Learning (1)
IJCAI2022 Tutorial | Spoken Language Comprehension: Recent Advances and New Fields
IDEA usage skills
uniapp folding box secondary loop
ZZULIOJ:1119: sequence order
通过对抗性知识蒸馏压缩深度图神经网络