二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈，紅黑樹等會用到三叉鏈。

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點左孩子struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點右孩子BTDataType _data; // 當(dāng)前節(jié)點值域
}
// 三叉鏈
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向當(dāng)前節(jié)點的雙親struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點左孩子struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點右孩子BTDataType _data; // 當(dāng)前節(jié)點值域
}

三、二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實現(xiàn)

1.結(jié)構(gòu)的定義

// 符號和結(jié)構(gòu)的定義
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

2.構(gòu)建二叉樹

由于二叉樹不能進(jìn)行增加和刪除操作，所以一般都是給定一個字符串或者一個數(shù)組，該字符串或者數(shù)組有我們創(chuàng)建二叉樹所需要的所有節(jié)點，我們根據(jù)字符串或者數(shù)組的內(nèi)容來構(gòu)建二叉樹

【注意】字符串或者數(shù)組中 # 表示空節(jié)點，即上一個節(jié)點沒有左孩子或者右孩子

// 通過前序遍歷的數(shù)組 1 2 3 # # 4 5 # # 6 ##構(gòu)建二叉樹
BTNode* BinaryTreeCreat(BTDataType* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}// 創(chuàng)建根節(jié)點BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = a[*pi];(*pi)++;// 創(chuàng)建左右子樹root->left = BinaryTreeCreat(a, pi);root->right = BinaryTreeCreat(a, pi);return root;
}

3.二叉樹前序遍歷

所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進(jìn)行相應(yīng)的操作，并且每個節(jié)點只操作一次。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運算之一，也是二叉樹上進(jìn)行其它運算的基礎(chǔ)

按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：

前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前

中序遍歷(Inorder Traversal)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間）

后序遍歷(Postorder Traversal)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后

由于被訪問的結(jié)點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

前序遍歷遞歸圖解：

//二叉樹先序遍歷
void PreOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){printf("NULL ");return;}printf("%d ", root->data);   //訪問根節(jié)點PreOrder(root->left);        //先序遍歷左子樹PreOrder(root->right);       //先序遍歷右子樹
}

4.二叉樹中序遍歷

//二叉樹中序遍歷
void InOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){//printf("NULL ");return;}InOrder(root->left);              //中序遍歷左子樹printf("%d ", root->data);        //訪問根節(jié)點//printf("%c ", root->data);InOrder(root->right);             //中序遍歷右子樹
}

5.二叉樹后序遍歷

/ 二叉樹后序遍歷
void PostOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){printf("NULL ");return;}PostOrder(root->left);        //后序遍歷左子樹PostOrder(root->right);       //后序遍歷右子樹printf("%d ", root->data);    //訪問根節(jié)點
}

6.二叉樹層次遍歷

層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根節(jié)點所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第2層上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點的過程就是層序遍歷

相比于其他三種遍歷方式，層序遍歷采用的是非遞歸的方式，其具體思路是：

利用一個隊列來存儲二叉樹節(jié)點的地址，先讓父節(jié)點入隊列，然后父節(jié)點出隊列，同時父節(jié)點的左右孩子會入隊列，如果沒有就不入，直到隊列為空時結(jié)束，這樣使得當(dāng)一層節(jié)點全部出隊列的時候，下一層的節(jié)點剛好全部入隊列，當(dāng)隊列為空時，二叉樹的節(jié)點就全部訪問完畢了；

【注意】我們用隊列來存儲二叉樹節(jié)點的地址，所以我們需要自己實現(xiàn)一個隊列，也可以把我們之前實現(xiàn)寫的隊列Queue.h和Queue.c加入到當(dāng)前工程中；此外，我們應(yīng)該將二叉樹節(jié)點的結(jié)構(gòu)體需要定義在隊列結(jié)構(gòu)體的前面。

// 二叉樹層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){// 取出隊頭元素BTNode* front = QueueFront(&q);QueuePop(root);printf("%c ", front->data);// 將隊頭元素的左右子節(jié)點入隊列if (front->left)QueuePop(&q, front->left);if (front->right)QueuePop(&q, front->right);}QueueDestroy(&q);
}

7.二叉樹節(jié)點個數(shù)

我們采用子問題思路來解決，我們要計算二叉樹節(jié)點的個數(shù)，那么分為左子樹的節(jié)點個數(shù)和右節(jié)點的個數(shù)再加上根節(jié)點 二叉樹節(jié)點數(shù) = 左子樹節(jié)點個數(shù)+右節(jié)點個數(shù)+根節(jié)點

/計算二叉樹節(jié)點個數(shù)
int TreeSize(BTNode* root)
{if (root == NULL)return 0;// 左子樹節(jié)點個數(shù)+右節(jié)點個數(shù)+根節(jié)點return TreeSize(root->left) + TreeSize(root->right) + 1;
}

8.二叉樹葉子節(jié)點個數(shù)

和計算二叉樹節(jié)點個數(shù)方法一樣，但是葉子節(jié)點要求左孩子為空并且右孩子為空，所以葉子節(jié)點數(shù)等與左右葉子數(shù)之和

//計算二叉樹葉子節(jié)點個數(shù)
int TreeLeafSize(BTNode* root)
{//空樹返回0if (root == NULL){return 0;}//左子樹和右子樹均為空則為葉子節(jié)點if (root->left == NULL && root->right == NULL){return 1;}//葉子節(jié)點數(shù)等與左右葉子數(shù)之和return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

9.二叉樹第k層節(jié)點個數(shù)

求第k層節(jié)點的個數(shù)轉(zhuǎn)換成求左右子樹的k-1層的節(jié)點個數(shù)，當(dāng)k為1 的時候，節(jié)點數(shù)為1

//第K層節(jié)點個數(shù)
int TreeKLevel(BTNode* root, int k)
{assert(k > 0);  //層數(shù)大于0//空樹返回0if (root == NULL){return 0;}if (k == 1){return 1;}//相對于根是第k層，則相對于根是子樹的k-1層！！！//換成求子樹第k-1層return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);}c

10.二叉樹的高度

樹的高度等于左子樹的高度和右子樹的高度的最大值+1

//計算二叉樹深度
int TreeHeight(BTNode* root)
{//如果是空樹返回0if (root == NULL){return 0;}int lret = TreeHeight(root->left);  //遞歸計算左子樹的深度記為lretint rret = TreeHeight(root->right); //遞歸計算右子樹的深度記為rret/*if (lret > rret){return lret + 1;}else{return rret + 1;}*///二叉樹的深度為lret和rret的較大者+1return lret > rret ? lret + 1 : rret + 1;
}

11.在二叉樹中查找值為x的節(jié)點

我們先在左子樹找沒有找到再到右子樹找，都沒有找到則返回NULL；注意的是，上一個節(jié)點的返回值將作為下一個節(jié)點是否繼續(xù)找的依據(jù)，所以我們要用一個指針保存左右子樹查找的返回值，再進(jìn)行判斷。

// 在二叉樹中查找值為x的節(jié)點
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;// 先去左樹找BTNode* lret = TreeFind(root->left, x);if (lret)return lret;// 左樹沒有找到，再到右樹找BTNode* rret = TreeFind(root->right, x);if (rret)return rret;//return TreeFind(root->right, x);// 都找不到則返回空retun NULL;
}

12.判斷二叉樹是否是完全二叉樹

我們知道，高度為h的完全二叉樹，前h-1層都是滿二叉樹，最后一層不一定是滿二叉樹，但是最后一層的節(jié)點必須是連續(xù)的，也就是說，當(dāng)完全二叉樹遇到空節(jié)點的時候，后面就不會在出現(xiàn)非空的節(jié)點，否則就不是完全二叉樹

根據(jù)上面完全二叉樹的性質(zhì)，我們可以利用二叉樹的層序遍歷來判斷二叉樹是否是完全二叉樹，基本思路為對二叉樹進(jìn)行層序遍歷，不管節(jié)點是否為空都入隊列，當(dāng)隊頭的元素為空的時候，我們檢查隊列中的剩余數(shù)據(jù)是否都是空節(jié)點，如果含有非空節(jié)點則該樹就不是完全二叉樹。

// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front == NULL)break;QueuePop(&q);QueuePush(&q, root->left);QueuePush(&q, root->right);}// 遇到空以后，后面全是空，則是完全二叉樹// 遇到空以后，后面存在非空，則不是完全二叉樹while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front != NULL){QueueDestroy(&q);return false;}QueuePop(&q);}return true;
}

13.銷毀二叉樹

我們不能直接刪除根節(jié)點，需要采用后續(xù)遍歷的方式進(jìn)行依次刪除

// 銷毀二叉樹
void BinaryTreeDestroy(BTNode* root)
{if (root == NULL)return;// 通過后續(xù)遍歷來銷毀節(jié)點BinaryTreeDestroy(root->left);BinaryTreeDestroy(root->right);// 此處置空不會影響外面，需要在外面進(jìn)行置空free(root);
}

四、完整代碼

1.BTree.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//創(chuàng)建二叉樹
BTNode* CreateTree();
//二叉樹先序遍歷
void PreOrder(BTNode* root);
//二叉樹中序遍歷
void InOrder(BTNode* root);
//二叉樹后序遍歷
void PostOrder(BTNode* root);
// 二叉樹層序遍歷
void BinaryTreeLevelOrder(BTNode* root);
//計算二叉樹節(jié)點個數(shù)
int TreeSize(BTNode* root);
//計算二叉樹深度
int TreeHeight(BTNode* root);
//第K層節(jié)點個數(shù)
int TreeKLevel(BTNode* root, int k);
//計算二叉樹葉子節(jié)點個數(shù)
int TreeLeafSize(BTNode* root);
//返回x所在的節(jié)點
BTNode* TreeFind(BTNode* root, BTDataType x);
//創(chuàng)建二叉樹
BTNode* BTreeCreate(char* a, int* pi);
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root);
// 銷毀二叉樹
void BinaryTreeDestroy(BTNode* root);

2.BTree.c

#include "BTree.h"//創(chuàng)建二叉樹
BTNode* CreateTree()
{//創(chuàng)建節(jié)點BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));assert(n1);BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));assert(n2);BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));assert(n3);BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));assert(n4);BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));assert(n5);BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));assert(n6);BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));assert(n7);//鏈接關(guān)系n1->data = 1;n2->data = 2;n3->data = 3;n4->data = 4;n5->data = 5;n6->data = 6;n7->data = 7;n1->left = n2;n1->right = n4;n2->left = n3;n2->right = NULL;n4->left = n5;n4->right = n6;n3->left = NULL;n3->right = NULL;n5->left = NULL;n5->right = NULL;n6->left = NULL;n6->right = NULL;n3->right = n7;n7->left = NULL;n7->right = NULL;return n1;
}//二叉樹先序遍歷
void PreOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){printf("NULL ");return;}printf("%d ", root->data);   //訪問根節(jié)點PreOrder(root->left);        //先序遍歷左子樹PreOrder(root->right);       //先序遍歷右子樹
}//二叉樹中序遍歷
void InOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){//printf("NULL ");return;}InOrder(root->left);              //中序遍歷左子樹printf("%d ", root->data);        //訪問根節(jié)點//printf("%c ", root->data);InOrder(root->right);             //中序遍歷右子樹
}// 二叉樹后序遍歷
void PostOrder(BTNode* root)
{//如果是空樹則返回NULLif (root == NULL){printf("NULL ");return;}PostOrder(root->left);        //后序遍歷左子樹PostOrder(root->right);       //后序遍歷右子樹printf("%d ", root->data);    //訪問根節(jié)點
}// 二叉樹層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){// 取出隊頭元素BTNode* front = QueueFront(&q);QueuePop(root);printf("%c ", front->data);// 將隊頭元素的左右子節(jié)點入隊列if (front->left)QueuePop(&q, front->left);if (front->right)QueuePop(&q, front->right);}QueueDestroy(&q);
}//int count = 0;//定義全局變量，導(dǎo)致兩次調(diào)用返回值不一樣//計算二叉樹節(jié)點個數(shù)
int TreeSize(BTNode* root)
{//知易行難（不行）遍歷計數(shù)//static int count = 0;//static修飾count成為全局變量，導(dǎo)致兩次返回值不一樣！！！// 第一次打印7，則第二次打印14！！！//if (root == NULL)//	return count;//	//++count;//TreeSize(root->left);//TreeSize(root->right);//	//	return count;/*if (root == NULL){return 0;}int lret = TreeSize(root->left);int rret = TreeSize(root->right);return TreeSize(root->left) + TreeSize(root->right) + 1;*//*if (root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;*///二叉樹的節(jié)點個數(shù)等于左子樹的個數(shù)+右子樹的深度+1return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}//計算二叉樹深度
int TreeHeight(BTNode* root)
{//如果是空樹返回0if (root == NULL){return 0;}int lret = TreeHeight(root->left);  //遞歸計算左子樹的深度記為lretint rret = TreeHeight(root->right); //遞歸計算右子樹的深度記為rret/*if (lret > rret){return lret + 1;}else{return rret + 1;}*///二叉樹的深度為lret和rret的較大者+1return lret > rret ? lret + 1 : rret + 1;
}//第K層節(jié)點個數(shù)
int TreeKLevel(BTNode* root, int k)
{assert(k > 0);  //層數(shù)大于0//空樹返回0if (root == NULL){return 0;}if (k == 1){return 1;}//相對于根是第k層，則相對于根是子樹的k-1層！！！//換成求子樹第k-1層return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);}//計算二叉樹葉子節(jié)點個數(shù)
int TreeLeafSize(BTNode* root)
{//空樹返回0if (root == NULL){return 0;}//左子樹和右子樹均為空則為葉子節(jié)點if (root->left == NULL && root->right == NULL){return 1;}//葉子節(jié)點數(shù)等與左右葉子數(shù)之和return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}//返回x所在的節(jié)點
BTNode* TreeFind(BTNode* root, BTDataType x)
{//空樹返回NULLif (root == NULL){return NULL;}//根節(jié)點返回root的地址 if (root->data == x){return root;}//先在左子樹找BTNode* lret = TreeFind(root->left, x);if (lret){return lret;}//左子樹沒找到，去右子樹找BTNode* rret = TreeFind(root->right, x);if (rret){return rret;}//不推薦，可讀性不強，不容易理解//return TreeFind(root->right, x);return NULL;
}BTNode* BTreeCreate(char* a, int* pi)
{//輸入字符為‘#’returnif (a[*pi] == '#'){(*pi)++;return NULL;}//創(chuàng)建新節(jié)點BTNode* root = (BTNode*)malloc(sizeof(BTNode));//空間未開辟成功，退出程序if (root == NULL){perror("malloc fail");exit(-1);}//數(shù)組的字符賦給根節(jié)點root->data = a[*pi];(*pi)++;root->left = BTreeCreate(a, pi);    //遞歸創(chuàng)建左子樹root->right = BTreeCreate(a, pi);  //遞歸創(chuàng)建右子樹return root;
}
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front == NULL)break;QueuePop(&q);QueuePush(&q, root->left);QueuePush(&q, root->right);}// 遇到空以后，后面全是空，則是完全二叉樹// 遇到空以后，后面存在非空，則不是完全二叉樹while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front != NULL){QueueDestroy(&q);return false;}QueuePop(&q);}return true;
}// 銷毀二叉樹
void BinaryTreeDestroy(BTNode* root)
{if (root == NULL)return;// 通過后續(xù)遍歷來銷毀節(jié)點BinaryTreeDestroy(root->left);BinaryTreeDestroy(root->right);// 此處置空不會影響外面，需要在外面進(jìn)行置空free(root);
}

3.test.c

#include "BTree.h"int main()
{//創(chuàng)建二叉樹BTNode* root = CreateTree();//先序遍歷二叉樹PreOrder(root);printf("\n");//計算二叉樹節(jié)點個數(shù)printf("Tree size:%d\n", TreeSize(root));printf("Tree size:%d\n", TreeSize(root));//計算二叉樹高度printf("Tree Height:%d\n", TreeHeight(root));//計算第k層節(jié)點個數(shù)printf("Tree KLevel:%d\n", TreeKLevel(root, 1));printf("Tree KLevel:%d\n", TreeKLevel(root, 2));printf("Tree KLevel:%d\n", TreeKLevel(root, 3));printf("Tree KLevel:%d\n", TreeKLevel(root, 4));//查找x所在的節(jié)點BTNode* ret = TreeFind(root, 7);printf("ret=%p\n", ret);printf("retbefore:%d\n", ret->data);//修改x所在的節(jié)點的值ret->data *= 10;printf("retafter:%d\n", ret->data);//計算二叉樹葉子節(jié)點個數(shù)printf("Tree LeafSize:%d\n", TreeLeafSize(root));//測試創(chuàng)建二叉樹//char str[100];       //創(chuàng)建數(shù)組//scanf("%s", str);    //輸入字符//int i = 0;           //記錄數(shù)組的下標(biāo)遞歸i的值不會改變，所以傳i的地址！！！//BTNode* root = BTreeCreate(str, &i);//InOrder(root);return 0;
}

4.Queue.h

#pragma once   //防止頭文件被重復(fù)包含//包含頭文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef char BTDataType;
typedef struct BinaryTree
{BTDataType data;struct BinaryTree* left;struct BinaryTree* right;
}BTNode;//結(jié)構(gòu)和符號的定義
typedef int QDataType;  //數(shù)據(jù)類型重定義//定義隊列的一個節(jié)點
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;   //記錄隊列的頭QNode* tail;   //記錄隊列的尾int size;      //記錄隊列的長度
}Queue;//函數(shù)的聲明
//初始化隊列
void QueueInit(Queue* pq);
//銷毀隊列
void QueueDestroy(Queue* pq);
//隊尾入隊列
void QueuePush(Queue* pq, QDataType x);
//對頭出隊列
void QueuePop(Queue* pq);
//獲取對頭元素
QDataType QueueFront(Queue* pq);
//獲取隊尾元素
QDataType QueueBack(Queue* pq);
//判斷隊列是否為空
bool QueueEmpty(Queue* pq);
//返回隊列元素個數(shù)
int QueueSize(Queue* pq);

5.Queue.c

#include "Queue.h"//初始化隊列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}//銷毀隊列
void QueueDestroy(Queue* pq)
{assert(pq);//遍歷刪除QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);}pq->head = pq->tail = NULL;
}//隊尾入隊列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//開辟新節(jié)點QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{//節(jié)點的數(shù)據(jù)復(fù)制為x，指針置為空newnode->data = x;newnode->next = NULL;}//空隊列在隊列頭部if (pq->head == NULL){pq->head = pq->tail = newnode;}else{//尾指針后移pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}//對頭出隊列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));  //隊列為空時不能出隊列//只有一個元素的時候，出隊列之后，頭尾指針都置為空if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;}pq->size--;
}//獲取對頭元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//獲取隊尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}//判斷隊列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}//返回隊列元素個數(shù)
int QueueSize(Queue* pq)
{assert(pq);/*int count = 0;QNode* cur = pq->head;while (cur){cur = cur->next;count++;}return count;*/return pq->size;
}