简单二叉树类

【 tulaoshi.com - C语言心得技巧 】

简单二叉树类
翻译: 丁顺光

（本文来源于图老师网站，更多请访问http://www.tulaoshi.com）

下载本文示例源代码



本文由DigitalConvict供稿。
原文出处：http://www.codeguru.com/algorithms/SimpleBinaryTree.html

环境: (无特别限制) 在VC6 上开发

我不会详细介绍二叉树理论的详细细节，因为这些东西，Per Nilsson 已经在他的“二叉树”中讨论过了，你可以在如下地址here找到详细的细节。
对半查找树对于找到在一个列表中很少变化的项来说是很有用的。添加和删除操作的开销是很大的，只主要是因为对半查找树的平衡性所决定的。
我们可以这样说这个类是在同一主题上的一个不同的执行方式。

执行细节

创建这棵树

要创建二叉树，可以简单的创建一个CSimpleBinaryTree 对象并初始化。

#define MAXELEMS 100CSimpleBinaryTree 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;nIndex = btree.FindItem(psObj,pFoundObject); 

FindItem() 返回两个值.如果子项存在，第一个值就是子项的索引值，如果不存在，赋值为ITEM_NOT_PRESENT value.第二个返回值是可选择的第二个参数值。如果子项被发现了，pFoundObject 将指向它在树中的对象,如果子项没有被发现，pFoundObject 赋为空;
在CSimpleBinaryTree 中有两个搜索算法.线性搜索和对半搜索.线性搜索只在树种子项数目小于指定值的时候才使用 (缺省为10),从这个点以后的各项，将使用对半搜索.这样做的原因是线性查找不要求元素进行排序并且它的运算规则相对要简单的多.因此对于小数目项来说，线性查找是理想的.
如果在树中允许复制(m_bAllowDuplicates=TRUE) ，那末平衡(所有子项排序)操作只有当在“被要求”的时候进行，而不是