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

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

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

一些想法：在最初的代码实现中，曾使用静态树，因为考虑到在处理大型数据时，重复的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 = -1;
		lc = rc = fa = NULL;
	}
};
node *root = new node;;

int ary[15] = {0,213,5,12,45,65,2,1,4,8,6,554,52,-1},n = 12;

void myFind(int now , node *&tmp)//查询函数（从参数节点返回信息） 
{
	tmp = root;
	while(tmp)
	{
		if(now > tmp->data)	//查询值大于当前节点值，进入右子树 
			tmp = tmp->rc;
		else if(now < tmp->data)//查询值小于当前值，进入左子树 
			tmp = tmp->lc;
		else	//找到查询值，返回 
			return ;
	}
}

void myInsert(int now)//插入函数 
{
	node *tmp = root;
	while(1)
	{
		if(now > tmp->data)	//若待插入节点大于当前节点的值，则进入右子树 
		{
			if(!tmp->rc)//当前节点右子树为空，则将待插入节点插入到此位置 
			{
				tmp->rc = new node;
				tmp->rc->data = now;
				tmp->rc->fa = tmp;
				return ;
			}
			tmp = tmp->rc;
		}
		else if(now < tmp->data)//若待插入节点小于当前节点的值，则进入左子树 
		{
			if(!tmp->lc)//当前节点左子树为空，则将待插入节点插入到此位置 
			{
				tmp->lc = new node;
				tmp->lc->data = now;
				tmp->lc->fa = tmp;
				return ;
			}
			tmp = tmp->lc;
		}
		else	//树中已有待插入节点，则直接返回 
			return ;
	}
}

void myDelete(node *&tmp)//删除函数  （通过节点） 
/*
若想通过数值删除，则只需先调用一次myFind函数 
*/ 
/*
删除函数的思想是“替罪羊节点”思想：即在待删除节点左子树中
找到最大的节点p（即替罪羊），用它的值覆盖待删除节点的值，然后删除
p即可，其中有很多细节需要注意 
*/ 
{
	node *ano = tmp->lc;
	if(!ano)//若待删除节点没有左子树 
	{
		if(tmp == tmp->fa->lc)//若带删除节点是其父节点的左子树 
			tmp->fa->lc = tmp->rc;
		else					//若带删除节点是其父节点的右子树 
			tmp->fa->rc = tmp->rc;
		if(tmp->rc)	//不能直接访问tmp->rc的父节点，需要先判断tmp->rc是否为空 
			tmp->rc->fa = tmp->fa;
		free(tmp);
	}
	else
	{
		while(ano->rc)	//寻找左子树中的最大节点 
			ano = ano->rc;
		tmp->data = ano->data;//值覆盖 
		if(ano->lc)	//若“替罪羊”有左孩子 
		{
			if(ano->fa->data < ano->lc->data)	
			//判断“替罪羊”的左孩子和替罪羊父亲节点的大小关系 
				ano->fa->rc = ano->lc;
			else
				ano->fa->lc = ano->lc;
			ano->lc->fa = ano->fa;
		}
		else
		{
			if(ano->fa == tmp)	//判断替罪羊是左子树根还是左子树的其他节点 
				ano->fa->lc = NULL;
			else
				ano->fa->rc = NULL;
		}
		free(ano);
	}
}

void myInit()//初始化整棵树 
{
	root->data = MAX_INT;
	for(int i = 1;i <= n;i ++)
		myInsert(ary[i]);
}

void myPrint(node *tmp)//中序遍历方式输出整棵树，形成有序列 
{
	if(!tmp)
		return ;
	myPrint(tmp->lc);
	cout<<tmp->data<<" ";
	myPrint(tmp->rc);
}

void myInit_test()	//myInit测试函数
{
	cout<<endl; 
	cout<<"====myInit函数测试开始==========="<<endl;
	cout<<endl;
	myInit();
	cout<<endl;
	cout<<"====myInit函数测试结束==========="<<endl;
	cout<<endl;
}

void myPrint_test() //myPrint测试函数 
{
	cout<<endl;
	cout<<"====myPrint函数测试开始==========="<<endl;
	cout<<endl;
	myPrint(root->lc);
	cout<<endl;
	cout<<endl;
	cout<<"====myPrint函数测试结束==========="<<endl;
	cout<<endl;
}

void myFind_test() //myFind测试函数 
{
	cout<<endl;
	cout<<"====myFind函数测试开始==========="<<endl;
	cout<<endl;
	for(int i = 1;i <= n;i ++)
	{
		node *tmp;
		myFind(ary[i] , tmp);
		cout<<tmp->data<<" ";
	}
	cout<<endl;
	cout<<endl;
	cout<<"====myFind函数测试结束==========="<<endl;
	cout<<endl;
}

void myDelete_test() //myDelete测试函数 
{
	cout<<endl;
	cout<<"====myDelete函数测试开始==========="<<endl;
	cout<<endl;
	for(int i = 1;i <= n;i ++)
	{
		node *tmp;
		myFind(ary[i] , tmp);
		myDelete(tmp);
		myPrint(root->lc);
		cout<<endl;
		myInsert(ary[i]);
	}
	cout<<endl;
	cout<<"====myDelete函数测试结束==========="<<endl;
	cout<<endl;
}

int main()
{
	TIME_BEGIN; 
	myInit_test();			//myInit函数测试 
	myPrint_test();			//myFind函数测试
	myFind_test();			//myFind函数测试
	myDelete_test();		//myDelete函数测试 
	TIME_END;
}