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

創(chuàng)建二叉樹(shù)：

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);
}

我們的隊(duì)列是用來(lái)存放二叉樹(shù)節(jié)點(diǎn)的，所以我們的目的是將節(jié)點(diǎn)一層一層的遍歷出來(lái)，所以我們的第一層是根節(jié)點(diǎn)，我們把它放入隊(duì)列，出隊(duì)列的時(shí)候就要帶它的左子樹(shù)和右子樹(shù)節(jié)點(diǎn)進(jìn)入隊(duì)列，那么我們?cè)趺粗烂繉拥墓?jié)點(diǎn)數(shù)呢？我們定義一個(gè)levelSize，初始值為1。

我們的levelSize是每層的節(jié)點(diǎn)個(gè)數(shù)，我們的節(jié)點(diǎn)個(gè)數(shù)因?yàn)樵陉?duì)列中，所以我們的個(gè)數(shù)就等于隊(duì)列的數(shù)據(jù)個(gè)數(shù)，即levelSize = QueueSize(&q)，我們通過(guò)循環(huán)讓節(jié)點(diǎn)一層一層的出隊(duì)列打印出來(lái)就達(dá)到了我們的目的。整個(gè)過(guò)程如下圖所示：

判斷二叉樹(shù)是否是完全二叉樹(shù)：

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);}// 前面遇到空以后，后面還有非空就不是完全二叉樹(shù)while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

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

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

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