C语言编程之完全二叉树的层序遍历

#include<stdio.h> #include<stdlib.h> #include<assert.h> #include"Queue.h" typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail\n"); return NULL; } node->data = x; node->left = node->right = NULL; return node; } BTNode* CreateBinaryTree() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; } //层序遍历 void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { 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"); QueueDestroy(&q); } //判断完全二叉树 bool BTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } //该循环作用就是找到空节点 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,说明第一个空节点之后的节点均为空节点~ return true; } int main() { BTNode* root = CreateBinaryTree(); LevelOrder(root); printf("%d", BTreeComplete(root)); }