二叉树的层次遍历难以理解的地方

若前提有结构体定义：

//二叉树结点
typedef char datatype;
typedef struct node_tree{
    datatype data;
    struct node_tree *left;
    struct node_tree *right;
}Bitree,*Bit;

//链式队列结点
typedef struct node_queue{
    Bit data;         //一定要清楚此时队列里面存放的是什么了，此时存放的树的结点！！！而不是普普通通的数据了
    struct node_queue *next;
}linknode,*linklist;

typedef struct{
    linklist front;
    linklist rear;
}linkqueue;

那么以下代码请区分清楚！

linkqueue *lq = (linkqueue*)malloc(sizeof(linkqueue));

1、 这个代码可以理解为定义了一个盒子，这个盒子里面分别存放了 链表结点的头指针和尾指针；强调：你只需要知道这么一个盒子里面放了两个指针就好。例如下图：

​ 此时你只申请了两个野指针，他们此时代表的结点都没有，因此你需要对这两个指针进行初始化。对其初始化代码如下所示：

lq->front = lq->rear = (linklist)malloc(sizeof(linknode));
lq->front->next = lq->rear->next = NULL;

此时的两个指针已经同时指向了同一片区域，而这个区域的大小就是链表结点的大小； 注意：这边不能写成下面的这种形式。因为在链式队列中，头指针和尾指针的初始化是同时指向同一片区域，并且链式队列判空的条件也是其两个指针指向的区域相等。错误代码如下：

lq->front = (linklist)malloc(sizeof(linknode));
lq->rear = (linklist)malloc(sizeof(linknode));
lq->front->next = NULL;
lq->rear->next = NULL;

2、经过上面的处理，此时的链表可以想象成如下图所示：

​ 此时这边需要清楚一点：lq 是外面的一个大盒子；lq->front 是盒子里面的一个结点指针，lq->rear也是盒子里的一个结点指针。且现在他们所指的这一片区域中没有存放数据和指向下一个结点的地址。

3、当我们开始对链式队列中存放数据时，需明白两个指针的调用。伪代码如下：

linklist s = (linklist)malloc(sizeof(linknode));
s->data = data;   //注意  这边的data数据存放的是一个二叉树的结点，并不是普通int型等
s->next =NULL;
lq->rear->next = s;
lq->rear = s;
return true;

​ 这边可能会绕的地方就是 lq->rear->next = s; 这个代码说明了尾指针指向了最新结点，但同时front也指向了这个新结点。此时对应的图如下：

4、当我们需要对队列进行出队操作时，这边front指针的调用就非常的重要。我们要清楚lq->front 和 lq->front->next 分别都是什么。以下有两组代码进行区别：

linklist p = lq->front;
lq->front->next = p->next;    
free(p); 
return (lq->front->next->data);    //此时返回的值必然是垃圾值。

linklist p = lq->front;
lq->front = p->next;
free(p);
p = NULL;
return (lq->front->data);

​ 以下给出第一组示例图和第二组示例图加强区别判断：

​ 看图其实很容易看出区别来，第一组代码中的问题是：lq->front 是个链表结点指针，lq->front->next也是链表结点的指针，你如果是lq->front->next去指向p->next，那不就是一动都没动，等于在原地。那么当程序执行后面的free§时，会出现释放这个p结点的时候，front指向的结点又是跟p结点是相同结点，因此front指向的地方也是空了。那么不管return里面返回的是何种指针，其返回的都是垃圾值。