目录
二叉排序树的定义
二叉排序树的查找
二叉排序树的插入
二叉排序树的定义
二叉排序树的定义
二叉排序树(Binary Sort Tree, BST),也称二叉查找树。
二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二叉树:
1) 若左子树非空,则左子树上所有结点关键字均小于根结点的关键字值;
2) 若右子树非空,则右子树上所有结点关键字均大于根结点的关键字值;
3) 左、右子树本身也分别是一棵二叉排序树。
由定义可知,二叉排序树是一个递归的数据结构,可以方便的使用递归算法对二叉排序树进行各种运算。
根据二叉树的定义,可得左子树结点值 < 根结点值 < 右子树结点值。
所以,对二叉排序树进行中序遍历,可以得到一个递增的有序序列。
二叉排序结点结构:
typedef struct BiTNode
{
int data;
struct BiTNode *left, *right;
}BiTNode,*Bitree;
二叉排序树的查找
二叉排序树的查找是从根结点开始的,沿某个分支逐层向下进行比较的过程。
其查找过程描述如下:若二叉排序树非空,则将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的关键字值大于给定关键字值时,在根结点的左子树中查找;否则在根结点的右子树中查找。
递归查找:
Bitree SearchBST(Bitree root, int key){
if(root->data == key){
return root;
}else if(key< root->data){
return SearchBST(root->left, key);
}else{
return SearchBST(root->right, key);
}
}
非递归查找文章来源:https://www.toymoban.com/news/detail-470864.html
//查找的非递归算法
Bitree SearchBST(Bitree root, int key){
Bitree p = root;
while(p!=NULL && p->data!=key){
if(key< p->data)
p = p->left;
else
p = p->right;
}
return p;
}
二叉排序树的插入
//插入的递归算法
Bitree Insert(Bitree root, int x) {
if (root == NULL) {
root = (Bitree)malloc(sizeof(BiTNode));
root->data;
root->left = NULL;
root->right = NULL;
return root;
}
if (x < root->data) {
root->left = Insert(root->left, x);
}
if (x > root->data) {
root->right = Insert(root->right, x);
}
return root;
}
//插入的非递归算法
void Inser_Node(Bitree &T, int key)
{
Bitree parent = NULL;
Bitree p = T;
Bitree s = (Bitree)malloc(sizeof(BiTNode));
s->data = key;
s->left = NULL;
s->right = NULL;
if (T== NULL)
{
T = s;
return;
}
while (p != NULL)
{
parent = p;
if (p->data > key)//在左孩子继续查找
{
p = p->left;
}
if (p->data < key)
{
p = p->right;
}
}
if (parent->data > key)
{
parent->left = s;
}
else
{
parent->right = s;
}
}
根据书上代码,将查找和插入整合:文章来源地址https://www.toymoban.com/news/detail-470864.html
/****************书上代码***************************/
int SearchBST(Bitree T,int key, Bitree f, Bitree& p)
{
if (!T)
{
p = f;
return 0;
}
else if(T->data==key)
{
p = T;
printf("有重复");
return 1;
}
else if (T->data > key)
{
return SearchBST(T->left, key, T, p);
}
else
{
return SearchBST(T->right, key, T, p);
}
}
void InserBST(Bitree& T, int key)
{
Bitree p;
if (SearchBST(T, key, NULL, p)==0)//查找失败,进行插入
{
Bitree s =(Bitree) malloc(sizeof(BiTNode));
s->data = key;
s->left = NULL;
s->right = NULL;
if (!p)
{
T = s;
}
else if (key < p->data)
{
p->left = s;//被插入点作为*s左孩子
}
else {
p->right = s;
}
}
}
到了这里,关于二叉排序树的查找、插入、删除的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!