C语言：如何用递归的方法层序遍历一棵二叉树？

Question

层序遍历使用递归，请求大佬描述一下详细思路，或者提供伪代码，感激不尽！

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT  10

typedef int status;
typedef int ElemType;
typedef int KeyType;
//数据元素类型定义

typedef struct {
    //二叉树结点类型定义
    KeyType  key;
    char others[20];
} TElemType;

typedef struct BiTNode {
    //二叉链表结点的定义
    TElemType  data;
    struct BiTNode* lchild, * rchild;
} BiTNode, * BiTree;

Answer 1

有个思路，就是给每个节点增加一个指向下一个兄弟节点的指针。然后访问的时候从根开始，向下遍历所有左孩子，对于每一个左孩子，递归遍历它的下一个兄弟节点。

麻烦的地方在于建立树的时候，要设置好指向下一个兄弟节点的指针。

Answer 2

可以用BFS，虽然不符合题目中递归的条件

BiTNode* q[TREE_SIZE];
q[0]=Root;
int head=0,tail=1;
while(head!=tail){
    BiTNode* u=q[head++];
    if(u->lchild) q[tail++]=u->lchild;
    if(u->rchild) q[tail++]=u->rchild;
}
// 此时q内即为答案

非要递归的话，可以给BiTNode增加一个成员depth，递归计算，然后用类似桶排的东西输出（？）总之感觉很难受