二叉树层序遍历（队列）
首先需要一个遍历结点的指针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,null,null,15,7],
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;
}