简单二叉树类

本文由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;
nIndex = btree.FindItem(psObj,pFoundObject);FindItem() 返回两个值.如果子项存在，第一个值就是子项的索引值，如果不存在，赋值为ITEM_NOT_PRESENT value.第二个返回值是可选择的第二个参数值。如果子项被发现了，pFoundObject 将指向它在树中的对象,如果子项没有被发现，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).

重设大小的操作代价昂贵，因此应该尽可能的避免.上面的例子中给出了增长/消减触发器的缺省值和增长/消减的对应值。

公共方法概述

本文配套源码

• 没有相关文章