用层序遍历建一棵二叉树

要求用层序遍历的序列建一棵二叉树，并且用先序序列输出

层次遍历序列构造二叉树

让我们先来思考一下怎么层次遍历一棵二叉树：

1.树不为空，root先入队
2.进入循环，循环条件为队列不为空，取出队头元素，队头出队。
3.打印刚刚队头元素的数据。
4.它如果存在左孩子，左孩子入队。
5.它如果存在右孩子，右孩子入队。
6.结束一次循环，回到步骤2

构造二叉树过程和遍历很相似，假设要构造的二叉树的层次遍历序列存在一个数组里

1.只要数组不为空，就先入队数组首元素，并用这个值创建二叉树的root。
2.然后进入循环，循环条件为队列不为空，取出队头元素，队头出队。
3.只要数组还有元素，就先给刚刚拿出的对头元素创建左孩子，然后左孩子入队。
4.同上，再创建右孩子，右孩子入队。
5.结束一次循环。回到2

例：

输入样例：

1 5 12 0 3 0 0 6 0 0 0 0

输出样例：

1 5 12 6 11 3

考虑到有的同学不会用c++中stl里的队列，我们这里分享一种用数组模拟的队列

数组模拟的队列也很好用，效率还高，要注意的是用数组模拟时，空间定义多大？

队列一般有两种情况：

1.如果我们已知有多少元素会入队，开辟一个足够大的计可以。

2.如果我们不知道有多少元素，用一个循环队列就可以。

数组模拟队列（固定大小）：

//声明队列 
Node* q[MaxSize];
//定义 hh为队头 tt为尾
int hh = 0, tt = -1;
//在队尾加入元素，t是一个节点指针
q[++tt] = t;
//取出队头
Node* s = q[hh++];
//队头出队
hh++;

代码（数组模拟）:

#include 
using namespace std;
#define MaxSize 1010
typedef long long LL;
//树节点的定义
struct Node {
	int e;
	Node* leftchild, * rightchild;
};
//创建树节点
//传入这个节点指针的地址，为的是传址调用，把这个节点返回回去
void Create_Node(Node*& t,int x) {
	t = (Node*)malloc(sizeof(struct Node));
	t->e = x;
	t->leftchild = t->rightchild = NULL;
}
//层次遍历序列建树
void Create_Level(Node*& t) {
	Node* q[MaxSize];//一个队列，元素类型是节点指针
	int hh = 0, tt = -1;//头是hh，尾是tt
	int x;
	cin >> x;
	if (x != 0) {
		Create_Node(t, x);
		q[++tt] = t;
	}
	while (hh<=tt) {//队列不空就一直循环
		Node* s = q[hh++];//取出队头
		//创建左右子节点，注意，如果是0代表没有节点，不用管它
		cin >> x;
		if (x != 0) {
			Create_Node(s->leftchild, x);
			q[++tt] = s->leftchild;
		}
		cin >> x;
		if (x != 0) {
			Create_Node(s->rightchild, x);
			q[++tt] = s->rightchild;
		}
	}
}
//递归先序遍历
void fun(Node* t) {
	if (t == NULL)return;
	cout << t->e << " ";
	fun(t->leftchild);
	fun(t->rightchild);
}
int main()
{
    //建树
	Node* t;
	Create_Level(t);
	//遍历树(先序)
	fun(t);
    return 0;
}

代码（c++STL   queue）：

#include 
using namespace std;
typedef long long LL;
//树节点的定义
struct Node {
	int e;
	Node* leftchild, * rightchild;
};
//创建树节点
//传入这个节点指针的地址，为的是传址调用，把这个节点返回回去
void Create_Node(Node*& t,int x) {
	t = (Node*)malloc(sizeof(struct Node));
	t->e = x;
	t->leftchild = t->rightchild = NULL;
}
//层次遍历序列建树
void Create_Level(Node*& t) {
	queue q;//一个队列，元素类型是节点指针
	int x;
	cin >> x;
	if (x != 0) {
		Create_Node(t, x);
		q.push(t);
	}
	while (!q.empty()) {//队列不空就一直循环
		Node* s = q.front();//取出队头
		//创建左右子节点，注意，如果是0代表没有节点，不用管它
		cin >> x;
		if (x != 0) {
			Create_Node(s->leftchild, x);
			q.push(s->leftchild);
		}
		cin >> x;
		if (x != 0) {
			Create_Node(s->rightchild, x);
			q.push(s->rightchild);
		}
		q.pop();
	}
}
//递归先序遍历
void fun(Node* t) {
	if (t == NULL)return;
	cout << t->e << " ";
	fun(t->leftchild);
	fun(t->rightchild);
}
int main()
{
    //建树
	Node* t;
	Create_Level(t);
	//遍历树(先序)
	fun(t);
    return 0;
}

运行结果：