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

excelperfect

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

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

BinaryTreeItem类

Public Value As Variant

Public LeftChild As BinaryTreeItem

Public RightChild As BinaryTreeItem

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()

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

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

143 篇文章27 人订阅

0 条评论