simplebinarytree.h

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

// SimpleBinaryTree.h: interface for the CSimpleBinaryTree class.
//
//////////////////////////////////////////////////////////////////////
/*
 *
 *
 *  Copyright (c) 2002 DigitalConvict <[e-mail]>
 *  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *
 * Contact info:
 * Site: http://www.digitalconvict.com
 * Email: [e-mail]
 */

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#define ITEM_NOT_PRESENT	-1
#define DUPLICATE_FOUND		-2
#define OUT_OF_MEMORY		-3
#define TREE_IS_FULL		-4

int GenericLongCompare(const void *a, const void *b);
void DoTest();

class CSimpleBinaryTree  
{
public:
	CSimpleBinaryTree();
	BOOL m_bAutoResize;
	BOOL m_bAllowDuplicates;
	BOOL ReSize(size_t nNewSize);
	BOOL RemoveItem(int nItem);
	BOOL Initialise(size_t nNumItems, size_t nItemSize,
		int(*compar)(const void *,const void *)=GenericLongCompare,
		int nGrowTrigger=90, int nGrowByValue=50,
		int nShrinkTrigger=10, int nShrinkByValue=50);
	int FindItem(const void* pvItemToFind, void* pvItemFound=NULL);
	int AddItem(const void* pNewData, void* pStoredObject=NULL);
	int GetSearchMethodThreshold();
	int GetTreeSize();
	int GetTotalItems();
	int GetShrinkByPercentage();
	int GetShrinkTriggerValue();
	int GetGrowByPercentage();
	int GetGrowTriggerValue();
	void SetShrinkByPercentage(int nPercentDecrease);
	void SetShrinkTriggerValue(int nPercentageUsed);
	void SetGrowByPercentage(int nPercentIncrease);
	void SetGrowTriggerValue(int nPercentageUsed);
	void FreeMemory();
	void SetSearchMethodThreshold(int nThreshold);
	void* GetItemPtr(int nItem);
	virtual ~CSimpleBinaryTree();

protected:
	BOOL m_bFullySorted;
	BOOL m_bInitialised;
	int BinarySearch(const void* pvItemToFind);
	int LinearSearch(const void* pvItemToFind);
	int m_nLastItemIndex;
	int m_nDoBSThreshold;
	int (*m_pfuncCompare)(const void *,const void *);
	int m_nTotalItems;
	int m_nShrinkByValue;
	int m_nGrowByValue;
	int m_nShrinkTrigger;
	int m_nGrowTrigger;
	size_t m_nSizeOfItem;
	size_t m_nArraySize;
	void **m_BTree;
	void SortItems();	
};