歡迎來到我的：世界
希望作者的文章對(duì)你有所幫助，有不足的地方還請(qǐng)指正，大家一起學(xué)習(xí)交流 !
前言
國(guó)慶到了，也要內(nèi)卷一下，感謝所以老鐵們的支持！??
隊(duì)列的實(shí)現(xiàn)
1、隊(duì)列的定義
隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。
隊(duì)列是一種先進(jìn)先出（First In First Out）的線性表，簡(jiǎn)稱FIFO。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭；
隊(duì)頭（Front）：允許刪除的一端，又稱隊(duì)首。
隊(duì)尾（Rear）：允許插入的一端。
空隊(duì)列：不包含任何元素的空表。
鏈?zhǔn)疥?duì)列存儲(chǔ)類型：
typedef int QDatatype;
typedef struct QueueNode
{
QDatatype val;//記錄每個(gè)節(jié)點(diǎn)的值
struct QueueNode* next;//下一個(gè)節(jié)點(diǎn)
}QueueNode;
typedef struct Queue
{
QueueNode* head;//隊(duì)列的頭指針
QueueNode* tail;//隊(duì)列的尾指針
int size;//記錄隊(duì)列的元素個(gè)數(shù)，開始為0；
}Queue;
隊(duì)列的常見基本操作：
//初始化隊(duì)列，構(gòu)造一個(gè)空隊(duì)列pd。
void QueueInit(Queue* pd);
//清除隊(duì)列，將隊(duì)列清除，以免空間泄露
void Queuedestroy(Queue* pd);
//入隊(duì)，若隊(duì)列pd未滿，將x加入，使之成為新的隊(duì)尾。
void Queuepush(Queue* pd, QDatatype x);
//出隊(duì)，若隊(duì)列pd非空，刪除隊(duì)頭元素。
void QueuePop(Queue* pd);
//讀取隊(duì)頭元素值，并返回值
QDatatype QueueFront(Queue* pd);
//判隊(duì)列空，若隊(duì)列pd為空返回true，否則返回false。
bool QueueEmpty(Queue* pd);
鏈隊(duì)列初始化
void QueueInit(Queue* pd)
{
//構(gòu)造一個(gè)空隊(duì)列
pd->head = pd->tail = NULL;
pd->size = 0;
}
鏈隊(duì)列入隊(duì)
void Queuepush(Queue* pd, QDatatype x)
{
assert(pd);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->next = NULL;
newnode->val = x;
if (pd->tail == NULL)
{
pd->head = pd->tail = newnode;
}
else
{
pd->tail->next = newnode;
pd->tail = newnode;
}
pd->size++;
}
出隊(duì)列，刪除隊(duì)頭元素
void QueuePop(Queue* pd)
{
assert(pd);
assert(!QueueEmpty(pd));
if (pd->head->next == NULL)
{
free(pd->head);
pd->tail = pd->head = NULL;
}
else
{
QueueNode* next = pd->head->next;
free(pd->head);
pd->head = next;
}
pd->size--;
}
讀取隊(duì)頭元素
QDatatype QueueFront(Queue* pd)
{
assert(pd);
assert(!QueueEmpty(pd));
return pd->head->val;
}
判隊(duì)列空，若隊(duì)列pd為空返回true，否則返回false。
bool QueueEmpty(Queue* pd)
{
assert(pd);
return pd->head == NULL;
}
清除隊(duì)列，釋放空間
void Queuedestroy(Queue* pd)
{
assert(pd);
QueueNode* cur = pd->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pd->head = pd->tail = NULL;
pd->size = 0;
}
層序遍歷詳解
緊接上回，以層來訪問，一層一層往下訪問，每一層是從左往右訪問;
這里用到了隊(duì)列，將根節(jié)點(diǎn)先A存入隊(duì)列中，然后再將其子節(jié)點(diǎn)a b存入隊(duì)列，再取出根節(jié)點(diǎn)A，上述操作為一個(gè)循環(huán)；而后在存入上一次存入a b 他們分別的子節(jié)點(diǎn)，然后在取出來，依次執(zhí)行操作下去，就是層序遍歷；
圖解：
代碼實(shí)現(xiàn)：
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);//隊(duì)列初始化
//如果根節(jié)點(diǎn)不為空，則將其存入隊(duì)列
if (root)
{
Queuepush(&q, root);
}
//直到隊(duì)列為空則代表遍歷完成
while (!QueueEmpty(&q))
{
BTNode* tem = QueueFront(&q);
printf("%d ", tem->val);
if (tem->left)//是避免NULL也存入到隊(duì)列中去
Queuepush(&q, tem->left);
if (tem->right)//是避免NULL也存入到隊(duì)列中去
Queuepush(&q, tem->right);
QueuePop(&q);
}
Queuedestroy(&q);
}
強(qiáng)化練習(xí)
1.判斷是不是完全二叉樹
地址：oj地址
解題思路：
要知道完全二叉樹是一種什么樣的結(jié)構(gòu)：
所以這道題可以通過層序遍歷的方式來解決；
可以看出：完全二叉樹的非空節(jié)點(diǎn)是連續(xù)的，而非完全二叉樹的非空節(jié)點(diǎn)不是連續(xù)的；可以根據(jù)這點(diǎn)來解決問題；
int BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
Queuepush(&q, root);
}
//層序遍歷出最后一個(gè)葉節(jié)點(diǎn)，找到第一個(gè)空節(jié)點(diǎn)
while (!QueueEmpty(&q))
{
BTNode* tem = QueueFront(&q);
if (tem == NULL)
break;
//這是將空節(jié)點(diǎn)也存入到了隊(duì)列中
Queuepush(&q, tem->left);
Queuepush(&q, tem->right);
QueuePop(&q);
}
//找到了空節(jié)點(diǎn)，繼續(xù)往下找
while (!QueueEmpty(&q))
{
BTNode* tem = QueueFront(&q);
QueuePop(&q);
if (tem)//如果有一個(gè)幾點(diǎn)不為空節(jié)點(diǎn)，則代表不是連續(xù)的空節(jié)點(diǎn)，則代表該不是完全二叉樹，返回false；
{
Queuedestroy(&q);
return false;
}
}
//否則給該空節(jié)點(diǎn)是連續(xù)的，證明是完全二叉樹，返回true
Queuedestroy(&q);
return true;
}
求二叉樹的最大深度
地址oj地址
解題思路：
樹的最大深度也就是其最大的高度；求高度的一個(gè)思路：
根節(jié)點(diǎn)高度=其左右子節(jié)點(diǎn)高度高的+1；
具體代碼實(shí)現(xiàn)：
int maxDepth(struct TreeNode* root){
if(root==NULL)
return 0;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return left>right?left+1:right+1;
}
如果你知道一個(gè)函數(shù)fmax那就更簡(jiǎn)單了；該函數(shù)就是用來求兩個(gè)值返回大的那一個(gè)；
代碼實(shí)現(xiàn)：
int maxDepth(struct TreeNode* root){
if(root==NULL)
return 0;
return fmax(maxDepth(root->left),maxDepth(root->right))+1;
}
總結(jié)
到了最后：感謝支持文章來源：http://www.zghlxwxcb.cn/news/detail-715471.html
我還想告訴你的是：
------------對(duì)過程全力以赴，對(duì)結(jié)果淡然處之
也是對(duì)我自己講的文章來源地址http://www.zghlxwxcb.cn/news/detail-715471.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】隊(duì)列實(shí)現(xiàn)+層序遍歷詳解+一些練題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
