树的遍历

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有节点系统地访问，即依次对树中每个节点访问一次且仅访问一次。

对于二叉树，树的3种最重要的遍历方式分别称为先序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时，若按访问节点的先后次序将节点排列起来，就可分别得到树中所有节点的先序列表、中序列表和后序列表。相应的节点次序分别称为节点的先序、中序和后序。

对于多叉树，数的遍历通常有两种：深度优先遍历、广度优先遍历。

下面以二叉树为例讲解三种遍历方法。

每棵二叉树由节点、左子树、右子树这三个基本部分组成，如果遍历了这三部分，也就遍历了整个二叉树。

先序遍历

先序遍历指先访问根，然后访问孩子的遍历方式。若二叉树为非空，则过程为：

①访问根节点。

②先序遍历左子树。

③先序遍历右子树。

中序遍历

中序遍历指先访问左（右）孩子，然后访问根，最后访问右（左）孩子的遍历方式。若二叉树为非空，则过程为：

①按中序遍历左子树。

②访问根节点。

③按中序遍历右子树。

后序遍历

后序遍历指先访问孩子，然后访问根的遍历方式。若二叉树为非空，则过程为：

①按后序遍历左子树。

②按后序遍历右子树。

③访问根节点。

如图1-23的二叉树所示，D为二叉树中某一节点，L、R分别为节点D的左、右子树，则其遍历方式有6种：

图1-23　二叉树示例

例如，以先左后右的方式用三种遍历方法对图1-24中的二叉树进行遍历。

图1-24　二叉树示例

用先序遍历的方式，得到结果为ABDECF。

用中序遍历的方式，得到结果为DBEACF。

用后序遍历的方式，得到结果为DEBFCA。