?🌈个人主页:秦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.
?