二叉排序树的查找、插入、删除

这篇具有很好参考价值的文章主要介绍了二叉排序树的查找、插入、删除。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

二叉排序树的定义

二叉排序树的查找

二叉排序树的插入


二叉排序树的定义

二叉排序树的定义
二叉排序树(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);
    }
}

非递归查找

//查找的非递归算法
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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构--6.5二叉排序树(插入,查找和删除)

    目录 一、创建  二、插入 三、删除   二叉排序树(Binary Sort Tree)又称为二叉查找树,它或者是一棵空树,或者是具有下列性质的二叉树: ——若它的左子树不为空,则左子树上所有结点的值均小于它的根结构的值; ——若它的右子树不为空,则右子树上所有结点的值均大

    2024年02月09日
    浏览(33)
  • 考研算法第十三天:二叉排序树 【二叉排序树的插入和遍历】

    这道题很妙。题目给的二叉排序树好像没学过其实就是二叉查找树。然后这道题主要的就是思路     1.先找到那个要删除节点所在处     2.找到之后处理分三种情况     删除的节点是叶节点,直接删除即可     删除的节点只有右节点或者左节点 将左节点或者右节点删除即可

    2024年02月05日
    浏览(49)
  • 【数据结构】18 二叉搜索树(查找,插入,删除)

    二叉搜索树也叫二叉排序树或者二叉查找树。它是一种对排序和查找都很有用的特殊二叉树。 一个二叉搜索树可以为空,如果它不为空,它将满足以下性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值都大于其根结点的键值 左、右子树都是二叉树 在

    2024年02月22日
    浏览(50)
  • 二叉搜索树(查找、插入、删除的讲解实现+图文并茂)

    目录 1. 二叉搜索树(BST)   1.1 二叉搜索树概念   1.2 二叉搜索树操作         1.2.1 二叉搜索树的查找         1.2.2 二叉搜索树的插入          1.2.3 二叉搜索树的删除 2. 二叉搜索树的实现   2.1BST基本结构   2.2 BST操作成员函数(非递归)   2.3 BST操作成员函数(递归) 3. 二

    2024年02月06日
    浏览(61)
  • 算法刷题Day 22 二叉搜索树的最近公共祖先+二叉搜索树中的插入操作+删除二叉搜索树中的节点

    根据二叉搜索树的性质,相比普通二叉树可以极大程度的简化代码,作为公共祖先其值一定在两个给定节点值之间,从树根往下遍历,第一次出现两个给定节点值之间的值,那个节点即为最近公共祖先(为什么是最近不是最远?根节点一般为最远,第一次出现的值处于两个给

    2024年02月17日
    浏览(44)
  • 【算法刷题day22】Leetcode:235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 50.删除二叉搜索树中的节点

    文档链接:[代码随想录] 题目链接:235. 二叉搜索树的最近公共祖先 题目: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深

    2024年04月13日
    浏览(40)
  • 代码随想录二刷day22 |二叉树之 235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点

    235. 二叉搜索树的最近公共祖先 题目链接 解题思路:讨论 中节点 p 中节点 q 或者 中节点 q 中节点 p ,其余的情况的最近公共祖先就是根节点。 使用递归三部曲 确定递归函数返回值以及参数 参数就是当前节点,以及两个结点 p、q。 返回值是要返回最近公共祖先,所以是Tr

    2024年02月08日
    浏览(49)
  • B树的插入与删除过程

    原树: 插入key后,若导致原节点数超过上限,则从中间位置( ⌈ m 2 ⌉ lceilfrac{m}{2}rceil ⌈ 2 m ​ ⌉ )将分成两部分,左部分包含的放在原节点中,右部分包含的放到新节点中,中间位置( ⌈ m 2 ⌉ lceilfrac{m}{2}rceil ⌈ 2 m ​ ⌉ )的节点插入原

    2024年02月13日
    浏览(32)
  • 链式二叉树的查找,遍历(递归实现)等接口的实现

    目录 前言: 一:二叉树的建立 (1)本文采用的二叉树表示方法 (2)手动建立一颗二叉树 二:二叉树的遍历 (1)二叉树的三种遍历方式 (2)分治思想 (3)前序遍历  (4)中序遍历 (5)后序遍历 三:求二叉树的节点和高度(深度) (1)求二叉树节点 ①求二叉树的全部节点 ②求二叉树的叶子节点

    2023年04月25日
    浏览(34)
  • 链表的初始化、取值、查找、插入、删除

    链表是一种常见的数据结构,它的节点不像数组一样是连续的,而是通过指针链接在一起的。下面是链表的初始化、取值、查找、插入和删除的示例代码,均使用C语言实现,并带有标头。 链表初始化代码: 以上代码中,定义了一个`ListNode`结构体,其中`val`表示节点的值,

    2024年02月07日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包