欢迎来到我的：世界

希望作者的文章对你有所帮助，有不足的地方还请指正，大家一起学习交流 !

---

前言

国庆到了，也要内卷一下，感谢所以老铁们的支持！😎

---

队列的实现

1、队列的定义
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头；

队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。
空队列：不包含任何元素的空表。

链式队列存储类型：

typedef int QDatatype;
typedef struct QueueNode
{QDatatype val;//记录每个节点的值struct QueueNode* next;//下一个节点
}QueueNode;typedef struct Queue
{QueueNode* head;//队列的头指针QueueNode* tail;//队列的尾指针int size;//记录队列的元素个数，开始为0；
}Queue;

队列的常见基本操作：

//初始化队列，构造一个空队列pd。
void QueueInit(Queue* pd);
//清除队列，将队列清除，以免空间泄露
void Queuedestroy(Queue* pd);
//入队，若队列pd未满，将x加入，使之成为新的队尾。
void Queuepush(Queue* pd, QDatatype x);
//出队，若队列pd非空，删除队头元素。
void QueuePop(Queue* pd);
//读取队头元素值，并返回值
QDatatype QueueFront(Queue* pd);
//判队列空，若队列pd为空返回true，否则返回false。
bool QueueEmpty(Queue* pd);

链队列初始化

void QueueInit(Queue* pd)
{//构造一个空队列pd->head = pd->tail = NULL;pd->size = 0;
}

链队列入队

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++;
}

出队列，删除队头元素

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--;
}

读取队头元素

QDatatype QueueFront(Queue* pd)
{assert(pd);assert(!QueueEmpty(pd));return pd->head->val;
}

判队列空，若队列pd为空返回true，否则返回false。

bool QueueEmpty(Queue* pd)
{assert(pd);return pd->head == NULL;
}

清除队列，释放空间

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;
}

层序遍历详解

紧接上回，以层来访问，一层一层往下访问，每一层是从左往右访问;

这里用到了队列，将根节点先A存入队列中，然后再将其子节点a b存入队列，再取出根节点A，上述操作为一个循环；而后在存入上一次存入a b 他们分别的子节点，然后在取出来，依次执行操作下去，就是层序遍历；
图解：

代码实现：

void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);//队列初始化//如果根节点不为空，则将其存入队列if (root){Queuepush(&q, root);}//直到队列为空则代表遍历完成while (!QueueEmpty(&q)){BTNode* tem = QueueFront(&q);printf("%d ", tem->val);if (tem->left)//是避免NULL也存入到队列中去Queuepush(&q, tem->left);if (tem->right)//是避免NULL也存入到队列中去Queuepush(&q, tem->right);QueuePop(&q);}Queuedestroy(&q);
}

强化练习

1.判断是不是完全二叉树

---

地址：oj地址

---

解题思路：

要知道完全二叉树是一种什么样的结构：

所以这道题可以通过层序遍历的方式来解决；

可以看出：完全二叉树的非空节点是连续的，而非完全二叉树的非空节点不是连续的；可以根据这点来解决问题；

int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root){Queuepush(&q, root);}//层序遍历出最后一个叶节点，找到第一个空节点while (!QueueEmpty(&q)){BTNode* tem = QueueFront(&q);if (tem == NULL)break;//这是将空节点也存入到了队列中Queuepush(&q, tem->left);Queuepush(&q, tem->right);QueuePop(&q);}//找到了空节点，继续往下找while (!QueueEmpty(&q)){BTNode* tem = QueueFront(&q);QueuePop(&q);if (tem)//如果有一个几点不为空节点，则代表不是连续的空节点，则代表该不是完全二叉树，返回false；{Queuedestroy(&q);return false;}}//否则给该空节点是连续的，证明是完全二叉树，返回trueQueuedestroy(&q);return true;
}

求二叉树的最大深度

---

地址oj地址

---

解题思路：

树的最大深度也就是其最大的高度；求高度的一个思路：
根节点高度=其左右子节点高度高的+1；

具体代码实现：

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;
}

如果你知道一个函数fmax那就更简单了；该函数就是用来求两个值返回大的那一个；

代码实现：

int maxDepth(struct TreeNode* root){if(root==NULL)return 0;return fmax(maxDepth(root->left),maxDepth(root->right))+1;}

---

总结

---

到了最后：感谢支持

我还想告诉你的是：
------------对过程全力以赴，对结果淡然处之
也是对我自己讲的