先序遍历森林

问题描述：设计算法输出先序遍历的森林节点及其所在的层次

【算法设计思想】

1. 数据结构定义

首先，定义二叉树节点的数据结构。每个节点包含存储数据的data字段，以及指向左右子节点的指针（lChild和rChild）。这种数据结构是二叉树和森林表示的基础。

2. 先序遍历单棵树

设计一个递归函数preorderTraversal用于先序遍历单棵树。先序遍历的顺序是：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。在访问每个节点时，输出该节点的数据和层次信息。层次信息是通过递归调用时增加的层次参数level来维护的。

3. 遍历森林

森林可以视为二叉树的数组。设计一个函数preorderTraversalForest，它接受表示森林的二叉树数组和数组的大小。对于数组中的每棵树，使用preorderTraversal函数进行先序遍历，并在每棵树的遍历开始前打印一个标识该树的消息，以区分不同的树。

4. 层次信息传递

在遍历过程中，通过递归函数的参数传递当前节点的层次信息。每当递归进入新的一层（即向下遍历到子节点时），层次参数level增加1。这样，可以确保每个节点的层次信息准确无误地被计算和输出。

【算法描述】

void preorderTraversalForest(BiNode** forest, int size) {
    for (int i = 0; i < size; i++) {
        printf("Tree %d:\n", i + 1);
        preorderTraversal(forest[i], 1); // 根节点层次为 1
        printf("\n");
    }
}

【测试程序】

#include <stdio.h>
#include <stdlib.h>

typedef struct BiNode {
    char data;
    struct BiNode* lChild;
    struct BiNode* rChild;
} BiNode, *BiTree;

void preorderTraversal(BiNode* root, int level) {
    if (root == NULL)
        return;
    
    printf("Node: %c, Level: %d\n", root->data, level);
    preorderTraversal(root->lChild, level + 1);
    preorderTraversal(root->rChild, level + 1);
}

void preorderTraversalForest(BiNode** forest, int size) {
    for (int i = 0; i < size; i++) {
        printf("Tree %d:\n", i + 1);
        preorderTraversal(forest[i], 1); // 根节点层次为 1
        printf("\n");
    }
}

BiNode* createNode(char data) {
    BiNode* newNode = (BiNode*)malloc(sizeof(BiNode));
    newNode->data = data;
    newNode->lChild = NULL;
    newNode->rChild = NULL;
    return newNode;
}

int main() {
    // 创建森林，包含两棵树
    BiNode* forest[2];

    // 创建第一棵树
    //      A
    //     / \
    //    B   C
    BiNode* tree1 = createNode('A');
    tree1->lChild = createNode('B');
    tree1->rChild = createNode('C');

    // 创建第二棵树
    //      D
    //       \
    //        E
    BiNode* tree2 = createNode('D');
    tree2->rChild = createNode('E');

    forest[0] = tree1;
    forest[1] = tree2;

    // 遍历森林
    preorderTraversalForest(forest, 2);

    // 释放分配的内存
    free(tree1->lChild);
    free(tree1->rChild);
    free(tree1);
    free(tree2->rChild);
    free(tree2);

    return 0;
}