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

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

excelperfect

在上一篇文章《基础扩展| 22. 遍历二叉树—前序遍历算法的VBA代码解析》中，我们给出了前序遍历二叉树算法的VBA代码，并详细解析了代码的运行过程。本文主要详细讲解遍历二叉树的中序遍历算法的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 InOrder(i As Integer)

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

InOrder btTree.Node(i).LeftChild

Debug.Print btTree.Node(i).Value

InOrder btTree.Node(i).RightChild

End If

End Sub

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

Sub testInOrder()

Call InOrder(btTree.Root)

End Sub

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

1.代码将btTree.Root（根结点）的值（编号1）传递给InOrder过程，由于根结点不为空，因此执行InOrder btTree.Node(i).LeftChild语句，访问其左结点B，由于其不为空，继续调用InOrder btTree.Node(i).LeftChild语句，访问结点B的左结点D，由于其不为空，继续调用InOrder btTree.Node(i).LeftChild，访问结点D的左结点H，由于其不为空，继续调用InOrder btTree.Node(i).LeftChild，访问结点H的左结点，由于H没有左结点，其值为空，因此过程返回。打印结点H，如下图2所示。

图2

2.接着执行语句InOrder btTree.Node(i).RightChild，访问结点H的右子树，因为其结点值为空，过程返回。打印结点H的过程执行完毕。返回到执行结点D的过程，执行Debug.Print btTree.Node(i).Value语句，打印结点数据D，如下图3所示。

图3

3.执行语句InOrder btTree.Node(i).RightChild，访问结点D的右子树结点I，因为其结点值不为空，执行InOrder btTree.Node(i).LeftChild语句，结点I无左子树，过程返回，执行Debug.Print btTree.Node(i).Value语句，打印结点数据I，如下图4所示。

图4

4.执行语句InOrder btTree.Node(i).RightChild，访问结点I的右子树，结点I无右子树，过程返回。打印结点I的过程执行完毕，返回至结点D。打印结点D的过程执行完毕，返回结点B。执行Debug.Print btTree.Node(i).Value语句，打印结点数据B，如下图5所示。

图5

5.执行语句InOrder btTree.Node(i).RightChild，访问结点B的右子树，此时其结点值不为空（即为结点E），接着调用InOrder btTree.Node(i).LeftChild语句，访问结点E的左子树，其值不为空（即为结点J），再次调用InOrder btTree.Node(i).LeftChild语句，访问结点J的左子树，其值为空，过程返回。执行Debug.Print btTree.Node(i).Value语句，打印结点数据J，如下图6所示。

图6

6.接着执行语句InOrder btTree.Node(i).RightChild，访问结点J的右子树，为空，过程返回，打印结点J的过程执行完毕。过程返回至结点E，执行Debug.Print btTree.Node(i).Value语句，打印结点数据E，如下图7所示。

图7

7. 执行语句InOrder btTree.Node(i).RightChild，访问结点E的右子树，因为其结点值不为空，过程返回，打印结点E的过程执行完毕。过程返回至结点B，打印结点B的过程也执行完毕。过程返回至结点A，执行Debug.Print btTree.Node(i).Value语句，打印结点A，如下图8所示。

图8

8. 接着执行语句InOrder btTree.Node(i).RightChild，访问结点A的右子树，其结点值不为空（即为结点C），调用InOrder btTree.Node(i).LeftChild语句，访问结点C的左子树，其结点值不为空（即为结点F），接着调用InOrder btTree.Node(i).LeftChild语句，访问结点F的左子树，其结点值为空，过程返回，执行Debug.Print btTree.Node(i).Value语句，打印结点F，如下图9所示。

图9

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

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

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