Excel VBA的非常基础的递归二叉搜索树

• 下载源代码 - 36.8 KB

引言

我最近问自己：“VBA中有二叉搜索树吗？” 我已经在C#和C++等其他语言中使用过它们很多次了，而且它们效果很好，那么为什么我在网上找不到很多关于VBA的例子呢？ 我做了一些更多的在线研究，很快找到了几个.NET的例子，以及几种将VBA以外的代码调用到我的宏中来构建二叉搜索树（BST）的方法，但我想使用原生的VBA。在我研究的过程中，我在 Implementing a Binary Tree 的一个文档中找到了一个仅使用VBA的BST示例，经过一些修改后，我终于让它能工作了。 似乎很多程序员宁愿避开VBA，而我认为这是一项挑战，尽管它带来的回报微乎其微。

背景

根据 此链接， BST 的定义如下： “二叉搜索树是一种数据结构，可以快速地维护一个排序的数字列表。

• 之所以称为二叉树，是因为每个节点最多有两个子节点。
• 之所以称为搜索树，是因为它可以用于在 O(log(n)) 时间内搜索数字是否存在。

使二叉搜索树与普通二叉树区分开来的属性是 [原文如此]

1. 左子树的所有节点都小于根节点
2. 右子树的所有节点都大于根节点
3. 每个节点的两个子树也都是BST，即它们也具有上述两个属性。”

这只是BST的一种定义。我在研究中找到了许多定义，并决定采用这个基本定义，外加一个额外的条件：

      4.BST 中不应有重复项。

为了解决这个问题，我计算了重复项，但另一种解决方案是跳过它们。我选择计算它们，因为在BST的应用中，如果它们的键值不同（例如在字典应用程序中），我可能需要将重复项推入链表。

这张来自 此链接 的二叉树图片有助于说明这种数据结构。

在这里，我们看到根节点的值是9，所有左子树都小于前面的节点，而所有右子树都大于前面的节点。请注意，为了使此图片成为真正的BST，左侧的任何节点的值都不能高于前面的节点，反之亦然。现在，将图中的数字5替换为数字2，它就不再是BST了，即使2小于6。

Using the Code

这是一个简单的非平衡BST，它由两个类模块（TreeNode和BinarySearchTree）以及一个Random_Main测试模块实现，该模块包含运行所有BST函数的宏。该示例使用10个随机整数填充BST，并完成几个函数：

• Insert
• 中序遍历
• 前序遍历
• 后序遍历
• 搜索（删除前后均可）
• 删除
• 最小值
• 最大值
• 根节点值（删除前后均可）

Random_Main 模块

完整的示例可供下载，所有模块都包含每个步骤的注释。 这是“Random_MAIN”子程序“Random_Main”模块的一部分。此子程序自动选择随机数，驱动所有BST属性，跟踪TreeNode，并将结果打印到Excel工作簿主页（BST）以及立即监视窗口。打开可下载示例中的代码面板，并将bstSize更改为代表您想要自动插入的BST值的数量。upperRnd是要输入的最高值，而lowerRnd是要输入的最低值，这两个值都可以更改。这只是为了说明TreeNode和BinarySearchTree类如何工作，并且可以根据需要进行修改，或者由架构师根据自己的需求进行创建。

' always force declaration of variables
Option Explicit
' change bstSize as suited for more or less vars in bst and upper or lower to extend value range in BST
Private Const bstSize As Integer = 10: Private Const upperRnd As Integer = 10, lowerRnd As Integer = 1
' declare WB, WS, and outPut as public to use in updating functions
Public WB As Workbook: Public WS As Worksheet: Public outPut As Collection
' this is our testing module to test the random bst
Public Sub Random_MAIN()
    ' turn off screen updating
    Application.ScreenUpdating = False
    ' local variables to use and declare a new BST and root
    Dim loopCount, rndNumber As Integer: Dim BST As New BinarySearchTree: Dim root As TreeNode
    ' set workbook, worksheet, and collection
    Set WB = ThisWorkbook: Set WS = WB.Sheets("BST"): Set outPut = New Collection
    ' loop x times and add random number
    For loopCount = 1 To bstSize
        rndNumber = rndOmizer: Set root = BST.insert(root, rndNumber): outPut.add (rndNumber)
    Next loopCount
    ' print out the input results and update BST sheet
    updateBSTSheet ("A"):  myPrint ("Order in which values are inserted."): myPrint ("")

TreeNode 类模块

这是“TreeNode”类模块，其中包含一个用于在TreeNode中存储值的变量（Value），一个用于计算重复项的变量（ValueCount），以及指向左子节点和右子节点的链接（LeftChild 和RightChild）。所有内容都声明为Public，以便在类外部轻松访问。

Option Explicit
' stores the count of how many of each value is present
Public ValueCount As Long
' stores the actual value (integer in this case)
Public Value As Variant
' stores the pointer to the left child node
Public LeftChild As TreeNode
' stores the pointer to the right child node
Public RightChild As TreeNode

BinarySearchTree 类模块

这是“BinarySearchTree”类模块的“insert”函数。此函数在root TreeNode尚不存在时创建它，在现有值上添加ValueCount而不是允许重复项，并递归地向下到第一个左侧或右侧的NothingTreeNode以添加一个新节点。TreeNode 然后返回一个TreeNode。

' public function to recursively insert value with no duplicates
Public Function insert(TN As TreeNode, valToInsert As Variant) As TreeNode
    ' create node if it doesn't exist
    If TN Is Nothing Then
        Set TN = New TreeNode
        TN.Value = valToInsert
        TN.ValueCount = 1
    ' count duplicates without expanding tree
    ElseIf TN.Value = valToInsert Then
        TN.ValueCount = TN.ValueCount + 1
    ' recursively call until empty node is found
    Else
        ' go left or right based on value and recursively call
        If valToInsert < TN.Value Then
            Set TN.LeftChild = insert(TN.LeftChild, valToInsert)
        ElseIf valToInsert > TN.Value Then
            Set TN.RightChild = insert(TN.RightChild, valToInsert)
        End If
    End If
    ' set the function to the node continually
    Set insert = TN
End Function

这是“BinarySearchTree”类模块的“delete”函数。此函数根据Value递归地删除一个TreeNode，无论该TreeNode是叶节点、没有子节点，还是一个binary tree，然后返回一个TreeNode。

' public function to delete the value (node)
Public Function delete(TN As TreeNode, valToDelete As Variant) As TreeNode
    ' go left or right by value to be deleted and reccrsively call
    If valToDelete < TN.Value Then
        Set TN.LeftChild = delete(TN.LeftChild, valToDelete)
    ElseIf valToDelete > TN.Value Then
        Set TN.RightChild = delete(TN.RightChild, valToDelete)
    ' delete node if value is the same
    Else
        Dim copyNode As TreeNode
        ' node has no or only one child
        If TN.LeftChild Is Nothing Then
            Set copyNode = TN.RightChild: Set TN = Nothing: Set delete = copyNode: Exit Function
        ElseIf TN.RightChild Is Nothing Then
            Set copyNode = TN.LeftChild: Set TN = Nothing: Set delete = copyNode: Exit Function
        Else
        ' node has two children: 1st get inorder successor: 
        ' 2nd copy to this node: 3rd delete inorder successor
            Set copyNode = minValueNode(TN.RightChild): TN.Value = copyNode.Value: _
                           Set TN.RightChild = delete(TN.RightChild, copyNode.Value)
        End If
    End If
    ' set the function to the node continually
    Set delete = TN
End Function

这是“BinarySearchTree”类模块的“minValueNode”函数。此函数循环查找将被删除的具有两个子节点的TreeNode的后继TreeNode，然后返回一个TreeNode。此函数由“delete”函数调用。

' private function to find node's inorder successor
Private Function minValueNode(TN As TreeNode) As TreeNode
    ' loop down to find the leftmost leaf
    Dim tempNode As TreeNode: Set tempNode = TN
    While Not tempNode.LeftChild Is Nothing
        Set tempNode = tempNode.LeftChild
    Wend
    Set minValueNode = tempNode
End Function

这是“BinarySearchTree”类模块的“search”函数。此函数递归地查找Value，然后返回一个boolean。

' public function to search for a value
Public Function search(TN As TreeNode, valToSearch As Variant) As Boolean
    Dim searchNode As TreeNode: Set searchNode = TN
    ' loop until value is found (true) or bst ends (false)
    While Not searchNode Is Nothing
        If searchNode.Value = valToSearch Then
            search = True: Exit Function
        ElseIf valToSearch < searchNode.Value Then
            Set searchNode = searchNode.LeftChild
        Else
            Set searchNode = searchNode.RightChild
        End If
    Wend
End Function

这是“BinarySearchTree”类模块的“maxValue”函数。此函数向右循环查找最大Value，然后返回一个Variant。

' public function to get the max value from right tree recursively
Public Function maxValue(TN As TreeNode) As Variant
    Dim maxValueNode As TreeNode: Set maxValueNode = TN
    While Not maxValueNode.RightChild Is Nothing
        Set maxValueNode = maxValueNode.RightChild
    Wend
    maxValue = maxValueNode.Value
End Function

这是“BinarySearchTree”类模块的“minValue”函数。此函数向左循环查找最小Value，然后返回一个Variant。

' public function to get the min value from left tree recursively
Public Function minValue(TN As TreeNode) As Variant
    Dim minValueNode As TreeNode: Set minValueNode = TN
    While Not minValueNode.LeftChild Is Nothing
        Set minValueNode = minValueNode.LeftChild
    Wend
    minValue = minValueNode.Value
End Function

这是“BinarySearchTree”类模块的“InOrder”函数。此函数按左TreeNode、根TreeNode、右TreeNode的顺序递归遍历BST，以按从小到大的顺序显示值。返回一个Collection，但该变量也可以是Array。

' public function to display the values in order from lowest to highest (left, root, right) recursively
Public Function InOrder(TN As TreeNode, Optional myCol As Collection) As Collection
    If Not TN Is Nothing Then
        Call InOrder(TN.LeftChild, myCol)
        If myCol Is Nothing Then
            Set myCol = New Collection: myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        Else
            myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        End If
        Call InOrder(TN.RightChild, myCol)
    End If
    Set InOrder = myCol
End Function

这是“BinarySearchTree”类模块的“PreOrder”函数。此函数按根TreeNode、左TreeNode、右TreeNode的顺序递归遍历BST。这可以用于获取前缀或复制BST，但在此我将它们显示出来。 返回一个Collection，但该变量也可以是Array。

' public function to display the values from left to right (root, left, right) recursively
Public Function PreOrder(TN As TreeNode, Optional myCol As Collection) As Collection
    If Not TN Is Nothing Then
        If myCol Is Nothing Then
            Set myCol = New Collection: myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        Else
            myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        End If
        Call PreOrder(TN.LeftChild, myCol)
        Call PreOrder(TN.RightChild, myCol)
    End If
    Set PreOrder = myCol
End Function

这是“BinarySearchTree”类模块的“PostOrder”函数。 此函数按左TreeNode、右TreeNode，然后是右root TreeNode的顺序递归遍历BST。这可以用来获取后缀或删除BST，但在此我将它们显示出来。 返回一个Collection，但该变量也可以是Array。

' public function to display the values from right to left (left, right, root) recursively
Public Function PostOrder(TN As TreeNode, Optional myCol As Collection) As Collection
    If Not TN Is Nothing Then
        Call PostOrder(TN.LeftChild, myCol)
        Call PostOrder(TN.RightChild, myCol)
        If myCol Is Nothing Then
            Set myCol = New Collection: myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        Else
            myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        End If
    End If
    Set PostOrder = myCol
End Function

关注点

也许最困难的障碍是递归函数不断解除我的指针引用。在插入了几个“SET”关键字后，大功告成！它奏效了！我试图保持（O）符号的大小，但不得不增加至少一个额外的步骤。我计划将来添加一个手动BST工作簿，允许用户插入、删除和搜索值，而不是我现在的自动系统。

历史

• 2019年2月19日。V1.0.0：初始发布
• 2019年2月23日。V1.8.8：添加了search、deleted、min和max函数，并清理了所有函数。