简单二叉树类

就爱国舰

就爱国舰

2016-01-29 12:15

简单二叉树类,简单二叉树类

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

(本文来源于图老师网站,更多请访问http://m.tulaoshi.com/cyuyanjiaocheng/)

下载本文示例源代码



本文由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) ,那末平衡(所有子项排序)操作只有当在“被要求”的时候进行,而不是
展开更多 50%)
分享

猜你喜欢

简单二叉树类

C语言教程 C语言函数
简单二叉树类

创建二叉树 二叉树如何删除节点操作教程

编程语言 网络编程
创建二叉树 二叉树如何删除节点操作教程

s8lol主宰符文怎么配

英雄联盟 网络游戏
s8lol主宰符文怎么配

二叉树实现源代码

编程语言 网络编程
二叉树实现源代码

二叉树的几种运算方法

编程语言 网络编程
二叉树的几种运算方法

lol偷钱流符文搭配推荐

英雄联盟 网络游戏
lol偷钱流符文搭配推荐

c++二叉树的几种遍历算法

编程语言 网络编程
c++二叉树的几种遍历算法

C++数据结构学习:二叉树(1)

编程语言 网络编程
C++数据结构学习:二叉树(1)

lolAD刺客新符文搭配推荐

英雄联盟
lolAD刺客新符文搭配推荐

PSV《讨鬼传 极》瞬间伤害加成实战排行一览

PSV《讨鬼传 极》瞬间伤害加成实战排行一览

九宫问题(八数码)求解过程动态演示

九宫问题(八数码)求解过程动态演示
下拉加载更多内容 ↓