前言
來(lái)嘍來(lái)嘍~ 二叉樹(shù)的層序遍歷來(lái)嘍~
層序遍歷那是相當(dāng)有趣滴！
我的朋友，請(qǐng)不要迷惘，你要記住，你終有鯤鵬一日！
加油吧！從現(xiàn)在開(kāi)始~
一、層序遍歷的概念和實(shí)現(xiàn)
層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對(duì)二叉樹(shù)進(jìn)行層序遍歷。設(shè)二叉樹(shù)的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹(shù)的根節(jié)點(diǎn)出發(fā)，首先訪問(wèn)第一層的樹(shù)根節(jié)點(diǎn)，然后從左到右訪問(wèn)第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問(wèn)樹(shù)的結(jié)點(diǎn)的過(guò)程就是層序遍歷。
既然了解了層序遍的概念，那么要層序遍歷二叉樹(shù)那么首先就應(yīng)該想到利用隊(duì)列來(lái)進(jìn)行！
大家對(duì)于層序遍歷已經(jīng)有了一些基礎(chǔ)的認(rèn)知了吧，那么現(xiàn)在開(kāi)始代碼實(shí)現(xiàn)吧！
1.頭文件的聲明
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
2.二叉樹(shù)接口的定義
typedef char BTDataType;//類型重命名
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;//左子樹(shù)
struct BinaryTreeNode* right;//右子樹(shù)
}BTNode;
3.隊(duì)列接口的定義
這里有涉及到之前隊(duì)列的知識(shí)，如果對(duì)于隊(duì)列不是太了解的話可以看看之前的文章！
棧和隊(duì)列
//鏈表接口定義
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
//隊(duì)列接口定義
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Que;
void QueueInit(Que* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
//否為空
bool QueueEmpty(Que* pq)
{
assert(pq);
return pq->head == NULL;
}
void QueueDestroy(Que* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
//查找隊(duì)頭元素
QDataType QueueFront(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
void QueuePush(Que* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Que* pq)
{
assert(pq);//判斷隊(duì)列指針指向是否為空
assert(!QueueEmpty(pq));//判斷隊(duì)列里面的數(shù)據(jù)是否為空
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
4.前序遍歷構(gòu)建二叉樹(shù)
BTNode* BinaryTreeCreate(BTDataType* a, int* pi) {
if (a[*pi] == '#') {//如果字符為#，則說(shuō)明此處為空
(*pi)++;//讀取字符串中的下一個(gè)字符
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->data = a[*pi];
(*pi)++;
root->left = BinaryTreeCreate(a, pi);//構(gòu)建左子樹(shù)
root->right = BinaryTreeCreate(a, pi);//構(gòu)建右子樹(shù)
return root;
}
此處#轉(zhuǎn)化為NULL
5.層序遍歷代碼實(shí)現(xiàn)
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root) {
Que q;//定義一個(gè)隊(duì)列
QueueInit(&q);//初始化隊(duì)列
if (root)
QueuePush(&q, root);//如果根節(jié)點(diǎn)不為空則入隊(duì)列
while (!QueueEmpty(&q)) {
BTNode* front = QueueFront(&q);//指針指向隊(duì)頭
printf("%c ", front->data);//輸出隊(duì)頭字符
if(front->left!=NULL)//如果左子樹(shù)存在則將其入隊(duì)列
QueuePush(&q, front->left);
if(front->right!=NULL)//如果右子樹(shù)存在則將其入隊(duì)列
QueuePush(&q, front->right);
QueuePop(&q);//將頭結(jié)點(diǎn)刪除，并將下一個(gè)結(jié)點(diǎn)變?yōu)殛?duì)頭
}
printf("\n");
QueueDestroy(&q);//銷(xiāo)毀隊(duì)列
}
6.二叉樹(shù)的銷(xiāo)毀
利用后序遍歷思想，從左子樹(shù)，右子樹(shù)，根依次銷(xiāo)毀結(jié)點(diǎn)
// 二叉樹(shù)銷(xiāo)毀
void BinaryTreeDestory(BTNode** root) {
if (root == NULL) {
return;
}
BinaryTreePrevOrder((*root)->left);
BinaryTreePrevOrder((*root)->right);
free(*root);
}
7.主函數(shù)的定義
int main() {
char arr[] = "ABD##E#H##CF##G##";
BinaryTreeLevelOrder(arr);
return 0;
}
8.運(yùn)行結(jié)果
二、判斷二叉樹(shù)是否是完全二叉樹(shù)
例子：數(shù)組"ABD##E#H##CF##G##"
思路解析：
這道題理所當(dāng)擔(dān)要用到層序遍歷思想!
代碼實(shí)現(xiàn)：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-723128.html
int BinaryTreeComplete(BTNode* root) {
Que q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q)) {
BTNode* front = QueueFront(&q);//front指向隊(duì)頭
if (front == NULL)//當(dāng)隊(duì)頭為NULL時(shí)退出入隊(duì)
break;
QueuePush(&q, front->left);//左子樹(shù)入隊(duì)
QueuePush(&q, front->right);//右子樹(shù)入隊(duì)
QueuePop(&q);//刪除隊(duì)頭
}
while (!QueueEmpty(&q)) {
BTNode* front = QueueFront(&q);//front指向隊(duì)頭，即NULL結(jié)點(diǎn)
QueuePop(&q);//
if (front != NULL) {//當(dāng)隊(duì)頭不為BULL，則說(shuō)明這不是完全二叉樹(shù)
QueueDestroy(&q);//銷(xiāo)毀隊(duì)列
return false;
}
}
QueueDestroy(&q);
return true;//如果從隊(duì)列中的第一個(gè)NULL開(kāi)始后面也全為NULL，則說(shuō)明是完全二叉樹(shù)
}
總結(jié)
不知道有沒(méi)有難住你呢！
相信你不會(huì)被這些小困難絆倒！
說(shuō)給你，更說(shuō)給我，現(xiàn)在的努力至少不會(huì)辜負(fù)這一點(diǎn)青春時(shí)光！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-723128.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——二叉樹(shù)層序遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
