本文由DigitalConvict供稿。
原文出處：http://www.codeguru.com/algorithms/SimpleBinaryTree.html
環境: (無特別限制) 在VC6 上開發
我不會詳細介紹二叉樹理論的詳細細節，因為這些東西，Per Nilsson 已經在他的“二叉樹”中討論過了，你可以在如下地址here找到詳細的細節。
對半查找樹對於找到在一個列表中很少變化的項來說是很有用的。添加和刪除操作的開銷是很大的，只主要是因為對半查找樹的平衡性所決定的。
我們可以這樣說這個類是在同一主題上的一個不同的執行方式。
執行細節
創建這棵樹
要創建二叉樹，可以簡單的創建一個CSimpleBinaryTree 對象並初始化。
#define MAXELEMS 100或
CSimpleBinaryTree btree;
btree.Initialise(MAXELEMS,sizeof(CSomeObject));btree.Initialise(MAXELEMS,sizeof(CSomeObject), someCompareFunction);或btree.Initialise(MAXELEMS,sizeof(CSomeObject), someCompareFunction, nGrowTrigger, nGrowByValue, nShrinkTrigger, nShrinkByValue);"someCompareFunction"是一個有兩個指針參數的函數的指針，這個函數根據第一個參數是否小於，等於，大於第二個參數而分別返回負數，0和正數。CSimpleBinaryTree 提供了一個通用的全局比較函數，它可以比較兩個長整型的指針。
添加元素
要向這棵樹添加一個子項,可以簡單的調用AddItem()並傳一個指針給它，用來存放添加後的對象。在內部，相關數據通過指針被拷貝到動態分貝的內存上。CSomeObject sObj;或
CSomeObject *psObj1=&sObj;
CSomeObject psObj2;
int nResult;
nResult=btree.AddItem(&sObj);nResult=btree.AddItem(psObj1);或nResult=btree.AddItem(psObj1, psObj2);AddItem() 函數返回兩個值。第一個是整型結果。如果子項被成功添加了，子項的索引值會被成功返回，如果沒有成功添加，就會返回錯誤代碼:
· DUPLICATE_FOUND
· OUT_OF_MEMORY
· TREE_IS_FULL
第二個返回值是可選擇的第二個參數值。如果操作成功,那末指向新創建對象的指針被返回了, 如果操作不成功，該指針被賦值為空。
DUPLICATE_FOUND僅當公共變量m_bAllowDuplicates被設為FALSE時才返回，否則，這個樹將允許復制數據（缺省情況）。
如果復制操作不被允許，那末這棵樹將會在每次被搜索時都會添加子元素以便判斷子元素是否存在。這一點就降低了添加子項的速度，但是也潛在的節省了內存分配的數量。
刪除元素
要刪除一個子項，可以簡單的調用RemoveItem() 函數，並設置上我們要刪除的子項的索引值。
BOOL bResult;
bResult=RemoveItem(nIndex);
如果該項被成功地從樹中刪除了,函數返回TRUE, 否則返回FALSE;
當一個子項從樹中刪除時，其上面所有的元素對應的子項左移一個位置並“子項總數”減一。
這一點，說明效率並不高,潛在的,函數有可能不得不遍歷整棵樹.無論如何從二叉樹添加和刪除元素是天生的比其他的存儲/修補算法要慢，這是因為二叉遍歷網絡樹要求元素有序的事實。
遍歷這棵樹
要判斷一個元素是否在這棵樹中存在,可以簡單的調用FindItem() 函數.int nIndex;或
nIndex = btree.FindItem(psObj);CSomeObject *pFoundObject;FindItem() 返回兩個值.如果子項存在，第一個值就是子項的索引值，如果不存在，賦值為ITEM_NOT_PRESENT value.第二個返回值是可選擇的第二個參數值。如果子項被發現了，pFoundObject 將指向它在樹中的對象,如果子項沒有被發現，pFoundObject 賦為空;
nIndex = btree.FindItem(psObj,pFoundObject);
在CSimpleBinaryTree 中有兩個搜索算法.線性搜索和對半搜索.線性搜索只在樹種子項數目小於指定值的時候才使用 (缺省為10),從這個點以後的各項，將使用對半搜索.這樣做的原因是線性查找不要求元素進行排序並且它的運算規則相對要簡單的多.因此對於小數目項來說，線性查找是理想的.
如果在樹中允許復制(m_bAllowDuplicates=TRUE) ，那末平衡(所有子項排序)操作只有當在“被要求”的時候進行，而不是像m_bAllowDuplicates=FALSE and並且所有子項在每次添加新的子項時都會進行排序.相反地,排序可能會在調用FindItem() 函數時進行.當用FindItem()查找一個子項時，使用的是對半查找算法,即使該項存在，查找也可能失敗.這樣的原因是這個樹並不是完全平衡的.這這種情況下，算法查找子項時，就會失敗,同時也說明該樹並非完全平衡的,通過排序使得該樹平衡，然後再遞歸的調用FindItem()函數.一旦該樹平衡了，一個內部標記將會被設置，並且這個標記在添加一個新元素時不會被設置,因而避免了任何一個遞歸的循環.因此後來的FindItem()調用就會避免重復的調用.對於程序員來說，沒有必要作些特殊的操作.以上說的只是這個類中眾多內部處理中一個而已.
這樣在允許復制操作的時候，每添加一個子項就不必再調用SortItems() 了，從而效率得到很大的提高.此處使用的是C 語言庫中的qsort()函數來實現排序算法的.
重設樹的大小
通過ReSize()來設置二叉樹的子項數目，以滿足添加和刪除的需要.btree.ReSize(300);通過調用ReSize()可以設置樹中可以容納的最大子項數. 然而當樹中已經存在200個元素並且其最大容納子項數為250， 如果作如下調用btree.ReSize(100),那末樹中開始的100元素 將會傳送到新的指針數組上面，而後面的120個元素將會從樹中被移除，其占用的內存也會被釋放掉.
通過設置公共成員變量m_bAutoResize = TRUE (缺省),該樹可以通過成員變量中用於控制增減和減少的參數自動的設置元素數目的大小.
增加和消減
當公共成員變量m_bAutoResize被設為TRUE時，增加和消減參數控制樹的元素數目.每項操作會有兩個變量.一個觸發器，一個增加/消減值.所有的值用占當前樹中元素數目的百分比來表示.
觸發器的值可以確定增長或消減操作的發生.增加/消減 的百分比確定了該樹增加或消減的程度.
比如，如果在樹中我有80 元素，被允許的最大子項數為100，m_bAutoResize 設為TRUE.同樣的增長觸發器被設為90 (90%) ，消減觸發器被設為10 (10%)，增長和消減的值都設為50 (50%).
如果我向樹中添加11個元素,該樹將會有91%的填充率，同時增長觸發器也會被激活.那末此時該樹可容納的元素數目就會增加50%,i.e. 在內部會調用ReSize(150).同樣的，如果我刪除了80 個元素中的71個，該樹將只有9%的填充率，消減觸發器會被激活，從而導致樹中可容納元素樹消減50%,i.e. 在內部會調用ReSize(50).
重設大小的操作代價昂貴，因此應該盡可能的避免.上面的例子中給出了增長/消減觸發器的缺省值和增長/消減的對應值。
公共方法概述
AddItem() 為新元素分配一個空間,把指針添加到二叉樹的元素數組中,從而添加.向二叉樹中添加一個新元素如果失敗,返回負數 RemoveItem() 從二叉樹中刪除某項. 該項被刪除厚,此項上面的所有指針左移一個位置,子項的數目相應地更新,如果nItem在有效的索引范圍內,返回TRUE FindItem() 決定使用哪一種查找算法查找元素,如果數組大小小於對半查找的開始位置,線性查找將被執行,而不是對半查找. ReSize() 根據nNewSize對二叉樹進行增長和消減.如果nNewSize等於當前的數目或者沒有更多的內存可供分配了的話返回FALSE,否則返回 TRUE. Initialise() 在一個對象被創建後,初始化函數必須被調用.設置內部成員值並為二叉樹數組分配空間. GetSearchMethodThreshold() 獲取當前查找算法的臨界值. GetTotalItems() 取得當前樹中存放的子項的數目. GetTreeSize() 取得樹中子項數目的最大值. GetShrinkTriggerValue() 在消減觸發器激活時，返回當前的值 SetShrinkTriggerValue() 設置消減觸發器的值.當該樹使用的空間與自身的空間百分比小於nPercentageUsed,當且僅當AutoResizing有效時，該樹會自動的重新設置子項數目.缺省的消減觸發器值為10% GetShrinkByPercentage() 返回當前消減百分比 SetShrinkByPercentage() 當AutoResize 有效時，設置消減百分比的值.當AutoResize有效並且重設大小被觸發時，該樹將會釋放nPercentDecrease相關項. GetGrowTriggerValue() 在增長觸發器激活時，返回當前的值 SetGrowTriggerValue() 設置增長觸發器的值.當該樹已經分配了使用的百分比時,當且僅當AutoResizing有效時，該樹會自動的重新設置子項數目.缺省的增長觸發器值為90% GetGrowByPercentage() 返回當前增長百分比 SetGrowByPercentage() 當AutoResize 有效時，設置增長百分比的值.當AutoResize有效並且重設大小被觸發時，該樹將會給nPercentIncrease相關項分配空間. FreeMemory() 釋放所有的堆空間，包括二叉樹數組以及其中包括的子項.用戶不必調用這個函數，除非他想立刻釋放內存並願意刪除二叉樹. 最好的辦法是，使用缺省的析構函數自動的調用這個函數. SetSearchMethodThreshold() 設置對半查找的臨界值，以區分何時使用對半查找和線性查找。查找方法會根據這個臨界值進行切換.缺省值為10. GetItemPtr() 返回一個空類型指針，用於指向在二叉樹子項數組中nItem索引對應的子項的指針.如果索引值超出了有效值，返回空. GenericLongCompare() 提供給用戶的全局比較函數.用來比較兩個long型數據（a,b）.如果相等，返回0,如果a<b,返回負數如果 a>b. 返回正數 DoTest() CSimpleBinarySearch類中提供了測試函數.在使用這個函數前，必須先定義BINARY_TREE_EXAMPLE .
本文配套源碼
