首页 > 代码库 > 数据结构学习之二叉排序树

数据结构学习之二叉排序树

2024-07-06 17:21:54   217人阅读

介绍：二叉排序树是以一定的规则排列树中元素，因而可以进行快速的排序和查询的树状数据结构，一般规则是：对于树中任意一个节点，左孩子严格小于根，根严格小于右孩子，有点像大根堆。（只是大根堆中左右孩子关系并不确定，且和根的关系是统一的，而且有上浮和下沉操作使得大根堆总是一棵完全二叉树，其不断弹出堆顶形成有序列的过程叫做堆排序。虽然二叉排序树中也有旋转操作使得树尽量平衡，但是由于数值大小分明的左右孩子，在进行平衡操作时远不如大根堆方便快捷。）对于一棵已经构造完成的排序二叉树，它的中序遍历序列即为升序排列的有序列，这就是二叉排序树的排序方法。

 

基本操作：二叉排序树的基本操作为查找、插入和删除。查找操作以及插入操作过程同二分查找类似，用待处理节点和当前节点进行数值比较，如果待处理节点的值小于当前节点的值，则进入当前节点的左子树进行操作，否则进入当前节点的右子树进行操作，直到到达叶子节点或者操作完成。删除操作有好几种实现方法，我是用的是“替罪羊节点法”，即从待删除节点的左子树中找到最大的一个节点（即“替罪羊节点”），用它的值覆盖待删除节点的值，然后删除替罪羊节点即可。在具体操作中还有许多需要注意的细节，在代码注释中有详细介绍。

 

一些想法：在最初的代码实现中，曾使用静态树，因为考虑到在处理大型数据时，重复的new或者malloc操作会使得程序慢的令人发指（并不是说指针慢，只是申请空间的过程耗费时间），所以一开始就开一段长度合适的空间，另外设置一个指针指示当前数组中可以用的节点，然后new操作在这里的实现就可以这样写：tmp->lc = &Tree[++index]，如果当前序列空间不够时，再用malloc或new申请另一段空间，有点类似内存池的概念。这样的静态操作经在线评测系统（POJ）测试，在进行最基本的操作来处理100，000左右的数据量时会快上两个甚至更多的数量级。静态树的查找和插入操作都可以正常进行，但是在进行删除操作时，我自己写的回收空间算法（为了节省空间，删除的节点重新归到可用空间中，想法是把待删除节点和当前排序树二叉树用的最后一个节点进行交换，再把上文提到的指针前移一位即可，代码实现可以写成：swap(*tmp , Tree[index--])。）总是不能正确执行，调了一段时间未果就先放在一边，写现在这个用指针操作实现的排序二叉树。

 

代码：（内置测试数据，并对于测试数据保证代码正确）

 

#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<iostream>
#include<algorithm>

#define MAXN 10005
#define MAX_INT 2147483647
#define LC(x) (x << 1)
#define RC(x) ((x << 1) | 1)
#define MID(x,y) ( (x + y) >> 1 )
#define TIME_BEGIN double t1 = clock()
#define TIME_END double t2 = clock();printf("\n%.2fms\n",t2-t1)

using namespace std;

struct node	//结构体定义
{
	int data;
	node *lc , *rc , *fa;
	node()//初始化 
	{
		data = http://www.mamicode.com/-1;>


联系
我们