|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 树和二叉树 >
|
被考次数：1次
被考频率：低频率
总体答错率：31%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
相关知识点：3个
|
|
|
|
|
所谓树的遍历，指按某种规定的顺序访问树中的每一个结点一次，且每个结点仅被访问一次。根据根结点的访问位置不同，树的遍历可以分为前序遍历和后序遍历；又由于树具有层次性，遍历树中结点时可以按层次自上而下访问每个结点，因此树的遍历方式分为以下三种：
|
|
|
|
|
|
首先访问根结点，再依次按前序遍历的方式访问根结点的每一棵子树。
|
|
|
|
|
|
首先按后序遍历的方式访问根结点的每一棵子树，然后再访问根结点。
|
|
|
|
|
|
首先访问第一层上的根结点，然后从左到右依次访问第二层上的所有结点，再以同样的方式访问第三层上的所有结点……最后访问树中最低一层的所有结点。
|
|
|
|
如下图所示的树对其进行三种遍历的结果分别为：前序遍历的结果——ABCEFHIGD；后序遍历的结果——BEHIFGCDA；层次遍历的结果——ABCDEFGHI。
|
|
|
|
|
|
|
|
显然，树的前序遍历和后序遍历的定义具有递归性，因此采用递归方式实现树的前、后序遍历算法十分方便，只要按照其各自规定的顺序，访问根结点时就输出根结点的值，访问子树时进行递归调用即可。以下以指针方式的孩子表示法作为树的存储结构，分别给出树的前序遍历和后序遍历算法的实现。
|
|
|
|
|
|
|
|
|
|
|
