基础扩展 | 21. 遍历二叉树

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

excelperfect

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。下面，以图1所示的二叉树为例，讲解二叉树的前序遍历、中序遍历、后序遍历。

图1

前序遍历

规则：

• 若二叉树为空，则返回空
• 否则，先访问根结点
• 然后遍历左子树
• 再遍历右子树

按照上面的规则，对图1所示的二叉树进行前序遍历，其遍历顺序为：ABDHIEJCFG。

图2

中序遍历

规则：

• 若二叉树为空，则返回空
• 否则，从根结点开始，遍历结点的左子树
• 然后，回到根结点，遍历结点的右子树

按照上面的规则，对图1所示的二叉树进行中序遍历，其遍历顺序为：HDIBJEAFCG。

图3

后序遍历

规则：

• 若二叉树为空，则返回空
• 否则，从左至右先叶子节点后结点的顺序遍历左右子树
• 最后，遍历根结点

按照上面的规则，对图1所示的二叉树进行后序遍历，其遍历顺序为：HIDJEBFGCA。

图4

好了，对照规则和示意图，好好体会一下三种遍历方式的顺序。后续文章，我们将给出实现三种遍历的VBA代码。