C语言实现二叉树的层次遍历(队列)

画画还真是费时间，主要的思路就是有队列来完成层次遍历，首先需要一个遍历结点的指针p，初始化首尾指针，当p！=null进入循环，让根节点1入队，rear指针+1，

下面的循环遍历条件是首尾指针不等(rear!=front) 标记一下此时的父结点p就是队列的首结点p=queue[rear],首节点出队front+1，如果当前父节点的左子树不是null，那么左结点入队，rear+1

如果当前父节点的右子树不是null,那么

右节点入队，rear+1.。这样一层遍历就完成了此时队列里面是2和3，p为2结点。接着第二轮，标记此时的父节点p为队列的首节点2，2结点出队front+1，

p的左子树不为null，4结点入队，同理5结点入队。第三轮。标记父节点p为队列的首节点此时为3结点。3结点出队，front+1,3结点没有左右子树进入第四轮。标记父节点p为队首4，4出队

同理下一轮5出队 。rear==front 队空结束

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 256
typedef struct BitNode{
    int val;
    struct BitNode * Lchild;
    struct BitNode * Rchild;
}*BitTree , TreeNode;


/*
typedef struct Queue{
    int arr[MAXSIZE];
    int rear ;
    int front ;
} ;*/
BitTree creatBitTree(BitTree root);
 void Preorder_traversal(BitTree root);
 void Level_traversal(BitTree root);
 void visit(BitTree root);
int main(){
    BitTree root = NULL ;
    printf("请输入值0表示NULL\n");
    root =creatBitTree(root);
    printf("先序遍历是:");
    Preorder_traversal(root);
    printf("\n");
    printf("层次遍历是:");
    Level_traversal(root);
    printf("\n");
}
BitTree creatBitTree(BitTree root){
    int data ;
    scanf("%d",&data);
    if(data == 0){
        root = NULL;
    }
    else{
        root = (BitTree)malloc(sizeof(TreeNode));
        root->val = data;
        if(!root){
            printf("内存分配失败\n");
            exit(1);
        }
        root->Lchild =creatBitTree(root->Lchild);
        root->Rchild =creatBitTree(root->Rchild);
    }
    return root;
}
void Preorder_traversal(BitTree root){
    if(root){
        printf("%d ",root->val);
        Preorder_traversal(root->Lchild);
        Preorder_traversal(root->Rchild);
    }
}
void Level_traversal(BitTree root){
    BitTree queue[MAXSIZE];
    int rear =0,front =0;
    BitTree p = root ;
    if(p!=NULL){
        //根结点入队(是整个结点入队)
        queue[rear] = p;
        rear=(rear+1)%MAXSIZE ;
        while(rear != front){
            //每次进来首尾指针不同的时候p指向队列中第一个元素，然后p出队,front指针+1
            p =queue[front];
            visit(queue[front]);
            front =(front+1)%MAXSIZE;
            if(p->Lchild!=NULL){
                //入队左子结点
                queue[rear]=p->Lchild;
                rear =(rear+1)%MAXSIZE;
            }
            if(p->Rchild!=NULL){
                //入队右子结点
                queue[rear]=p->Rchild;
                rear =(rear+1)%MAXSIZE;
                
            }
        }
    }
}
void visit(BitTree root){
    printf("%d ",root->val);
}

3
   /   9  20
    /     15   7

[
  [3],
  [9,20],
  [15,7]
]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
# define MAX_NUM 10000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if(!root){
        *returnSize = 0;
        return NULL;
    }
    struct TreeNode** Queen = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*MAX_NUM);  // 定义指针队列，用来存储所有节点的地址
    int** ret = (int**)malloc(sizeof(int*)*MAX_NUM);
    int i = 0, Queen_len, level_len, level_cnt;  // Queen_len：Queen中已有元素个数， level_len：每层的节点个数， level_cnt：每层的节点个数计数，
    *returnColumnSizes = (int*)malloc(sizeof(int)*MAX_NUM);

    // 头节点入队
    Queen[0] = root;
    Queen_len++;
    level_len = 1;
    *returnSize = 0;
    (*returnColumnSizes)[*returnSize] = level_len;
    // 遍历队列
    while(i<Queen_len){
        ret[*returnSize] = (int*)malloc(sizeof(int)*((*returnColumnSizes)[*returnSize]));
        level_cnt = 0;
        // 遍历当前层
        for(int j=0; j<level_len; j++){
            // 取出当前节点存入ret
            ret[*returnSize][j] = Queen[i+j]->val; 
            // 取出当前节点的左右节点存入Queen
            if(Queen[i+j]->left){
                Queen[Queen_len++] = Queen[i+j]->left;
                level_cnt++;
            }
            if(Queen[i+j]->right){
                Queen[Queen_len++] = Queen[i+j]->right;
                level_cnt++;
            }
        }
        i += level_len;
        level_len = level_cnt;
        (*returnSize)++;
        (*returnColumnSizes)[*returnSize] = level_len;
    }
    return ret;
}