前言：二叉樹的實現(xiàn)方式多種多樣，有數(shù)組實現(xiàn)滿二叉樹，有鏈表實現(xiàn)完全二叉樹，今天我們就用隊列來實現(xiàn)二叉樹。

創(chuàng)建二叉樹：

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}TreeNode;

層序遍歷：

void LevelOrder(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q)){// 一層一層出while (levelSize--){TreeNode* 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);
}

我們的隊列是用來存放二叉樹節(jié)點的，所以我們的目的是將節(jié)點一層一層的遍歷出來，所以我們的第一層是根節(jié)點，我們把它放入隊列，出隊列的時候就要帶它的左子樹和右子樹節(jié)點進入隊列，那么我們怎么知道每層的節(jié)點數(shù)呢？我們定義一個levelSize，初始值為1。

我們的levelSize是每層的節(jié)點個數(shù)，我們的節(jié)點個數(shù)因為在隊列中，所以我們的個數(shù)就等于隊列的數(shù)據(jù)個數(shù)，即levelSize = QueueSize(&q)，我們通過循環(huán)讓節(jié)點一層一層的出隊列打印出來就達(dá)到了我們的目的。整個過程如下圖所示：

判斷二叉樹是否是完全二叉樹：

bool TreeComplete(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}// 前面遇到空以后，后面還有非空就不是完全二叉樹while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

我們這里同樣按照節(jié)點的順序給它入隊列和出隊列，我們的levelSize控制每一層的數(shù)據(jù)，我們的根節(jié)點出隊列就將它的左子樹和右子樹帶入隊列，如果中間有一個子樹為空那么就退出循環(huán)，但是我們后面如果還有不為空的節(jié)點，也就是不連續(xù)的話，那么就不是完全二叉樹。

我們拿到2的左子樹3后，出隊列，再拿2的右子樹，2的右子樹為空所以就結(jié)束循環(huán)，我們在到隊列里面取隊列首元素，再出隊列，隊列的元素不為空，說明二叉樹不連續(xù)，所以該樹就不是，完全二叉樹，反之就是完全二叉樹。

如果對大家有幫助的話就支持一下吧！感謝大家的支持！