层序遍历

本来以为四种遍历方法用递归都很容易解决，谁知看上去最直观的层序遍历不是太容易，参考了下通过链式队列的实现算法，完成了这项遍历

首先将根结点数据输出，并将根结点入队列，然后前端结点出队列，并输出该结点的数据域，如果该结点的左右孩子结点存在，也入队列，由于一个结点的孩子结点在该结点所在层的下一层，而且左孩子结点会在右孩子结点之前入队列，所以如此就能满足层序遍历的顺序，持续地出队列，输出数据域，入队列过程

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode;

typedef struct QueueNode {
    struct TreeNode *ptreenode;
    struct QueueNode *next;
}QueueNode;

typedef struct Queue {
    struct QueueNode *front;
    struct QueueNode *rear;
}Queue;

TreeNode* CreateBTree(){
    TreeNode *t;   
    int num;
    scanf_s(“%d”, &num);
    if (num == 0)
        t = NULL;
    else {
        t = (TreeNode *)malloc(sizeof(TreeNode));
        t->data = num;
        printf(“Node %d left child Node: “, t->data);
        t->left = CreateBTree();
        printf(“Node %d right child Node: “, t->data);
        t->right = CreateBTree();
    }
    return t;
}

int FirstVisit(TreeNode *BTree){
   
    if (BTree){
        printf(“%d “, BTree->data);
        FirstVisit(BTree->left);
        FirstVisit(BTree->right);
    }
    return 0;
}

Queue* InitQueue(Queue *q){
    q->front = q->rear = (QueueNode *)malloc(sizeof(QueueNode));
    q->front->next = NULL;
    q->rear->next = NULL;
    return q;
}

int PushQueue(Queue *q, TreeNode *tnode){
    QueueNode *qnode;
    qnode = (QueueNode *)malloc(sizeof(QueueNode));
    qnode->next = NULL;
    qnode->ptreenode = tnode;
    q->rear->next = qnode;
    q->rear = qnode;
    return 0;
}

TreeNode* PopQueue(Queue *q){
//    q->front->next = q->front->next->next;
    QueueNode *qnode;
    TreeNode *tnode;
    qnode = q->front->next;
//    qnode = qnode->next;
    q->front->next = qnode->next;
    tnode = qnode->ptreenode;
    if (q->rear == qnode)
        q->rear = q->front;
    free(qnode);
    return tnode;
}

int main(){
    TreeNode *tree, *treenode;
    printf(“Please input root node: “);
    tree = CreateBTree();
    /*Test
    printf(“First Visit: “);
    FirstVisit(tree);
    */
    Queue *queue;
    queue = (Queue *)malloc(sizeof(Queue));
    InitQueue(queue);

    PushQueue(queue, tree);
    printf(“Step Visit: %d “, tree->data);
    while (queue->front->next != NULL){
        treenode = PopQueue(queue);
        if (treenode->left != NULL){
            printf(“%d “, treenode->left->data);
            PushQueue(queue, treenode->left);
        }
        if (treenode->right != NULL){
            printf(“%d “, treenode->right->data);
            PushQueue(queue, treenode->right);
        }
    }
    free(queue);
    printf(“\n”);
    return 0;
}