基础扩展 | 26. 使用VBA实现二叉排序树

学习Excel技术，关注微信公众号：

excelperfect

经过前面一系列关于二叉树的知识的学习，我们对这种数据结构已经有了一定的基础。下面，我们来看如何使用VBA实现二叉排序树。

下图1所示就是一棵二叉排序树。

图1

根据程杰著的《大话数据结构》P315-P316的定义，二叉排序树的定义如下：

“二叉排序树（Binary Sort Tree），又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：

• 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值。
• 若它的右子树不为空，则右子树上所有结点的值均大小它的根结点的值。
• 它的左、右子树也分别为二叉排序树。”

下面我们以数组{62,88,58,47,35,73,51,99,37,93}为示例数据，使用VBA代码将其构造成一棵上图1所示的二叉排序树。

BinaryTreeItem类

在VBE中插入一个类模块，并将其命名为BinaryTreeItem，输入代码：

Public Value As Variant

Public LeftChild As BinaryTreeItem

Public RightChild As BinaryTreeItem

这定义了二叉树结点的数据结构。

BinarySortTree类

在VBE中插入一个类模块，并将其命名为BinarySortTree，输入代码：

Public HeadNode As BinaryTreeItem

'插入结点

Sub InsertNode(bstTree As BinaryTreeItem, newNode AsBinaryTreeItem)

Dim pTree As BinaryTreeItem

Dim qTree As BinaryTreeItem

Set qTree = Nothing

If bstTree Is Nothing Then

Set bstTree = newNode

Exit Sub

End If

Set pTree = bstTree

Do While (Not pTree Is Nothing)

If pTree.Value<> newNode.Value Then

Set qTree = pTree

If pTree.Value> newNode.Value Then

Set pTree =pTree.LeftChild

Else

Set pTree =pTree.RightChild

End If

End If

Loop

If pTree Is Nothing Then

If qTree.Value >newNode.Value Then

Set qTree.LeftChild = newNode

Else

Set qTree.RightChild = newNode

End If

End If

End Sub

'创建排序二叉树

Function CreateBinarySortTree(arr() As BinaryTreeItem) As BinaryTreeItem

Dim bst As BinaryTreeItem, pst As BinaryTreeItem

Dim i As Integer

Dim length As Integer

length = UBound(arr) -LBound(arr) + 1

Set bst = Nothing

For i = 0 To length - 1

Set pst = New BinaryTreeItem

pst.Value =arr(i).Value

Set pst.LeftChild =Nothing

Set pst.RightChild =Nothing

Call InsertNode(bst, pst)

Next i

Set HeadNode = bst

Set CreateBinarySortTree= bst

End Function

'遍历二叉树

Public Sub WalkInorder()

Call InOrder(HeadNode)

End Sub

'中序遍历

Private Sub InOrder(bstNode As BinaryTreeItem)

If Not bstNode Is NothingThen

Call InOrder(bstNode.LeftChild)

Debug.Print bstNode.Value

Call InOrder(bstNode.RightChild)

End If

End Sub

其中，InsertNode过程用来在树中插入结点，如果是空树，则将传入的第一个结点作为树的根结点，然后进行比较，比根结点小的数据往左子树插入，比根结点大的数据往右子树插入。

CreatBinarySortTree函数用来接收用来创建二叉树的结点数据并调用InsertNode过程来在相应位置插入结点，最后返回二叉树结果。

WalkInorder过程调用Inorder过程来输入遍历所创建的二叉排序树的结点数值，得到的将是一个有序序列。在本示例中为{35,37,47,51,58,62,73,88,93,99}。

测试

下在的代码提供创建二叉排序树的数据，并调用类模块来创建二叉排序树，最后输出结果。

Sub test()

Dim myTree() As New BinaryTreeItem

Dim myArr() As Variant

Dim bstTree As BinarySortTree

Dim i As Integer

'初始化结点数据

myArr = Array(62, 88, 58,47, 35, 73, 51, 99, 37, 93)

ReDim myTree(UBound(myArr)- LBound(myArr))

For i = LBound(myArr) To UBound(myArr)

myTree(i).Value =myArr(i)

Set myTree(i).LeftChild = Nothing

Set myTree(i).RightChild = Nothing

Next i

Set bstTree = New BinarySortTree

'创建排序二叉树

bstTree.CreateBinarySortTree myTree

'输出结果

bstTree.WalkInorder

End Sub

运行代码后的结果如下图2所示。

图2

二叉排序树的实现原理详见程杰著的《大话数据结构》P316-P328，有兴趣的朋友可以对照研读。

上文中BinarySortTree类模块代码的图片版如下：