目錄

鏈?zhǔn)蕉鏄涫疽鈭D?編輯

何為層序遍歷

手搓一個(gè)鏈?zhǔn)蕉鏄?/p>

實(shí)現(xiàn)層序遍歷鏈?zhǔn)蕉鏄?

鏈?zhǔn)蕉鏄涫疽鈭D

何為層序遍歷

和前中后序遍歷不同，前中后序遍歷鏈?zhǔn)蕉鏄湫枰眠f歸才能遍歷
而層序遍歷是非遞歸的形式，如上圖：層序遍歷的結(jié)果：1，2，4，3，5，6

手搓一個(gè)鏈?zhǔn)蕉鏄?/h2>

代碼演示（以上圖為例）：

// 數(shù)據(jù)類型
typedef int BTDataType;// 二叉樹節(jié)點(diǎn)的結(jié)構(gòu)
typedef struct BinaryTreeNode
{BTDataType data; //每個(gè)節(jié)點(diǎn)的數(shù)據(jù)struct BinaryTreeNode* left; //指向左子樹的指針struct BinaryTreeNode* right; //指向右子樹的指針
}BTNode;// 申請新節(jié)點(diǎn)
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));// 判斷是否申請成功if (newnode == NULL){perror("malloc fail");return NULL;}// 初始化newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* CreatBinaryTree()
{BTNode* n1 = BuyNode(1);assert(n1);BTNode* n2 = BuyNode(2);assert(n2);BTNode* n3 = BuyNode(3);assert(n3);BTNode* n4 = BuyNode(4);assert(n4);BTNode* n5 = BuyNode(5);assert(n5);BTNode* n6 = BuyNode(6);assert(n6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return n1;
}

---

實(shí)現(xiàn)層序遍歷鏈?zhǔn)蕉鏄?/h2>

實(shí)現(xiàn)思路：

利用隊(duì)列的先進(jìn)先出的性質(zhì)，實(shí)現(xiàn)層序遍歷鏈?zhǔn)蕉鏄?br /> 如上圖所示：先將 1 節(jié)點(diǎn)入隊(duì)列，再將 1 節(jié)點(diǎn)出隊(duì)列，在?1 節(jié)點(diǎn)出隊(duì)列的時(shí)候，把 2、4 節(jié)點(diǎn)帶入隊(duì)列，2 節(jié)點(diǎn)再出隊(duì)列，2 節(jié)點(diǎn)出隊(duì)列的時(shí)候，把 3 節(jié)點(diǎn)帶入隊(duì)列，然后就是 4 節(jié)點(diǎn)出隊(duì)列，同樣出隊(duì)列的時(shí)候，將 5、6 節(jié)點(diǎn)帶入隊(duì)列，最后再依次出隊(duì)列，所有數(shù)據(jù)出完隊(duì)列后，根據(jù)出隊(duì)列的順序，就是層序遍歷的順序

實(shí)現(xiàn)前要先構(gòu)建一個(gè)簡易隊(duì)列以及隊(duì)列的基本函數(shù)：

// 數(shù)據(jù)類型
typedef BTNode* QDataType;// 鏈?zhǔn)疥?duì)列每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)
typedef struct QueueNode
{struct QueueNode* next; //指向下一個(gè)節(jié)點(diǎn)的指針QDataType data; //當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
}QNode;// 鏈?zhǔn)疥?duì)列的結(jié)構(gòu)
typedef struct Queue
{QNode* phead; //指向隊(duì)頭節(jié)點(diǎn)的指針QNode* ptail; //指向隊(duì)尾節(jié)點(diǎn)的指針int size; //隊(duì)列的總數(shù)據(jù)個(gè)數(shù)
}Queue;// 初始化隊(duì)列
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}// 數(shù)據(jù)入隊(duì)列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);// 申請新節(jié)點(diǎn)QNode* newnode = (QNode*)malloc(sizeof(QNode));// 判斷是否申請成功if (newnode == NULL){perror("malloc fail");return;}// 初始化新節(jié)點(diǎn)newnode->data = x;newnode->next = NULL;if (pq->phead == NULL) //當(dāng)隊(duì)列中沒有數(shù)據(jù)的情況{// 雙重判斷，更加保險(xiǎn)assert(pq->ptail == NULL);// 頭尾都指向新節(jié)點(diǎn)即可pq->phead = newnode;pq->ptail = newnode;}else //當(dāng)隊(duì)列已有數(shù)據(jù)的情況{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}// 數(shù)據(jù)出隊(duì)列
void QueuePop(Queue* pq)
{assert(pq);// 當(dāng)隊(duì)列中沒有數(shù)據(jù)的情況if (pq->phead == NULL){perror(pq->phead);return;}if (pq->phead->next == NULL) //當(dāng)隊(duì)列中只有一個(gè)數(shù)據(jù)的情況{free(pq->phead);pq->phead = NULL;pq->ptail = NULL;}else //當(dāng)隊(duì)列中有多個(gè)數(shù)據(jù)的情況{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}// 訪問隊(duì)頭數(shù)據(jù)
QDataType QueueFront(Queue* pq)
{assert(pq);// 當(dāng)隊(duì)列中沒有數(shù)據(jù)的情況if (pq->phead == NULL){perror(pq->phead);return -1;}return pq->phead->data;
}// 判斷隊(duì)列是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return (pq->phead == NULL) && (pq->ptail == NULL);
}// 釋放隊(duì)列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur != NULL){QNode* next = cur->next;free(cur);cur = next;}pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}

在定義隊(duì)列數(shù)據(jù)時(shí)，需要定義鏈?zhǔn)蕉鏄涔?jié)點(diǎn)的指針，這樣才能找到二叉樹節(jié)點(diǎn)的左右子樹

代碼實(shí)現(xiàn)：

void LevelOrder(BTNode* root)
{// 定義隊(duì)列Queue q;// 初始化隊(duì)列QueueInit(&q);// 先將二叉樹的根節(jié)點(diǎn)的指針入隊(duì)列if (root != NULL)QueuePush(&q, root);while (!QueueEmpty(&q)){// 訪問隊(duì)頭數(shù)據(jù)BTNode* front = QueueFront(&q);printf("%d ", front->data);// 隊(duì)頭數(shù)據(jù)出隊(duì)列QueuePop(&q);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");
}

代碼解析：

當(dāng)隊(duì)列為空時(shí)，鏈?zhǔn)蕉鏄涞膶有虮闅v就實(shí)現(xiàn)了
但最開始隊(duì)列沒有數(shù)據(jù)，所以要先將指向根節(jié)點(diǎn)的指針存放入隊(duì)列
且存放節(jié)點(diǎn)指針是為了方便查找左右子樹
然后在利用 while 循環(huán)，只要隊(duì)列不為空，就循環(huán)下去
先訪問隊(duì)頭的數(shù)據(jù)，隊(duì)頭的數(shù)據(jù)就是鏈?zhǔn)蕉鏄涔?jié)點(diǎn)的指針
所以使用 BTNode* front 來接收，再利用 printf 函數(shù)打印指針?biāo)赶蚬?jié)點(diǎn)中的數(shù)據(jù)
再把隊(duì)頭數(shù)據(jù)出隊(duì)列，并且把出隊(duì)列那個(gè)節(jié)點(diǎn)的左右子樹存放入隊(duì)列
注意為空時(shí)就不要放入隊(duì)列，所以每次放入隊(duì)列前要判斷是否為空
直到隊(duì)列為空時(shí)，也就是不滿足 while 循環(huán)時(shí)，層序遍歷就實(shí)現(xiàn)了

此代碼的關(guān)鍵是利用?BTNode* front 接收每次要出隊(duì)列的節(jié)點(diǎn)指針，這樣就方便查找當(dāng)前節(jié)點(diǎn)的左右子樹，并且利用?BTNode* front 接收從而替代了遞歸邏輯

代碼驗(yàn)證：