层序遍历
层序遍历需要用到队列的思想。
这里先给出要用的队列相关函数
//初始化 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.
