树与森林的遍历

树的遍历

与二叉树类似，树的遍历有先根遍历和后根遍历以及层次遍历等。在这些遍历中，我们主要考虑孩子兄弟表示法的存储方式，原因是其他几种表示方式可以轻易地通过遍历数组来遍历。

由于一个节点有不止两个孩子，因此中序遍历没有太大价值不再考虑。

树的先根遍历

先访问根结点，再递归遍历第一个孩子子树，最后递归遍历下一个兄弟子树。

void preordertre(CSnode *root) /* root 根结点 */
{
    if (root ![[= NULL) {
        visit(root->data);                     /* 访问根结点 */
        preordertre(root->firstchild);
        preordertre(root->nextsibling);
    }
}

树的后根遍历

先递归遍历第一个孩子子树，再递归遍历下一个兄弟子树，最后访问根结点。

void postordertre(CSnode *root) /* root 根结点 */
{
    if (root != NULL) {
        postordertre(root->firstchild);
        postordertre(root->nextsibling);
        visit(root->data);
    }
}

树的层次遍历

算法运用队列做辅助存储结构，其步骤为：

首先将树根入队列。
出队一个结点便立即访问之，然后将它非空的第一个孩子结点进队，同时将该孩子结点的所有非空兄弟结点逐一进队。
重复步骤 2，这样便实现了树按层遍历。

森林的遍历

对于森林的结构，可以将其分解为森林中第一棵树的根节点、森林中第一棵树的子树组成的森林、森林中除了第一棵树以外其他的树组成的森林，因此可以进行递归遍历。

森林的先序遍历

若森林不空，则：

访问森林中第一棵树的根结点。
先序遍历森林中第一棵树的子树森林。
先序遍历森林中（除第一棵树之外）其余树构成的森林。

即依次从左至右对森林中的每一棵树进行先根遍历。

森林的后序遍历

若森林不空，则：

后序遍历森林中第一棵树的子树森林。
访问森林中第一棵树的根结点。
后序遍历森林中（除第一棵树之外）其余树构成的森林。

即依次从左至右对森林中的每一棵树进行后根遍历。

森林深度求解

想要求森林深度，可以利用遍历时对森林采取的划分结构，即节点、子树森林、其他树森林的形式进行递归运算，具体如下：

// T 指向森林中的第一棵树（即整个森林的代表）
function ForestDepth(T: CSTree): int
    if T == null then
        return 0
    else
        depthOfFirstTree = 1 + ForestDepth(T.firstChild)     // 第一棵树的深度
        depthOfRestForest = ForestDepth(T.nextSibling)        // 其他树构成的森林深度
        return max(depthOfFirstTree, depthOfRestForest)