基础扩展 | 22. 遍历二叉树—前序遍历算法的VBA代码解析

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

excelperfect

在上一篇文章《基础扩展| 21. 遍历二叉树》中，我们给出了遍历二叉树的三种方式：前序遍历、中序遍历、后序遍历，以及对应的规则和示意图。下面，我们给出实现这三种遍历算法的VBA代码并详细解析代码的运行过程。

本文使用的二叉树来自于：

基础扩展 | 20. 建立二叉树

中创建的二叉树，代码如下：

Const MAXSIZE = 100

Type BinaryTreeNode

Value As String

LeftChild As Integer

RightChild As Integer

End Type

Type BinaryTree

Node(MAXSIZE) As BinaryTreeNode

Root As Integer

End Type

Public btTree As BinaryTree

Sub CreatBinaryTree()

Dim arr As Variant

Dim i As Long

arr = Array("","A", "B", "C", "D", "E","F", "G", "H", "I", "J","")

btTree.Root = 1

For i = 1 To UBound(arr)

btTree.Node(i).Value= arr(i)

Next i

For i = 1 To UBound(arr)

IfbtTree.Node(i).Value <> "" Then

If btTree.Node(2* i).Value <> "" Then

btTree.Node(i).LeftChild = 2 * i

End If

If btTree.Node(2* i + 1).Value <> "" Then

btTree.Node(i).RightChild = 2 * i + 1

End If

End If

Next i

End Sub

创建的二叉树如下图1所示。

图1

本文实现遍历的算法都采用了递归方式，非常简洁明了。对照代码的运行，仔细体会，不仅有助于理解这些算法，而且有助于加深对递归原理的理解。

前序遍历算法

前序遍历算法的代码如下：

Sub PreOrder(i As Integer)

If btTree.Node(i).Value<> "" Then

Debug.Print btTree.Node(i).Value

PreOrder btTree.Node(i).LeftChild

PreOrder btTree.Node(i).RightChild

End If

End Sub

使用下面的测试代码来调用PreOrder过程：

Sub testPreOrder()

Call PreOrder(btTree.Root)

End Sub

下面来详细看看程序是怎么运行的。

1.代码将btTree.Root（根结点）的值（编号1）传递给PreOrder过程，由于根结点不为空，因此执行Debug.Print btTree.Node(i).Value语句，打印结点数据A，如下图2所示。

图2

2.接着执行语句PreOrder btTree.Node(i).LeftChild，访问结点A的左子树，因为其结点值不为空，执行Debug.Print btTree.Node(i).Value语句，打印结点数据B，如下图3所示。

图3

3.再次执行语句PreOrder btTree.Node(i).LeftChild，访问结点B的左子树，因为其结点值不为空，执行Debug.Print btTree.Node(i).Value语句，打印结点数据D，如下图4所示。

图4

4.再次执行语句PreOrder btTree.Node(i).LeftChild，访问结点D的左子树，因为其结点值不为空，执行Debug.Print btTree.Node(i).Value语句，打印结点数据H，如下图5所示。

图5

5.再次执行语句PreOrder btTree.Node(i).LeftChild，访问结点H的左子树，此时其结点值为空，过程返回；接着调用PreOrder btTree.Node(i).RightChild语句，访问结点H的右子树，其值也为空，过程返回。该层递归调用过程执行完毕，返回到上一级递归调用过程，即调用结点D的过程。此时，递归调用执行PreOrder btTree.Node(i).RightChild语句，访问结点D的右子树，打印结点数据I，如下图6所示。

图6

6.再次执行语句PreOrder btTree.Node(i).LeftChild，访问结点I的左子树，此时其结点值为空，过程返回；接着调用PreOrder btTree.Node(i).RightChild语句，访问结点I的右子树，其值也为空，过程返回。该层递归调用过程执行完毕，返回到上一级递归调用过程，即打印结点D时的过程，该过程也执行完毕。也返回到上一级递归过程，即打印节点B的过程，递归调用执行PreOrder btTree.Node(i).RightChild语句，访问结点B的右子树，打印结点数据E，如下图7所示。

图7

7. 再次执行语句PreOrder btTree.Node(i).LeftChild，访问结点E的左子树，因为其结点值不为空，执行Debug.Print btTree.Node(i).Value语句，打印结点数据J，如下图8所示。

图8

8. 再次执行语句PreOrder btTree.Node(i).LeftChild，访问结点J的左子树，此时其结点值为空，过程返回；接着调用PreOrder btTree.Node(i).RightChild语句，访问结点J的右子树，其值也为空，过程返回。该层递归调用过程执行完毕，返回到上一级递归调用过程，即打印结点E时的过程，递归调用执行PreOrder btTree.Node(i).RightChild语句，访问结点E的右子树，其结点值为空，过程返回。此时该层递归过程执行完毕，返回到上一级递归调用过程，即打印结点B时的过程，也执行完毕。再向上一层返回到打印节点A时的过程，调用PreOrder btTree.Node(i).RightChild语句，访问结点A的右子树，因为其结点值不为空，执行Debug.Print btTree.Node(i).Value语句，打印结点数据C，如下图9所示。

图9

9.类似前面的递归调用，依次继续打印结点F、G。

综上，前序遍历这棵二叉树的结点顺序是：ABDHIEJCFG。

本文所讲解的前序遍历原理也可以参考《大话数据结构》的P178-P181。