給定一顆二叉樹，要求從下至上按層遍歷二叉樹，每層的訪問順序是從左到右，每一層單獨輸出一行，

這道題目是資料結構初學者最頭疼的題目之一，二叉樹，c語言的靈魂和難點都在指標，而想要這里的二叉樹實作的好，指標和鏈表的熟練運用必不可少，這題中還運用到了佇列（環形佇列）的知識，不熟悉的小伙伴可以去看一下這塊的操作，ps：這兩次被難哭了，艱難完成后心血來潮，希望能夠借此造福后來人，第一次寫博文，有問題的地方，希望大家多指教啦，

前言

這道題目其實用堆疊和二維陣列來處理蠻簡單的，不過既然考察二叉樹和層次遍歷，那還是按要求來好一些，這道題有幾個比較難處理的點在于：

一、元素是int型資料而不是單個字符，也就是說需要考慮一個元素包含多于一位的數字（正整數），

那這里我選擇將整個字串逐個字符讀取并“轉譯”，把‘（’，‘）’，‘，’三種符號用-1，-2，-3來代替（因為元素都是正整數，所以不怕混淆），其他部分的字符以字串形式讀取，每次當遇到‘（’，‘）’，‘，’，‘\n’標志著一個字串的結束，此時把這個字串用atoi函式轉換成int資料，存入int陣列中，遍歷完成后，實作了字串像字符陣列的轉譯，

void String2Int(char str[])
{
	int i = 0;
	char temp[6];
	int x = 0;
	while (true)
	{
		
		
		if (str[i] == '(')
		{
			num[number++] = atoi(temp); memset(temp, '\0', sizeof(temp)); num[number++] = -1; x = 0;
		}
		else if (str[i] == ')')
		{
			if(temp[0]!='\0')num[number++] = atoi(temp); memset(temp, '\0', sizeof(temp)); num[number++] = -2; x = 0;
		}
		else if (str[i] == ',')
	





## 二、二叉樹的創建
與其他經典二叉樹的創建方式一樣，陣列中逐個資料讀取后，通過條件陳述句選擇合適的操作，這個步驟需要用到堆疊St（后進先出），當有括號嵌套時，總是能夠保證由內到外，逐個完成鏈接，

```c
void CreateBTree(BTNode* &b)
{
	BTNode* St[MAXSIZE], * p=NULL;
	int top = -1, k=0, j = 0;
	int ch;
	b = NULL;
	ch = num[j];
	while (j<number)
	{
		switch (ch)
		{
		case -1:top++; St[top] = p; k = 1; break;
		case -2:top--; break;
		case -3:k = 2; break;
		default:p = (BTNode*)malloc(sizeof(BTNode));
			p->data = ch;
			p->left = p->right = NULL;
			if (b == NULL)
				b = p;
			else
			{
				switch (k)
				{
				case 1:St[top]->left = p; break;
				case 2:St[top]->right = p; break;
				}
			}
		}
		j++;
		ch = num[j];
	}
}

三、層次遍歷

作為二叉樹四種經典的遍歷方式之一，需要用到環形佇列，先進先出，每次把隊頭出隊（deSqQueue），并把出隊的元素的子節點從左到右依次入隊（enSqQueue），該程序可以對出隊元素增添一些需要的操作，故此可以實作層次遍歷，但這還不夠，因為我們這題要求分層并從最后一層開始輸出，

四、從上到下層次遍歷時如何實作分層，并按層數倒序輸出

基本思路是創建一個二維陣列，并將每一層放在同一維度中，難點在于遍歷程序中難以確定在什么位置分層，有人講可以根據深度判斷，但個人感覺這樣做的話完全就不需要二叉樹，所以這樣不太好，所以這里介紹一下動態分層的演算法，
增加四個變數i（初始值為0），cur（初始值為1）表示當前層數應當容納的元素數量，next（初始值為0）表示下一層應當容納的元素數量,floor(初始值為0)表示層數，具體操作如下：

void LevelOrder(BTNode* b)
{
	BTNode* p;
	SqQueue* qu;
	InitQueue(qu);
	enQueue(qu, b);
	int i, cur, next;
	i = next = 0;
	cur = 1;
	while (qu->front<qu->rear)
	{
		p = (BTNode*)malloc(sizeof(BTNode));
		if (i < cur)
		{
			deQueue(qu, p);
			result[floor][i] = p->data;
			if (p->left != NULL)
			{enQueue(qu, p->left); next++;}
			if (p->right != NULL)
			{enQueue(qu, p->right); next++;}
			i++;
		}
		else
		{
			cur = next;
			i = 0;
			next = 0;
			floor++;
		}
	}

}

結果的輸出

通過以上操作，最后從最后一層輸出即可

完整代碼如下

#define _CRT_SECURE_NO_WARNIGS
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>
#define MAXSIZE 200
int number = 0;
int floor = 0;
int print[100];
int result[10][20];
int num[MAXSIZE];
typedef struct node
{
	int data;
	struct node* left;
	struct node* right;
}BTNode;
typedef struct
{
	BTNode* data[MAXSIZE];
	int front, rear;
}SqQueue;
void String2Int(char str[])
{
	int i = 0;
	char temp[6];
	int x = 0;
	while (true)
	{
		
		
		if (str[i] == '(')
		{
			num[number++] = atoi(temp); memset(temp, '\0', sizeof(temp)); num[number++] = -1; x = 0;
		}
		else if (str[i] == ')')
		{
			if(temp[0]!='\0')num[number++] = atoi(temp); memset(temp, '\0', sizeof(temp)); num[number++] = -2; x = 0;
		}
		else if (str[i] == ',')
		{
			if(temp[0]!='\0')num[number++] = atoi(temp); memset(temp, '\0', sizeof(temp)); num[number++] = -3; x = 0;
		}
		else if (str[i] == '\0'||str[i]=='\n')
		{
			if(temp[0]!='\0')num[number++] = atoi(temp); break;
		}
		else
		{
			temp[x++] = str[i];
		}
		
		i++;
	}
}
void CreateBTree(BTNode* &b)
{
	BTNode* St[MAXSIZE], * p=NULL;
	int top = -1, k=0, j = 0;
	int ch;
	b = NULL;
	ch = num[j];
	while (j<number)
	{
		switch (ch)
		{
		case -1:top++; St[top] = p; k = 1; break;
		case -2:top--; break;
		case -3:k = 2; break;
		default:p = (BTNode*)malloc(sizeof(BTNode));
			p->data = ch;
			p->left = p->right = NULL;
			if (b == NULL)
				b = p;
			else
			{
				switch (k)
				{
				case 1:St[top]->left = p; break;
				case 2:St[top]->right = p; break;
				}
			}
		}
		j++;
		ch = num[j];
	}
}
void InitQueue(SqQueue*& qu)
{
	qu = (SqQueue*)malloc(sizeof(SqQueue));
	qu->front = qu->rear = 0;
}
bool enQueue(SqQueue*& q, BTNode* e)
{
	if ((q->rear + 1) % MAXSIZE == q->front)
		return false;
	q->rear = (q->rear + 1) % MAXSIZE;
	q->data[q->rear] = e;
	return true;
}
bool deQueue(SqQueue*& q, BTNode* &e)
{
	if (q->front == q->rear)
		return false;
	q->front = (q->front + 1) % MAXSIZE;
	e = q->data[q->front];
	return true;
}
bool QueueEmpty(SqQueue* q)
{
	return(q->front == q->rear);
}
void LevelOrder(BTNode* b)
{
	BTNode* p;
	SqQueue* qu;
	InitQueue(qu);
	enQueue(qu, b);
	int i, cur, next;
	i = next = 0;
	cur = 1;
	while (qu->front<qu->rear)
	{
		p = (BTNode*)malloc(sizeof(BTNode));
		if (i < cur)
		{
			deQueue(qu, p);
			result[floor][i] = p->data;
			if (p->left != NULL)
			{enQueue(qu, p->left); next++;}
			if (p->right != NULL)
			{enQueue(qu, p->right); next++;}
			i++;
		}
		else
		{
			cur = next;
			i = 0;
			next = 0;
			floor++;
		}
	}

}
int main()
{
	char str[MAXSIZE];
	
	BTNode* b=NULL;
	gets_s(str);
	String2Int(str);
	CreateBTree(b);
	LevelOrder(b);
	for (int i = floor; i >= 0; i--)
	{
		int j = 0;
		while (result[i][j] != '\0')
		{
			printf("%d ", result[i][j]);
			j++;
		}
		printf("\n");
	}
	return 0;
}

總結

一百多行一道題的資料結構代碼對小白還是不太友好，這道題的重點需要有二叉樹，堆疊，隊的基本知識，除了最后倒序輸出的小創新外，其他的演算法都屬于經典的基本操作，有問題可以查詢資料結構的課本，總之作為第一次博文，還是有許多的不完美之處，希望大家多多指導哦，