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

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

excelperfect

前面的两篇文章《基础扩展| 22. 遍历二叉树—前序遍历算法的VBA代码解析》和《基础扩展| 23. 遍历二叉树—中序遍历算法的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 PostOrder(i As Integer)

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

PostOrder btTree.Node(i).LeftChild

PostOrder btTree.Node(i).RightChild

Debug.Print btTree.Node(i).Value

End If

End Sub

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

Sub testPostOrder()

Call PostOrder(btTree.Root)

End Sub

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

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

图2

2.访问结点H的过程执行完毕，返回到访问结点D的过程，接着执行语句PostOrder btTree.Node(i).RightChild，访问结点D的右子树结点I，递归调用PostOrder过程。由于结点I不为空，调用PostOrder btTree.Node(i).LeftChild语句，访问结点I的左子树结点，其值为空，过程返回至结点I，接着调用PostOrder btTree.Node(i).RightChild语句，访问结点I的右子树结点，其值为空，过程返回至结点I，接着调用Debug.Print btTree.Node(i).Value语句，打印结点I，如下图3所示。

图3

3.访问结点I的过程执行完毕，返回至访问结点D的过程，执行语句Debug.Print btTree.Node(i).Value，打印结点D，如下图4所示。

图4

4.访问结点D的过程执行完毕，返回至访问结点B的过程，执行语句PostOrder btTree.Node(i).RightChild，访问结点B的右子树结点E，递归调用PostOrder过程，由于结点E不为空，访问结点E的左子树结点J，再次递归调用PostOrder过程，访问结点J的左子树结点，其值为空，过程返回，访问结点J的右子树结点，其值为空，过程返回。执行Debug.Print btTree.Node(i).Value语句，打印结点J，如下图5所示。

图5

5.访问结点D的过程执行完毕，返回至访问结点E的过程，执行语句PostOrder btTree.Node(i).RightChild，访问结点E的右子树，其值为空，过程返回，执行Debug.Print btTree.Node(i).Value语句，打印结点E，如下图6所示。

图6

6.访问结点E的过程执行完毕，返回至访问结点B的过程，执行语句Debug.Print btTree.Node(i).Value，打印结点数据B，如下图7所示。

图7

7.访问结点B的过程执行完毕，返回至访问结点A的过程，执行语句PostOrder btTree.Node(i).RightChild，访问结点A的右子树结点C，递归调用PostOrder过程，因为其结点值不为空，调用PostOrder btTree.Node(i).LeftChild语句，访问结点C的左子树结点F，再次调用PostOrder过程，因为其结点值不为空，调用PostOrder btTree.Node(i).LeftChild语句，访问结点F的左结点，因其值为空，过程返回，接着调用PostOrder btTree.Node(i).RightChild语句，访问结点F的右子树结点，其值为空，过程返回至结点F，接着调用Debug.Print btTree.Node(i).Value语句，打印结点F，如下图8所示。

图8

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

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

本文所讲解的中序遍历原理也可以参考《大话数据结构》的P184。重要的事情讲三遍，相信大家依次阅读完这三篇文章后，对遍历二叉树的原理以及递归原理会有更深入的理解了。