【数据结构】二叉排序树(c风格、结合c++引用)

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉排序树(c风格、结合c++引用)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1 基本概念

结构体定义

各种接口

2 二叉排序树的构建和中序遍历

递归版单次插入

非递归版单次插入

3 二叉排序树的查找

非递归版本

递归版本

4 二叉排序树的删除(难点)


1 基本概念

        普通二叉排序树是一种简单的数据结构,节点的值根据特定顺序(通常是升序或降序)排列。然而,如果普通二叉排序树不平衡,即左、右子树的高度相差很大时,查询效率可能会降低。因此引出了avl树、红黑树等一系列高阶数据结构。

       基本性质:

  • 若它的左子树不空,则左子树上所有结点的值均小于根结点的值。
  • 若它的右子树不空,则右子树上所有结点的值均大于根结点的值。
  • 它的左、右子树均为为⼆叉排序树。
  • 二叉排序树的查找时间复杂度为树的高度,即为O(以2为底N的对数) ,下面全写成O(logN)
  • 二叉排序树的中序遍历输出是一个递增的数列。

结构体定义

typedef struct BSTreeNode
{
	int val;
	struct BSTreeNode* left;
	struct BSTreeNode* right;
}BSTNode,*BiTree;

各种接口

【数据结构】二叉排序树(c风格、结合c++引用),数据结构,c语言,c++

关于用到C++中的引用:

BSTNode是结构体struct BSTreeNode的别名,BiTree是结构体struct BSTreeNode指针。

在链表中,首次插入时需要修改头节点,由于头节点的定义也是一个指针,所以要修改一个一级指针,必须传入二级指针或者一级指针的引用,二叉树也是一样,首次插入需要修改根节点的指向,所以这里用引用,当然也可以用二级指针,严蔚敏老师编写的数据结构中也经常用到C++的引用。

而再次或多次进行插入时,我们用cur去遍历链表或二叉树,其实是修改链表和二叉树的一个个结构体,这时我们只需要结构体指针,其实就只需要一级指针即可。

因此,我们直接用二级指针或一级指针的引用,就能解决所有的问题。 


2 二叉排序树的构建和中序遍历

 构建原则:

①根节点为空,先构建根节点。

②插入节点的值小于根节点的值,去根节点的左子树寻找插入位置。

③插入节点的值大于根节点的值,去根节点的右子树寻找插入位置。

void Create(BiTree& root,int* a,int n)
{
	for (int i = 0; i < n; ++i)
	{
		BST_InsertR(root, a[i]);
        //BST_Insert(root, a[i]);
	}
}

遍历数组O(N),数组每个元素插入O(logN),因此构建的时间复杂度是O(NlogN)

递归版单次插入

int BST_InsertR(BiTree& root, int x)
{
    //进行插入
	if (root == nullptr)//空树或者走到空
	{
        BSTNode* newnode = (BiTree)malloc(sizeof(BSTNode));
	    if (newnode == nullptr)
	    {
	    	perror("malloc fail");
		    exit(-1);
	    }
	    newnode->val = x;
	    newnode->left = newnode->right = nullptr;
		root = newnode;
		return 1;//插入成功
	}

	if (root->val == x)
		return -1;//插入失败,节点元素值不能相同

	if (root->val > x)//x小于根节点的值,就去左子树插入
		return BST_InsertR(root->left, x);

	if (root->val < x)//x大于于根节点的值,就去右子树插入
		return BST_InsertR(root->right, x);
}

非递归版单次插入

⭕定义两个指针,cur和prev,prev指向cur的根节点,cur最后走到空,对prev的左右指针进行操作,比对prev->val和x,如果val<x,就让prev->right指向新节点,反之。

int BST_Insert(BiTree& root, int x)
{
	//二叉排序树左孩子的值比根的值要小,右孩子的值比根的值要大
	BSTNode* newnode = (BiTree)malloc(sizeof(BSTNode));
	if (newnode == nullptr)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->left = newnode->right = nullptr;

	//第一次进来root为空
	if (root == nullptr)
	{
		root = newnode;
		return 0;
	}
	//第二次开始往后遍历
	BSTNode* cur = root;
	BSTNode* prev = nullptr;
	while (cur)//让cur走到空
	{
		prev = cur;
		if (cur->val < x)
		{
			cur = cur->right;
		}
		else if (cur->val > x)
		{
			cur = cur->left;
		}
		else
		{
			return -1;//插入失败,不能有元素相等的情况
		}
	}
	if (prev->val < x)
	{
		prev->right = newnode;
	}
	if (prev->val > x)
	{
		prev->left = newnode;
	}
	return 0;//插入成功
}

假设我们用这个数组去构建一棵树:

【数据结构】二叉排序树(c风格、结合c++引用),数据结构,c语言,c++

结果是这样的:

【数据结构】二叉排序树(c风格、结合c++引用),数据结构,c语言,c++

中序遍历:

void InOrder(BiTree root)
{
	if (root == nullptr)//空树或走到空
		return;
	InOrder(root->left);//左子树
	printf("%d ", root->val);//根
	InOrder(root->right);//右子树
}

输出的结果一定是一个递增序列,因此二叉排序树的中序遍历才有意义。

3 二叉排序树的查找

查找原则:

①所查找的值比当前节点的值要小,就去左子树找

②所查找的值比当前节点的值要大,就去右子树找

③查找成功,返回结构体指针BSTNode*/BiTree

二叉排序树的最大查找次数,就是树的深度,类似于折半查找,每查一次排除一半的树。

因此二叉排序树的查找时间复杂度为O(logN) 。

非递归版本

BSTNode* BinarySearch(BiTree root,int x)
{
	BSTNode* cur = root;
	while (cur)
	{
		if (cur->val < x)
		{
			cur = cur->right;
		}
		else if (cur->val > x)
		{
			cur = cur->left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}

递归版本

BSTNode* BinarySearchR(BiTree root, int x)
{
	if (root == nullptr)//空树或者找到空了还没找到
		return nullptr;
	if (x == root->val)
		return root;
	if (x > root->val)//大于就去右子树找
		return BinarySearchR(root->right, x);
	if(x < root->val)//小于就去左子树找
		return BinarySearchR(root->left, x);
}

4 二叉排序树的删除(难点)

删除原则:

①删除节点的右子树为空,左子树不为空,把左子树顶上来。

②删除节点的左子树为空,右子树不为空,把右子树顶上来。

③删除节点的左右子树都不为空,要么在左子树中找最大的数据和根的数据交换,要么在右子树中找最小的数据和根的数据交换。

void DeleteNode(BiTree& root, int x)
{
	if (root == nullptr)//找不到或者根为空,直接返回
	{
		return;
	}

	//先找后删除,递归
	if (x < root->val)
	{
		DeleteNode(root->left, x);
	}
	if (x > root->val)
	{
		DeleteNode(root->right, x);
	}
	//找到了,执行删除
	if (root->val == x)
	{
		if (root->left == nullptr)//左子树为空,把右子树顶上去
		{
			BiTree tmp = root;
			root = root->right;
			free(tmp);
		}
		else if (root->right == nullptr)//右子树为空,把左子树顶上去
		{
			BiTree tmp = root;
			root = root->left;
			free(tmp);
		}
		else//左右子树均不为空,要么在左子树中找最大的数据和根的数据交换,要么在右子树中找最小的数据和根的数据交换
			//采用前者即可,左子树的最大数据就是左子树的最右结点
		{
			BiTree left = root->left;
			while (left->right)
			{
				left = left->right;
			}
			root->val = left->val;
			//free(left);//不能这么做,万一这个结点有左子树怎么办?
			//只能重新在T的左子树找这个结点,复用递归删除这个结点
			DeleteNode(root->left, left->val);
		}
	}
}

图解何为“顶上来” 

由于函数传参用到引用,因此root就是上一层函数root->left或者root->right的别名

【数据结构】二叉排序树(c风格、结合c++引用),数据结构,c语言,c++

定义指针tmp去指向root形参,root形参用root(1)表示一下:

【数据结构】二叉排序树(c风格、结合c++引用),数据结构,c语言,c++

这时我们想让root->right变为root(1)->right,而root(1)就是root->right的别名,因此我们直接让root(1)=root(1)->right,然后去free(tmp),用代码表示就是这样:

【数据结构】二叉排序树(c风格、结合c++引用),数据结构,c语言,c++


同理,右子树为空,把左子树顶上去:

【数据结构】二叉排序树(c风格、结合c++引用),数据结构,c语言,c++


当左右子树都不为空时,要么去左子树中找最大的数据去替换删除节点,要么去右子树中找最小的数据去替换删除节点。

而左子树中的最大数据位于左子树的最右深处节点,右子树中的最小数据位于右子树的最左深处节点。

什么是“替换”:把要删除的根节点的值与左子树最右节点的值交换,然后“删除”掉左子树最右节点;或者把要删除的根节点的值与右子树最左节点的值交换,然后“删除”掉右子树最左节点。

【数据结构】二叉排序树(c风格、结合c++引用),数据结构,c语言,c++

何为删除?真的是直接free掉吗?

【数据结构】二叉排序树(c风格、结合c++引用),数据结构,c语言,c++ 删除59,那它的左子树咋办?直接free就坑了!

复用函数去递归删除59,让59的左子树顶上去:

【数据结构】二叉排序树(c风格、结合c++引用),数据结构,c语言,c++文章来源地址https://www.toymoban.com/news/detail-752603.html

到了这里,关于【数据结构】二叉排序树(c风格、结合c++引用)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构排序二叉树(下)

    哎,调了几天深度学习模型,今天来更新排序二叉树 文章目录 前言 一、排序二叉树的结构定义 二、在排序二叉树添加数据 三、定义创建排序二叉树函数 四、查找一棵二叉排序树中的结点x的所在层数 五、删除二叉排序树中Tx的节点 六、查找二叉排序树中的所有小于ke

    2024年01月20日
    浏览(35)
  • 详解数据结构——二叉排序树

    目录 二叉排序树 二叉排序树的查找 二叉排序树的插入 二叉排序树的删除 查找时间效率分析     二叉排序树,又称二叉查找树(BST,Binary Search Tree)一棵二叉树或者是空二叉树,或者是具有如下性质的二叉树:  左子树上所有结点的均小于根结点的; 右子树上所有

    2024年02月03日
    浏览(41)
  • 数据结构学习笔记——二叉排序树

    查找算法中,基于树这种数据结构进行查找即为树形查找,可将其分为 二叉排序树 、 平衡二叉树 和 B树 三种树形查找方法: 二叉排序树也称为二叉查找树或二叉搜索树(注意:与二分查找的判定树不同),其中各结点值的大小关系是: 左子树根结点右子树 ,且左、右子树

    2024年02月09日
    浏览(55)
  • 数据结构实现二叉排序树

    摘  要 二叉排序树(Binary Search Tree,BST),又叫做二叉查找树,二叉搜索树,是一种对查找和排序都有用的特殊二叉树。因为二叉排序树的中序遍历有序性,即得到的递增的序列,由于有序,因此其查找与二分查找类似,每次都可以缩小查找范围,查询效率较高。同时因为二叉排

    2024年02月03日
    浏览(32)
  • 【数据结构】【算法】二叉树、二叉排序树、树的相关操作

    树结构是以分支关系定义的一种层次结构,应用树结构组织起来的数据,逻辑上都具有明显的层次关系。 操作系统中的文件管理系统、网络系统中的域名管理、数据库系统中的索引管理等都使用了树结构来组织和管理数据。 树 Tree 是由n个节点组成的有限集合。在任意一颗非

    2024年02月04日
    浏览(50)
  • 【数据结构】二叉排序树——平衡二叉树的调整

    参考视频: 懒猫老师-数据结构-(59)平衡二叉树【互动视频】 (1)什么是平衡二叉树 平衡二叉树(Balanced Binary Tree)是一种特殊的二叉查找树,它的目的是保持树的高度尽量平衡,以保证查找、插入、删除等操作的时间复杂度为 O(log n)。 常见的平衡二叉树算法包括 AVL 树、红

    2024年02月04日
    浏览(38)
  • 【开卷数据结构 】二叉排序树(BST)

    目录 二叉排序树(BST) 二叉排序树的定义 二叉排序树的操作 二叉排序树的查找 代码演示 二叉排序树的插入 代码演示 二叉排序树的构造 代码演示 二叉排序树的删除 Q:什么是二叉排序树 A: 二叉排序树或者是一棵空树,或者是具有如下性质的二叉树 1) 若它的左子树不空

    2024年02月11日
    浏览(41)
  • 数据结构-二叉排序树(建立、查找、修改)

    二叉排序树是动态查找表的一种,也是常用的表示方法。 其中,它具有如下性质: 1.若它的左子树非空,则其左子树的所有节点的关键值都小于根节点的关键值。 2.若它的右子树非空,则其右子树的所有节点的关键值都大于根结点的关键值。 3.它的左右子树也分别都是二叉排

    2024年02月04日
    浏览(41)
  • 数据结构二叉排序树应用一

    2022.11.19 本关任务:输入一个无序序列,创建一棵二叉排序树。 为了完成本关任务,你需要掌握:1.二叉排序树定义,2.如何创建一棵二叉排序树。 二叉排序树定义 二叉排序树:即一个二叉树,它的每一个结点的左孩子的data值比当前结点的data值小,而右孩子结点的data值比当

    2024年02月08日
    浏览(34)
  • 【数据结构】:二叉树与堆排序的实现

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的有一个特殊的结点,称为根结点,根节点没有前驱结点 除根节点外,其余结点被分成M(M0)个互不相交的集合T1、

    2024年02月08日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包