二叉树的层序遍历中的几个问题（C语言）

在使用C语言实现二叉树的层序过程中，从队列的建立、二叉树的建立、层序遍历几个环节中遇到了几个问题，现记录一下这些问题。

---

1、队列的建立

• 队列初始化：InitQueue
• 在队尾加入元素：Push
• 删除队头元素：Pop

队列初始化的时候是开辟一个next域为NULL的队列指针，注意应该使得队列的头等于队列的尾，这样在队列增加和删除元素的时候队列的头才会指向下一个元素，不然整个队列是无法连起来的。

Status Push(LinkQueue &Q,QElemType x){
    //尾入
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    p->data = x;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return true;
}

Status Pop(LinkQueue &Q,QElemType &x){
    //头出
    QueuePtr q = Q.front->next;
    x = q->data;
    Q.front->next = q->next;
    if (Q.rear == q)
        Q.rear = Q.front;
    return true;
}   

Status InitQueue(LinkQueue &Q){
    //初始化
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    p->next = NULL;
    Q.front = Q.rear = p;
    return true;
}

2、二叉树的建立

一般二叉树的建立都是一边输入一边建立，对于每一次的递归，都需要获取输入的元素，这在调试程序的时候十分不方便。所以尝试通过传入字符串进行二叉树的建立。

在建立过程中有个很麻烦的问题，就是如何定位当前到底递归到字符串的哪个位置了，简单的使用int n来记录是做不到的，因为当建立了lchild的之后，再建立rchild会回溯到之前建立lchild时候的n，n做不到递归一次就+1。同样的，简单的使用char *str也是做不到的，同样的道理也会回溯到之前的位置。

这个时候就只能用指针的指针p，因为当回溯的时候，p的地址也就是p指向的指针q会回溯，但是这时候q指向的数值已经发生了改变，这样就可以实现以上的要求了。使用int **n来记录当前递归进行到了字符串的哪个位置。

BiTreePtr CreateBiTree(char * str,int *n){
    if (str[*n] == ' '){
        return NULL;
    }
    BiTreePtr p = (BiTreePtr)malloc(sizeof(BiTree));
    p->data = str[*n];
    *n = *n + 1;
    p->lchild = CreateBiTree(str, n);
    *n = *n + 1;
    p->rchild = CreateBiTree(str, n);
    return p;
}

3、层序遍历

层顺遍历的思路比较简单，节点入队列，循环判断当前队列是否为空，出队列的时候输出data，再将其左结点、右结点入队列。

Status LevelTraversal(BiTreePtr tree,LinkQueue Q){
    Push(Q, tree);
    while (Q.front != Q.rear){
        BiTreePtr p = NULL;
        Pop(Q, p);
        printf("%c", p->data);
        if (p->lchild){
            Push(Q, p->lchild);
        }
        if (p->rchild){
            Push(Q, p->rchild);
        }
    }
    return true;
}

明明很简单的程序却写了这么久！要注意细节啊注意细节~