VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 2282|回复: 4

[原创] 发一个vb6的二叉树排序

[复制链接]
发表于 2015-4-14 22:59:38 | 显示全部楼层 |阅读模式
本帖最后由 zzyong00 于 2015-4-14 23:01 编辑

vb6没有显式指针,用二叉树排序,需要用到类,可能速度上并不快,但是终究是一种方法。
不过,对于要排序的数据是一些对象(比如Autocad二次开发时)时,我觉得用这个排序可能有优势!
源码:

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
发表于 2015-4-16 16:59:57 | 显示全部楼层
我仅仅是点评一下...

二叉树排序的优势在于:
1.查找的速度和数组2分一样快
2.插入/删除的速度比数组快很多

楼主这个代码由于没有插入/删除后的树高调整
所以实际使用价值就降低了
对于某些特定数据,这个树会退化得和数组一样(比如输入排好序的数据)

另外是一些小问题...
含指针的数据结构,通常为了代码的统一性,NULL(VB里是NOTHING)的地方会采用哑元替代

点评

抛出来就是为了大家完善,插入和删除,我再补一下吧  发表于 2015-4-16 22:54
欢迎可爱的版主回归。期待您的精品帖~~  发表于 2015-4-16 20:37
回复 支持 反对

使用道具 举报

 楼主| 发表于 2015-4-16 22:55:28 | 显示全部楼层
  1. Public Sub Add(ByVal strValue As String)
  2.     ''按已排好序的情况考虑
  3.     Dim pNode As clsBiTreeNode, tNode As clsBiTreeNode, qNode As clsBiTreeNode
  4.     'pNode 遍历树的所有节点用
  5.     'tNode 保存要添加孩子的父节点
  6.     'qNode 要添加的作为孩子的节点
  7.     Dim LR_flag As Long '判别是左还是右节点
  8.     Set qNode = New clsBiTreeNode
  9.     qNode.NodeValue = strValue
  10.     '        qNode.LeftNode = Nothing
  11.     '        qNode.RightNode = Nothing
  12.     Set pNode = mRoot
  13.     Do While Not (pNode Is Nothing)
  14.         Set tNode = pNode
  15.         If Val(strValue) < Val(pNode.NodeValue) Then
  16.             LR_flag = 1
  17.             Set pNode = pNode.LeftNode
  18.         ElseIf Val(strValue) > Val(pNode.NodeValue) Then
  19.             LR_flag = 2
  20.             Set pNode = pNode.RightNode
  21.         ElseIf Val(strValue) = Val(pNode.NodeValue) Then
  22.             Debug.Print "已存该值的节点:"; strValue
  23.             Exit Sub
  24.         End If
  25.     Loop
  26.     If LR_flag = 1 Then
  27.         tNode.LeftNode = qNode
  28.     ElseIf LR_flag = 2 Then
  29.         tNode.RightNode = qNode
  30.     End If
  31.    
  32. End Sub
  33. Public Sub Del(ByVal strValue As String)
  34.     ''按已排好序的情况考虑
  35.     Dim pNode As clsBiTreeNode, tNode As clsBiTreeNode
  36.     'pNode 遍历树的所有节点用,和保存要删除的节点
  37.     'tNode 保存要删除节点的父节点
  38.     Dim LR_flag As Long '判别是左还是右节点,1左 2右
  39.     Dim Root_flag As Long '判别要删除的是根节点 1是,0不是
  40.    
  41.     Set pNode = mRoot
  42.     Set tNode = pNode
  43.    
  44.     Do While Not (pNode Is Nothing)
  45.         If Val(strValue) < Val(pNode.NodeValue) Then
  46.             Set tNode = pNode
  47.             
  48.             LR_flag = 1
  49.             Set pNode = pNode.LeftNode
  50.         ElseIf Val(strValue) > Val(pNode.NodeValue) Then
  51.             Set tNode = pNode
  52.             
  53.             LR_flag = 2
  54.             Set pNode = pNode.RightNode
  55.         ElseIf Val(strValue) = Val(pNode.NodeValue) Then
  56.             'Debug.Print "正要删除它"
  57.             Exit Do
  58.         End If
  59.     Loop
  60.     '没有要删的节点
  61.     If pNode Is Nothing Then
  62.         Debug.Print "没有要删的节点:"; strValue
  63.         Exit Sub
  64.     End If
  65.    
  66.     If pNode Is mRoot Then '如果删除的是根节点
  67.         Root_flag = 1
  68.         'else  删除的是叶子节点
  69.     End If
  70.     If pNode.LeftNode Is Nothing And pNode.RightNode Is Nothing Then
  71.         If Root_flag Then '根节点
  72.             Set mRoot = Nothing
  73.             Exit Sub
  74.         End If
  75.         If LR_flag = 1 Then
  76.             tNode.LeftNode = Nothing
  77.         ElseIf LR_flag = 2 Then
  78.             tNode.RightNode = Nothing
  79.         End If
  80.         Set pNode = Nothing
  81.         Exit Sub
  82.         
  83.     End If
  84.    
  85.     '只有右节点
  86.     If pNode.LeftNode Is Nothing And (Not pNode.RightNode Is Nothing) Then
  87.         If Root_flag Then '根节点
  88.             Set mRoot = pNode.RightNode
  89.             Set pNode = Nothing
  90.             Exit Sub
  91.         End If
  92.         If LR_flag = 1 Then
  93.             tNode.LeftNode = pNode.RightNode
  94.         ElseIf LR_flag = 2 Then
  95.             tNode.RightNode = pNode.RightNode
  96.         End If
  97.         Set pNode = Nothing
  98.         Exit Sub
  99.     End If
  100.     '只有左节点
  101.     If (Not pNode.LeftNode Is Nothing) And pNode.RightNode Is Nothing Then
  102.         If Root_flag Then '根节点
  103.             Set mRoot = pNode.LeftNode
  104.             Set pNode = Nothing
  105.             Exit Sub
  106.         End If
  107.         If LR_flag = 1 Then
  108.             tNode.LeftNode = pNode.LeftNode
  109.         ElseIf LR_flag = 2 Then
  110.             tNode.RightNode = pNode.LeftNode
  111.         End If
  112.         Set pNode = Nothing
  113.         Exit Sub
  114.     End If
  115.     '两边都有
  116.     '  If (Not pNode.LeftNode Is Nothing) And (Not pNode.RightNode Is Nothing) Then
  117.     If LR_flag = 2 And Root_flag = 0 Then
  118.         tNode.RightNode = pNode.LeftNode
  119.     ElseIf Root_flag = 0 Then
  120.         tNode.LeftNode = pNode.LeftNode
  121.     End If
  122.     Dim NextNode As clsBiTreeNode
  123.     Set NextNode = pNode.LeftNode
  124.     Do While Not NextNode.RightNode Is Nothing
  125.         Set NextNode = NextNode.RightNode
  126.     Loop
  127.     NextNode.RightNode = pNode.RightNode
  128.    
  129.     If Root_flag Then '根节点
  130.         Set mRoot = pNode.LeftNode
  131.         Set pNode = Nothing
  132.         Exit Sub
  133.     End If
  134.     '  End If
  135.    
  136. End Sub
复制代码
回复 支持 反对

使用道具 举报

发表于 2015-4-17 00:13:30 | 显示全部楼层
我解释一下树高调整的概念
N个结点的2叉树,理想的高度是logN(以2为底取对数)
这个时候平均的数高最小,意味着你最多只需要logN次查找就能找到想要的元素
如果只是按大的放右边,小的放左边这样插入元素,树的高度将不可控
查找的效率就会降低
比如说按顺序插入排好序的N个结点,树高直接变成N

所以发明了将树高控制在logN级别的算法
常见的有平衡树,红黑树,等等
楼主真的想写的话,我推荐个代码比较短的,用VB也比较容易实现
节点大小平衡树 Size Balanced Tree
这个只有左旋和右旋两种调整,比较好写

点评

我确实测试过release模式下速度只有stl的map的一半,而map里用的是红黑树...  发表于 2015-4-21 08:55
这个事儿大了,又汇泄露country机mi了  发表于 2015-4-20 22:37
wiki了下确实和Weight-balanced tree是一个东西,为什么这么长时间还没被揭穿...  发表于 2015-4-20 17:56
这个在各种文章里可是被捧上天了,其实除了容易写也没别的什么优势,吹速度怎么怎么快,和treap,splay各种比,不过在红黑树面前直接翔了 =.=  发表于 2015-4-20 17:48
SB树老外叫做Weight Balanced Tree 而且上世纪80年代就有了,难道中国人又搞了所谓的自主知识产权?  发表于 2015-4-20 13:54
回复 支持 反对

使用道具 举报

 楼主| 发表于 2015-4-18 23:04:39 | 显示全部楼层
http://www.nocow.cn/index.php/Size_Balanced_Tree
找到了,哪个谐音
下面还有c++源码,转成vb的应该不难
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2022-7-5 11:27

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表