main.c

红黑树和二叉查找树数据结构的实现以及二者的性能比较的C语言实现代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "rbTree.h"
#include "bsTree.h"
#include <windows.h>


#define   MaxNumber  300000 
static int randArray[MaxNumber];     


main()
{
	int arrayInt[9] = {8,11,17,15,6,1,22,25,27};
	int i;
	rbTree T1,T2;
	bsTree T3;
	rbTreeNode n1;
	bsTreeNode n2;
	double start,end;
	double time,sum;
	printf("\n\n                   ****  红黑树、二叉搜索树的实现和性能比较  ****\n\n");
	printf("\n按任意键继续........");
	getchar();


	printf("\n                                 1. 插入测试：\n\n");
	printf("\n按任意键继续........");
	getchar();


	printf("\n\n输入 8，11，17，15，6，1，22，25，27，建立红黑树T1:  \n\n");
	T1 = RB_NewTree();
	for (i=0;i<9;i++)
	{
		RB_Insert(T1, arrayInt[i]);
	}
	printf("\n按回车键 输出红黑树T1：\n");
	getchar();
	RB_Displiy_Tree(T1, RB_Pre_Disply);
	printf("\n按回车键输出红黑树T1的黑高度......");
	getchar();
	printf("   BH(T1) = %d\n",Bh_Tree(T1));
	printf("\n按回车键继续........");
	getchar();



	printf("\n                                 2. 删除测试：\n\n");
	printf("\n按任意键继续........");
	getchar();


	printf("\n\n删除红黑树T1中Key=15的节点:  \n\n");
	RB_Delete(T1, 15);
	printf("\n按回车键输出删除key = 15 后的红黑树T1......");
	getchar();
	RB_Displiy_Tree(T1, RB_Pre_Disply);
	printf("\n按回车键输出删除key = 15 后的红黑树T1的黑高度......");
	getchar();
	printf("   BH(T1) = %d\n",Bh_Tree(T1));
	printf("\n按回车键继续........");
	getchar();
	RB_Delete_Tree(T1, RB_Post_Visit);

	printf("\n                                 3. 查找测试：\n\n");
	printf("\n按回车键继续........\n");
	getchar();
	printf("\n随机生成1－300,000之间300,000个不同自然数的数组randArray1......\n\n");
	newRandArray(randArray, 1, MaxNumber);
	printf("\n利用随机数组randArray1建立红黑树 T2......\n\n");
	T2 = RB_NewTree_Rand(randArray, MaxNumber);
	printf("\n按回车键输出红黑树T2的黑高度......");
	getchar();
	printf("\nBH(T1) = %d\n",Bh_Tree(T2));
	printf("\n按回车键在红黑树T2中查找Key=15000的节点......\n");
	getchar();
	start = (double)clock();
	start = start/(double)CLOCKS_PER_SEC;
	n1 = RB_SearchInTree(T2, 15000);
	//Sleep(1500);
	end = (double)clock();
	time = end/(double)CLOCKS_PER_SEC - start;
	if ( NULL != n1)
		printf("\n查找成功，输出查找花费时间time1 = %.20lf：\n\n",time);
	else
		printf("\n查找失败，输出查找花费时间time1 = %.20lf：\n\n",time);
	printf("\n按回车键删除释放红黑树T2........");
	getchar();
	RB_Delete_Tree(T2, RB_Post_Visit);
	printf("\n按回车键继续........\n");
	getchar();

	printf("\n生成1－300,000之间300,000个不同自然数的数组randArray2......\n");
	newRandArray(randArray, 1, MaxNumber);
	printf("\n利用随机数组randArray2建立二叉搜索树T3......\n");
	T3 = BS_NewTree_Rand(randArray, MaxNumber);
	printf("\n按回车键在二叉搜索树 T3 中查找Key=15000的节点......\n\n");
	getchar();
	start = (double)clock();
	start = start/(double)CLOCKS_PER_SEC;
	n2 = BS_SearchInTree(T3, 15000);
	//Sleep(1500);
	end = (double)clock();
	time = end/(double)CLOCKS_PER_SEC - start;
	if ( NULL != n2)
		printf("\n查找成功，输出查找花费时间time2 = %.20lf：\n\n",time);
	else
		printf("\n查找失败，输出查找花费时间time2 = %.20lf：\n\n",time);
	printf("\n按回车键删除释放二叉搜索树T3........");
	getchar();
	BS_Delete_Tree(T3, BS_Post_Visit);
	printf("\n按回车键继续........\n");
	getchar();

    printf("\n                                 4. 求平均时间：\n\n");
    printf("\n按回车键继续........\n");
	getchar();

	printf("\n\n重复 5 次 3) 中操作，求在红黑树中查找Key=15000的节点的平均时间:  \n\n");
	sum = 0;
	for(i=0;i<6;i++)
	{
		newRandArray(randArray, 1, MaxNumber);
		T2 = RB_NewTree_Rand(randArray, MaxNumber);
		start = (double)clock();
	    start = start/(double)CLOCKS_PER_SEC;
		n1 = RB_SearchInTree(T2, 7);
		//printf("%d,\n",n1->rbkey);
		//Sleep(100);
		end = (double)clock();
	    time = end/(double)CLOCKS_PER_SEC - start;
		sum = sum + time;
		//RB_Displiy_Tree(T2, RB_Pre_Disply);
		//getchar();
		RB_Delete_Tree(T2, RB_Post_Visit);
	}
	printf("\n 红黑树中查找Key=15000的节点的平均时间time = %.20lf：\n\n",sum/(double)6);
	printf("\n 按回车键继续........");
	getchar();



	printf("\n\n重复 5 次 3) 中操作，求在二叉搜索树中查找Key=15000的节点的平均时间:  \n\n");
	sum = 0;
	for(i=0;i<6;i++)
	{
		newRandArray(randArray, 1, MaxNumber);
		T3 = BS_NewTree_Rand(randArray, MaxNumber);
		start = (double)clock();
	    start = start/(double)CLOCKS_PER_SEC;
		n2 = BS_SearchInTree(T3, 15000);
		//printf("%d,",n2->bskey);
		//Sleep(100);
		end = (double)clock();
	    time = end/(double)CLOCKS_PER_SEC - start;
		sum = sum + time;
		BS_Delete_Tree(T3, BS_Post_Visit);
	}
	printf("\n二叉搜索树中查找Key=15000的节点的平均时间time = %.20lf：\n\n",sum/(double)6);
	printf("\n按回车键继续........");
	getchar();


	printf("\n                    5. 修改红黑树算法并完成算法 OS_Key_Rank(T,k) ：\n\n");
	printf("\n按回车键继续........");
	getchar();


	printf("\n\n输入 1,2,3,4,5,6,7,8，建立红黑树T4......  \n\n");
	T1 = RB_NewTree();
	for (i=1;i<9;i++)
	{
		RB_Insert(T1, i);
	}
	printf("\n按回车键输出红黑树T4：\n\n");
	getchar();
	RB_Displiy_Tree(T1, RB_Pre_Disply);
	printf("\n按回车键输出红黑树T2的黑高度......");
	getchar();
	printf("\nBH(T4) = %d\n",Bh_Tree(T1));
	printf("\n按回车键继续........");
	getchar();
	printf("\nk=6, 输出OS_Key_Rank的返回值 OS_Key_Rank(T1, k) = %d\n",OS_Key_Rank(T1, 6));
	printf("\n按回车键删除释放红黑树T4........");
	getchar();
	RB_Delete_Tree(T1, RB_Post_Visit);
    printf("\n按回车键结束演示........");
	getchar();
}