simplebinarytree.cpp

一个简单二叉树类（非本人原创）

		if(m_pfuncCompare(pvItemToFind, &m_BTree[i])==0){
			nRetval=i;
			break;
		}
	}

	return nRetval;
}

/**********************************************************************
	Performs Binary Search.  Returns index of Element if found in
	BTree otherwise returns ITEM_NOT_PRESENT if Element does not 
	exist in the tree
**********************************************************************/
int CSimpleBinaryTree::BinarySearch(const void *pvItemToFind)
{
	int nLeftPivot=0;
	int nRightPivot=m_nTotalItems-1;
	int nIndex;

	while(nLeftPivot<=nRightPivot){
		nIndex=nLeftPivot+(nRightPivot-nLeftPivot)/2;
		int nResult=m_pfuncCompare(pvItemToFind, &m_BTree[nIndex]);

		if(nResult==0)
			break;
		else if(nResult>0)
			nLeftPivot=nIndex+1;
		else
			nRightPivot=nIndex-1;
	}

	if(nLeftPivot>nRightPivot){
		if(!m_bFullySorted && m_bAllowDuplicates){
			// if we haven't found an item and the tree is unsorted
			// then sort it and search for the item again
			SortItems();
			nIndex=BinarySearch(pvItemToFind);
		} else 
			nIndex=ITEM_NOT_PRESENT;
	}

	return nIndex;
}

/**********************************************************************
	Sets the threshold value at which searching will be done using the
	binary search method instead of the linear search method.  The
	The search method is switched when the number of items in the tree
	exceeds the threshold value.  The default value is 10.
**********************************************************************/
void CSimpleBinaryTree::SetSearchMethodThreshold(int nThreshold)
{
	if(nThreshold>0){
		if(nThreshold<m_nDoBSThreshold && m_nTotalItems>nThreshold)
			SortItems();
		m_nDoBSThreshold=nThreshold;
	}
}

/**********************************************************************
	Gets the current threshold value.  See SetSearchMethodThreshold for
	more details.
**********************************************************************/
int CSimpleBinaryTree::GetSearchMethodThreshold()
{
	return m_nDoBSThreshold;
}

/**********************************************************************
	Gets the number of items currently stored in the tree.
**********************************************************************/
int CSimpleBinaryTree::GetTotalItems()
{
	return m_nTotalItems;
}

/**********************************************************************
	Gets the maximum number of items the tree can hold.
**********************************************************************/
int CSimpleBinaryTree::GetTreeSize()
{
	ASSERT(m_bInitialised);
	return (int)m_nArraySize;
}

/**********************************************************************
	Returns the current value at which a Growth Resize is triggered
**********************************************************************/
int CSimpleBinaryTree::GetGrowTriggerValue()
{
	ASSERT(m_bInitialised);
	return m_nGrowTrigger;
}

/**********************************************************************
	Sets the percentage value of the Grow Trigger.  When the Tree has
	allocated nPercentageUsed of its current space, the tree is expanded
	by automatically resizing if and only if AutoResizing is enabled.
	The default value for the GrowTrigger is 90%
**********************************************************************/
void CSimpleBinaryTree::SetGrowTriggerValue(int nPercentageUsed)
{
	ASSERT(m_bInitialised);
	if(nPercentageUsed>0)
		m_nGrowTrigger=nPercentageUsed%100;
}

/**********************************************************************
	Sets the percentage value of the Shrink Trigger.  When the Tree is
	using less than nPercentageUsed of its current space, the tree is
	truncated by automatically resizing if and only if AutoResizing is
	enabled. The default value for the ShrinkTrigger is 10%
**********************************************************************/
void CSimpleBinaryTree::SetShrinkTriggerValue(int nPercentageUsed)
{
	ASSERT(m_bInitialised);
	if(nPercentageUsed>0)
		m_nShrinkTrigger=nPercentageUsed%100;
}

/**********************************************************************
	Returns the current value at which a Shrink Resize is triggered
**********************************************************************/
int CSimpleBinaryTree::GetShrinkTriggerValue()
{
	ASSERT(m_bInitialised);
	return m_nShrinkTrigger;
}

/**********************************************************************
	Sets the percentage value by which the tree will grow if
	AutoResize is enabled.  When AutoResize is enabled and a Resize is
	triggered the tree will allocate nPercentIncrease items to the tree
**********************************************************************/
void CSimpleBinaryTree::SetGrowByPercentage(int nPercentIncrease)
{
	ASSERT(m_bInitialised);
	if(nPercentIncrease>0)
		m_nGrowByValue=nPercentIncrease%100;
}

/**********************************************************************
	Returns the current GrowBy Percentage
**********************************************************************/
int CSimpleBinaryTree::GetGrowByPercentage()
{
	ASSERT(m_bInitialised);
	return m_nGrowByValue;
}

/**********************************************************************
	Sets the percentage value by which the tree will shrink if
	AutoResize is enabled.  When AutoResize is enabled and a Resize is
	triggered the tree will deallocate nPercentDecrease empty items from
	the tree.
**********************************************************************/
void CSimpleBinaryTree::SetShrinkByPercentage(int nPercentDecrease)
{
	ASSERT(m_bInitialised);
	if(nPercentDecrease>0)
		m_nGrowByValue=nPercentDecrease%100;
}

/**********************************************************************
	Returns the current ShrinkBy Percentage
**********************************************************************/
int CSimpleBinaryTree::GetShrinkByPercentage()
{
	ASSERT(m_bInitialised);
	return m_nShrinkByValue;
}

/**********************************************************************
	Global generic 'compare' function provided for the user.  Takes
	two longs and compares them. Returns 0 if equal, negative int if a<b,
	postive	int if a>b.
**********************************************************************/
int GenericLongCompare(const void *a, const void *b)
{
	long *aa, *bb;

	aa=*(long**)a;
	bb=*(long**)b;

	return(*aa-*bb);
}

/**********************************************************************
	Provides example usage of the functions contained in the
	CSimpleBinarySearch Class.  This doesn't actually work unless you
	cut and paste the code in DoTest into your project
**********************************************************************/
//#define BINARY_TREE_EXAMPLE

#ifdef BINARY_TREE_EXAMPLE

// increase MAXELEMS to say 100 to use Binary Search Method
#define MAXELEMS 10
#define FINDLOOP 10

void DoTest(){
	// create btree object
	CSimpleBinaryTree btree;
	int index=0;
	int nThreshold=0;

	//Initialise btree and don't specify a compare function
	// cos we're going to use the default global one.
	btree.Initialise(MAXELEMS,sizeof(long));
	
	//Set Allow Duplicates flag to FALSE
	btree.m_bAllowDuplicates=FALSE;

	//Get Search Method Threshold  value
	nThreshold=btree.GetSearchMethodThreshold();

	// Turn AutoResize Off
//	btree.m_bAutoResize=FALSE;

	// Increment and set the search threshold value
	nThreshold+=2;
	btree.SetSearchMethodThreshold(nThreshold);

	// Add some random numbers to the btree,
	printf("\r\n---ADDING NEW ITEMS\r\n\r\n");

	for(int i=0;i<MAXELEMS;i++){
		int x=rand()%MAXELEMS;
		if((index=btree.AddItem(&x))>=0)
			printf("allocated integer with value %d into position %d\r\n", x, index);
		else {
			switch (index) {
			case OUT_OF_MEMORY:
				printf("NO MORE MEMORY AVAILABLE\r\n");
				break;
			case DUPLICATE_FOUND:
				printf("DUPLICATE: where item has value %d\r\n",x);
				break;
			case TREE_IS_FULL:
				printf("TREE FULL AT INDEX=%d\r\n",i);
				break;
			}
		}
	}

	//Find out if some values exist in the tree
	printf("\r\n---SEARCH FOR & RETRIEVE ITEMS\r\n\r\n");

	for(i=0;i<FINDLOOP;i++){
		int item=rand()%MAXELEMS;
		if((index=btree.FindItem(&item))>=0){
			printf("Found int with value %d at index %d\r\n", item, index);
		} else {
			printf("Integer with value %d not found\r\n", item);
		}

		if(index>=0){
			//Get a pointer to the data held in the btree
			printf("Getting pointer to data at index: %d\r\n", index);

			long *dataptr;
			if((dataptr=(long*)btree.GetItemPtr(index))!=NULL)
				printf("Value of data referenced by dataptr=%d\r\n\r\n", *dataptr);
			else
				printf("Got NULL Pointer. i.e. No Data Here!!\r\n\r\n");
		}
	}

	printf("\r\nResizing tree: doubling\r\n\r\n");
	// Resize the Btree
	btree.ReSize(MAXELEMS*2);

	printf("\r\n---FIND & REMOVE EXISTING ITEMS\r\n\r\n");
	//Find out if some values still exist in the tree
	for(i=0;i<FINDLOOP;i++){
		int item=rand()%MAXELEMS;
		if((index=btree.FindItem(&item))>=0)
			printf("Found integer with value %d at index %d\r\n", item, index);
		else
			printf("Integer with value %d not found\r\n", item);
		
		// Remove elements from the btree
		printf("Result of Removing item at index %d: %s\r\n", index,
			((btree.RemoveItem(index)) ? "OK" : "BAD INDEX"));
	}

	printf("\r\nResizing tree: reducing by half\r\n\r\n");
	// Resize the Btree
	btree.ReSize(MAXELEMS/2);
}

#endif