大秦建设集团有限责任公司官方网站,有什么免费的网站,庆阳字体设计,哪家网站做推广好欢迎来到我的#xff1a;世界
希望作者的文章对你有所帮助#xff0c;有不足的地方还请指正#xff0c;大家一起学习交流 ! 目录 前言队列的实现层序遍历详解强化练习1.判断是不是完全二叉树求二叉树的最大深度 总结 前言
国庆到了#xff0c;也要内卷一下#xff0c;感…
欢迎来到我的世界
希望作者的文章对你有所帮助有不足的地方还请指正大家一起学习交流 ! 目录 前言队列的实现层序遍历详解强化练习1.判断是不是完全二叉树求二叉树的最大深度 总结 前言
国庆到了也要内卷一下感谢所以老铁们的支持 队列的实现 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(rootNULL)return 0;int leftmaxDepth(root-left);int rightmaxDepth(root-right);return leftright?left1:right1;
}如果你知道一个函数fmax那就更简单了该函数就是用来求两个值返回大的那一个 代码实现
int maxDepth(struct TreeNode* root){if(rootNULL)return 0;return fmax(maxDepth(root-left),maxDepth(root-right))1;}总结 到了最后感谢支持
我还想告诉你的是 ------------对过程全力以赴对结果淡然处之 也是对我自己讲的
