🌈个人主页：秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏：《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482
目录
层序遍历
层序遍历函数实现
判断二叉树是否为完全二叉树
二叉树性质
前言
💬 hello! 各位铁子们大家好哇。
今日更新了树的层序，判断完全二叉树相关内容
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
层序遍历
层序遍历需要用到队列的思想。
这里先给出要用的队列相关函数
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//插入
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
pq->ptail = pq->phead = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
//删除
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->phead);
QNode* del = pq->phead;
pq->phead = pq->phead->next;
free(del);
del = NULL;
if (pq->phead == NULL)
{
pq->ptail = NULL;
}
pq->size--;
}
//取队头
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
//判断是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
//节点个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}队列的声明
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
注意：第一行typedef的是节点的指针。因为队列里存放二叉树的节点的指针时，我们才可以通过节点的指针找到下一个节点。
层序遍历函数实现
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
int levelSize = 1;
while (!QueueEmpty(&q))
{
// 一层一层出
while (levelSize--)
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
printf("\n");
levelSize = QueueSize(&q);
}
printf("\n");
QueueDestroy(&q);
}
分析：将根结点push进队列，然后取队头，打印，删队头。再把该节点的两个子节点push进队列。如此循环，直到队列为空。Pop删除时，我们free掉的是队列的Node，不是树的Node，二者不会相互影响。取队头时，返回值是队列里节点的值，这个值就是树的节点的指针。levelSize控制一层一层出，打印出来的效果是一层一层的。某一层打印结束时，levelSize更新为队列里的节点个数，如此循环，就能一层一层打印。
判断二叉树是否为完全二叉树
函数实现
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
int levelSize = 1;
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
break;
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
// 前面遇到空以后，后面还有非空就不是完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}分析：前面的过程与层序相似，只不过在遇到空时，就结束循环。接着来到第二个while循环，当遇到非空时，if语句执行，就会直接返回false。如果后面都是空，if语句就不执行，最后就会返回true。
二叉树性质
这里分析第3个，其余在前几篇博客已说明。（n0表示度为0，n2表示度为2）
分析：第3个的意思是，度为0的节点的个数是度为2的节点个数+1。
当只有一个节点时，n0为1个，n2为0个。增加一个节点，减少一个n0，增加一个n0，所以n0不变。再如下图所示，再增加一个节点，n2就变为1个，n0也会增加1个，但是n1就会减少。因此有关系：n0=n2+1.文章来源：https://www.toymoban.com/news/detail-821328.html
文章来源地址https://www.toymoban.com/news/detail-821328.html
到了这里，关于【C语言/数据结构】二叉树（层序遍历|判断完全二叉树|性质）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
