题目
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
输出层序遍历的结果
3 9 20 15 7
分析
迭代法
用一个队列来存储当前层数的节点地址，每次从队列头部取出一个节点，然后判断是否为NULL，若不为空则输出当前节点，并把左右子节点存入队列尾部。直到队列中没有元素为止。因为这里拿c语言实现，所以用数组代替队列，
C
#include<stdio.h> #include<assert.h> #include<stdbool.h> #include<stdlib.h> #define MAXSIZE 100 /* 存储空间初始分配量 */ typedef int TElemType; /* 树结点的数据类型，目前暂定为整型 */ typedef struct node { TElemType data; struct node* lchild, * rchild;//左右孩纸指针 }BTree; void CreatTree(BTree** T)//构造二叉树 { TElemType n = 0; scanf("%d", &n); if (999 != n) { (*T) = (BTree*)malloc(sizeof(BTree)); assert(NULL != *T); (*T)->data = n; CreatTree(&((*T)->lchild)); CreatTree(&((*T)->rchild)); } else { *T = NULL; } } //层序遍历 迭代法 void sequenceTraversal(BTree* T) { assert(NULL != T); BTree* queue[MAXSIZE] = { 0 }; queue[0] = T; int end = 1; int start = 0; while (start < end) { T = queue[start]; start++; if (T != NULL) { printf("%d ", T->data); queue[end++] = T->lchild; queue[end++] = T->rchild; } } } int main() { BTree* root = NULL; printf("请按照先序的规则输入数据：\n"); CreatTree(&root); printf("层序遍历输出：\n"); sequenceTraversal(root); printf("\n"); return 0; }
本章完！
