【C语言/数据结构】二叉树（层序遍历|判断完全二叉树|性质）

个人主页：秦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;}//节点个数intQueueSize(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.