二叉搜索树（二叉排序树，二叉查找树，二叉检索树）的查找，插入，删除

时间：2021-04-18 20:19:33
1，二叉搜索树定义？ （1）每个节点有一个唯一的key值，且所有结点互不相同； （2）左子树所有key值小于根的key值； （3）右子树所有key值大于根的key值； （4）左右子树都是二叉搜索树。 二叉搜索树（二叉排序树，二叉查找树，二叉检索树）的查找，插入，删除这就是一棵二叉搜索树。
 2，二叉搜索树的查找操作：（1）与根结点的key值比较，相等则 查找成功；（2）小于则查找左子树；（3）大于则查找右子树。3，二叉搜索树的插入操作：（1）先用查找操作找到要插入元素插入后的父亲节点；（2）和父亲比较大小后，决定作为右孩子还是左孩子插入；（3）若树空，则作为根节点插入。4，二叉搜索树的删除操作：（1）先用查找操作找到被删除元素的位置；（2）若被删除元素只有左孩子或者只有右孩子，则直接删除，把它的右孩子或左孩子加到它父亲上；如图所示：二叉搜索树（二叉排序树，二叉查找树，二叉检索树）的查找，插入，删除（3）若被删除元素两个孩子都有，选取“替身”取代被删结点。然后删除替身结点！如何选择替身？左子树中最大的结点（从被删点的左子树中找到最右边的那个点）或 右子树中最小的结点（从被删点的右子树中的找到最右边的点）都可以作为替换节点；找到后，和被删点交换数据，则问题变成了删除替换节点的问题了，而此时替换节点只有一个孩子，就回到了上述第二种情况了。如图所示：二叉搜索树（二叉排序树，二叉查找树，二叉检索树）的查找，插入，删除找到后，交换200和122，然后问题变成了删除叶子节点的问题了。下边是具体代码：
#include "stdafx.h"
#include <iostream>
using std::cin;
using std::cout;
using std::endl;

typedef struct Bstnode{
int data;
Bstnode *rchild;
Bstnode *lchild;
Bstnode()
{
rchild = NULL;
lchild = NULL;
}
}*Bitree;
//下边是先序遍历建树的代码
void CreateBST(Bitree &T)//先序遍历建树
{
int data;
cin >> data;
if (data == -1)
{
T = NULL;
}
else
{
T = new Bstnode;
T->data = data;//在前面要申请空间，T是一个指针；
CreateBST(T->lchild);
CreateBST(T->rchild);
}
}
//下边是在二叉搜索树中查找的代码
//f表示T的父亲节点，初始为空，p用来返回被查到的位置
//要是找到了，p为该元素在树中所在位置；
//要是没找到，p为插入该元素后的父亲节点所在位置；
bool SearchBST(Bitree T, int key, Bitree f, Bitree &p)
{
if (!T)
{
p = f;
return false;
}
else
{
if (T->data == key)
{
//cout << "已经存在了，不做插入！" << endl;
p = T;
return true;
}
else
if (T->data < key)
{
return SearchBST(T->rchild, key, T, p);
}
else
{
return SearchBST(T->lchild, key, T, p);
}
}
}
//下边是在二叉搜索树中插入元素的代码
void InsertToCreateBST(Bitree &T, int data)
{
if (!T)
{
T = new Bstnode;
T->data = data;
}
else
{
Bitree f = NULL;
Bitree p = NULL;
SearchBST(T, data, f, p);//找到该元素的父亲节点
Bitree s = new Bstnode;
s->data = data;
if(p->data < data)
{
p->rchild = s;
}
else
{
p->lchild = s;
}
}
}
//下边是在二叉搜索树中删除元素的代码
void DeleteBST(Bitree &T, int data)
{
Bitree f = NULL;
Bitree p = NULL;
if (!SearchBST(T, data, f, p))
{
cout << "删除的元素不在树中！" << endl;
}
else
{
if (!p->rchild)
{
Bitree q = p;
p = p->lchild;
delete q;
}
else
if (!p->lchild)
{
Bitree q = p;
p = p->rchild;
delete q;
}
else//这种情况是找替换点，这里我们找右子树中最小的数，找到后和被删节点替换数据删除即可
{
Bitree s = p;//指向右子树中最小节点的父亲节点，用来区分情况
Bitree q = p->rchild;
while (q->lchild)
{
s = q;
q = q->lchild;//q指向被删节点右子树中最小的节点
}
//找到替换点了，交换数据
p->data = q->data;
if (s != p)//表明被删点的右孩子有左子树
{
s->lchild = q->rchild;
}
else//表明被删点的右孩子没有左子树，右孩子本身就是被替换点
{
p->rchild = q->rchild;
}
delete q;
}
}
}
void PrintBST(Bitree T)
{
if (!T)
{
return;
}
else
{
cout << T->data <<' ';
PrintBST(T->lchild);
PrintBST(T->rchild);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
Bitree T = NULL;
//CreateBST(T);
//PrintBST(T);
//InsertToCreateBST(T, 4);
int a[11] = {400,450,122,99,110,105,250,200,230,300,500};
for (int i = 0; i < 11; i++)
{
InsertToCreateBST(T, a[i]);
}
PrintBST(T);
cout << endl;
cout << "删除一个顶点后为：" << endl;
DeleteBST(T, 122);
PrintBST(T);
cout << endl;
system("pause");
return 0;
}
运行结果显示为：二叉搜索树（二叉排序树，二叉查找树，二叉检索树）的查找，插入，删除5，二叉搜索树性质分析：主要用于内存中目录的编制，要求能够快速的查找，插入和删除。查找，插入和删除的时间代价都为O（h）,h为树的高度。但二叉搜索树的高度与插入顺序有关，例如：二叉搜索树（二叉排序树，二叉查找树，二叉检索树）的查找，插入，删除
这就引出了平衡二叉树的概念了。
标签：

相关文章