C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的遍歷
前言：
學(xué)習(xí)二叉樹的基本操作前，需要先創(chuàng)建一顆二叉樹，然后才能學(xué)習(xí)其相關(guān)的基本操作，考慮到我們剛剛接觸二叉樹，為了能夠先易后難地進(jìn)行講解，我們將暫時手動創(chuàng)建一顆簡單的二叉樹，用來方便大家學(xué)習(xí)。等二叉樹結(jié)構(gòu)了解的差不多后，后期我們會帶大家研究二叉樹地真正的創(chuàng)建方式。
Ⅰ. 定義二叉樹
0x00 二叉樹的概念（回顧）
我們之前講過二叉樹的概念了，這里我們簡單的回顧下二叉樹的概念。
?? 復(fù)習(xí)鏈接：C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的概念及滿二叉樹與完全二叉樹
? 二叉樹是什么？① 空樹 ② 非空：根節(jié)點、根節(jié)點的左子樹與根節(jié)點的又子樹組成的。
?? 解讀：從概念中我們不難看出，二叉樹的定義是遞歸式的。因此后續(xù)基本操作中，我們基本都是按照該概念來實現(xiàn)的！我們可以來看一下，我們不去看 A，我們來看 A 的左子樹，把 B 看作為根節(jié)點，是不是一顆二叉樹？
?? 所以，我們可以通過采用遞歸的手法來玩二叉樹。
0x00 定義二叉樹
?? BinaryTree.h：
typedef int BTDataType;
typedef struct BinaryTreeNode {
struct BinaryTreeNode* left; // 記錄左節(jié)點
struct BinaryTreeNode* right; // 記錄右節(jié)點
BTDataType data; // 存儲數(shù)據(jù)
} BTNode; ?? 解讀：
① 還是老規(guī)矩，我們創(chuàng)建一個二叉樹的數(shù)據(jù)類型 BTDataType 。
② 由于是鏈?zhǔn)蕉鏄?，根?jù)二叉樹的概念我們定義出 left 和 right 來分別記錄根節(jié)點的左子樹與根節(jié)點的右子樹，再創(chuàng)建一個變量來存儲節(jié)點中的數(shù)據(jù)即可。
③ 最后為了方便表達(dá)，我們將這個結(jié)構(gòu)體 typedef 為 BTNode，因為 "struct BinaryTreeNode" 比較麻煩。
0x01 手動創(chuàng)建二叉樹
在學(xué)習(xí)二叉樹的基本操作前，需要先創(chuàng)建一顆二叉樹，然后才能學(xué)習(xí)其相關(guān)的基本操作。由于我們剛剛接觸二叉樹，為了能夠先易后難地學(xué)習(xí)，我們手動創(chuàng)建一顆簡單的二叉樹來來方便大家學(xué)習(xí)。等二叉樹結(jié)構(gòu)了解后，后期我們會帶著讀者研究二叉樹地真正的創(chuàng)建方式。
?? 手動創(chuàng)建一顆二叉樹（以上圖為例來創(chuàng)建）
/* 創(chuàng)建新節(jié)點 */
BTNode* BuyNode(BTDataType x) {
BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));
if (new_node == NULL) {
printf("malloc failed!\n");
exit(-1);
}
new_node->data = x;
new_node->left = new_node->right = NULL;
return new_node;
}
/* 手動創(chuàng)建二叉樹 */
BTNode* CreateBinaryTree() {
BTNode* nodeA = BuyNode('A');
BTNode* nodeB = BuyNode('B');
BTNode* nodeC = BuyNode('C');
BTNode* nodeD = BuyNode('D');
BTNode* nodeE = BuyNode('E');
BTNode* nodeF = BuyNode('F');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
nodeC->right = nodeF;
return nodeA;
}
int main(void)
{
BTNode* root = CreateBinaryTree();
}?? 畫圖解析：
Ⅱ. 二叉樹的遍歷
0x00 關(guān)于遍歷
學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂二叉樹遍歷，就是按照某種特定的規(guī)則，一次對二叉樹中的節(jié)點進(jìn)行相應(yīng)的操作，并且每個節(jié)點只操作一次。 訪問節(jié)點所做的操作要看具體的應(yīng)用問題。遍歷是二叉樹上最重要的運算之一，也是二叉樹上進(jìn)行其他運算的基礎(chǔ)。
?? 二叉樹遍歷（Traversal）：沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。 按照規(guī)則，二叉樹的遍歷有：前序 / 中序 / 后序 的遞歸結(jié)構(gòu)遍歷。除了前序、中序和后續(xù)遍歷外，我們還可以對二叉樹進(jìn)行層序遍歷。
0x01 二叉樹前序遍歷
?? 前序遍歷（Preorder Traversal）：訪問根節(jié)點的操作發(fā)生在遍歷其右子樹之前。
即，首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。
?? 代碼實現(xiàn)前序遍歷：
（這里我們用 Ø 符號來表示 NULL）
/* 二叉樹前序遍歷 */
void PreOrder(BTNode* root) {
/* 首先判斷根是否為空，為空就返回 */
if (root == NULL) {
printf("? "); // 暫時打印出來，便于觀察
return;
}
/* 走到這里說明不為空，根據(jù)前序遍歷，先訪問根節(jié)點 */
printf("%c ", root->data);
/* 然后遍歷左子樹（利用遞歸） */
PreOrder(root->left);
/* 最后遍歷右子樹（利用遞歸） */
PreOrder(root->right);
}?? 解讀：
① 首先判斷根是否為空，如果根為空，則返回。這里為了表示，我們把空節(jié)點以 " Ø " 打印出來。
② 如果跟不為空，這說明有數(shù)據(jù)。由于是前序遍歷（Preorder），前序遍歷是先訪問根節(jié)點，然后遍歷左子樹，最后再遍歷右子樹。所以，我們這里先要訪問的是根節(jié)點，我們把根節(jié)點的數(shù)據(jù)打印出來。
③ 然后我們需要遍歷左子樹，這時我們利用遞歸就可以實現(xiàn)。將根節(jié)點 root 的左數(shù) left 傳入 PreOrder 函數(shù)（將其左樹看作根），一直遞歸下去，直到碰到 root == NULL 則返回。
④ 最后，遍歷完左子樹后遍歷右子樹。利用遞歸，方法同上。
0x02 二叉樹中序遍歷
?? 中序遍歷（Inorder Traversal）：訪問根節(jié)點的操作發(fā)生在遍歷其左右子樹之中。
即，首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。
/* 二叉樹中序遍歷 */
void InOrder(BTNode* root) {
/* 首先判斷根是否為空，為空就返回 */
if (root == NULL) {
printf("? "); // 暫時打印出來，便于觀察
return;
}
/* 走到這里說明不為空，根據(jù)中序遍歷，先遍歷左子樹 */
InOrder(root->left);
/* 然后訪問根節(jié)點（利用遞歸） */
printf("? ", root->data);
/* 最后遍歷右子樹（利用遞歸） */
InOrder(root->right);
}?? 解讀：
① 首先判斷根是否為空，如果根為空，則返回。
② 如果跟不為空，這說明有數(shù)據(jù)。由于是中序遍歷（Inorder），中序遍歷是先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹。
0x03 二叉樹后序遍歷
?? 后序遍歷（Postorder Traversal）：訪問根節(jié)點的操作發(fā)生在遍歷其左右子樹之后。
即，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。
/* 二叉樹后序遍歷 */
void PostOrder(BTNode* root) {
/* 首先判斷根是否為空，為空就返回 */
if (root == NULL) {
printf("/ ");
return;
}
/* 走到這里說明不為空，根據(jù)后序遍歷，先遍歷左子樹（利用遞歸） */
PostOrder(root->left);
/* 然后遍歷右子樹（利用遞歸） */
PostOrder(root->right);
/* 最后訪問根節(jié)點 */
printf("%c ", root->data);
}?? 解讀：
① 首先判斷根是否為空，如果根為空，則返回。
② 如果跟不為空，這說明有數(shù)據(jù)。由于是后序遍歷（Postorder），后序遍歷是先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點。
0x04 層序遍歷
?? 層序遍歷（Level Traversal）：設(shè)二叉樹的根節(jié)點所在的層數(shù)為1的情況下，從二叉樹的根節(jié)點出發(fā)，首先訪問第1層的樹根節(jié)點，然后再從左到右訪問第2層上的節(jié)點。接著是第3層的節(jié)點……以此類推，自上而下、從左向右地逐層訪問樹的節(jié)點。
? 該如何實現(xiàn)層序遍歷呢？
?? 我們可以利用隊列的性質(zhì)來實現(xiàn)！
我們之前再講過隊列，這里你可以選擇自己實現(xiàn)一個隊列。如果不想實現(xiàn)就直接 CV 即可，因為我們這里重點要學(xué)的是層序遍歷！
?? 鏈接：C語言數(shù)據(jù)結(jié)構(gòu)系列隊列篇
?? Queue.h：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int QueueDataType;
typedef struct QueueNode {
struct QueueNode* next;
QueueDataType data;
} QueueNode;
typedef struct Queue {
QueueNode* pHead;
QueueNode* pTail;
} Queue;
void QueueInit(Queue* pQ); //隊列初始化
void QueueDestroy(Queue* pQ); //銷毀隊列
bool QueueIfEmpty(Queue* pQ); //判斷隊列是否為空
void QueuePush(Queue* pQ, QueueDataType x); //入隊
void QueuePop(Queue* pQ); //出隊
QueueDataType QueueFront(Queue* pQ); //返回隊頭數(shù)據(jù)
QueueDataType QueueBack(Queue* pQ); //返回隊尾數(shù)據(jù)
int QueueSize(Queue* pQ); //求隊列大小?? Queue.c：
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
/* 隊列初始化 */
void QueueInit(Queue* pQ) {
assert(pQ);
pQ->pHead = pQ->pTail = NULL;
}
/* 銷毀隊列 */
void QueueDestroy(Queue* pQ) {
assert(pQ);
QueueNode* cur = pQ->pHead;
while (cur != NULL) {
QueueNode* cur_next = cur->next;
free(cur);
cur = cur_next;
}
pQ->pHead = pQ->pTail = NULL;
}
/* 判斷隊列是否為空 */
bool QueueIfEmpty(Queue* pQ) {
assert(pQ);
return pQ->pHead == NULL;
}
/* 入隊 */
QueueNode* CreateNewNode(QueueDataType x) {
QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
if (new_node == NULL) {
printf("malloc failed!\n");
exit(-1);
}
new_node->data = x;
new_node->next = NULL;
return new_node;
}
void QueuePush(Queue* pQ, QueueDataType x) {
assert(pQ);
QueueNode* new_node = CreateNewNode(x);
if (pQ->pHead == NULL) {
pQ->pHead = pQ->pTail = new_node;
}
else {
pQ->pTail->next = new_node;
pQ->pTail = new_node;
}
}
/* 出隊 */
void QueuePop(Queue* pQ) {
assert(pQ);
assert(!QueueIfEmpty(pQ));
QueueNode* save_next = pQ->pHead->next;
free(pQ->pHead);
pQ->pHead = save_next;
if (pQ->pHead == NULL) {
pQ->pTail = NULL;
}
}
/* 返回隊頭數(shù)據(jù) */
QueueDataType QueueFront(Queue* pQ) {
assert(pQ);
assert(!QueueIfEmpty(pQ));
return pQ->pHead->data;
}
/* 返回隊尾數(shù)據(jù) */
QueueDataType QueueBack(Queue* pQ) {
assert(pQ);
assert(!QueueIfEmpty(pQ));
return pQ->pTail->data;
}
/* 求隊列大小 */
int QueueSize(Queue* pQ) {
assert(pQ);
int count = 0;
QueueNode* cur = pQ->pHead;
while (cur != NULL) {
count++;
cur = cur->next;
}
return count;
}這里為了方便講解 #include "展開" 的特點，我們把樹的定義放到 test.c 中，并且在 test.c 里完成層序遍歷。
?? test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
typedef char BTDataType;
typedef struct BinaryTreeNode {
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
} BTNode;
//#include "Queue.h" 解決方案？
/* 創(chuàng)建新節(jié)點 */
BTNode* BuyNode(BTDataType x) {
BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));
if (new_node == NULL) {
printf("malloc failed!\n");
exit(-1);
}
new_node->data = x;
new_node->left = new_node->right = NULL;
return new_node;
}
/* 手動創(chuàng)建二叉樹 */
BTNode* CreateBinaryTree() {
BTNode* nodeA = BuyNode('A');
BTNode* nodeB = BuyNode('B');
BTNode* nodeC = BuyNode('C');
BTNode* nodeD = BuyNode('D');
BTNode* nodeE = BuyNode('E');
BTNode* nodeF = BuyNode('F');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
nodeC->right = nodeF;
return nodeA;
}由于是我們的數(shù)據(jù)類型是 BTNode，我們需要修改一下 Queue.h 的 QueueDataType，我們之前一直強調(diào)的 typedef 的好處，這里就顯現(xiàn)出來了。我們只需要把 int 改成 BTNode 就可以了，而不需要改很多地方。
?? Queue.h：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef BTNode* QueueDataType;
typedef struct QueueNode {
struct QueueNode* next;
QueueDataType data;
} QueueNode;
typedef struct Queue {
QueueNode* pHead;
QueueNode* pTail;
} Queue;
void QueueInit(Queue* pQ); //隊列初始化
void QueueDestroy(Queue* pQ); //銷毀隊列
bool QueueIfEmpty(Queue* pQ); //判斷隊列是否為空
void QueuePush(Queue* pQ, QueueDataType x); //入隊
void QueuePop(Queue* pQ); //出隊
QueueDataType QueueFront(Queue* pQ); //返回隊頭數(shù)據(jù)
QueueDataType QueueBack(Queue* pQ); //返回隊尾數(shù)據(jù)
int QueueSize(Queue* pQ); //求隊列大小這時我們運行一下代碼會出現(xiàn)一個問題，我們發(fā)現(xiàn)它報錯了：
它說，缺少 " { " ，這明顯是胡說八道的，咱編譯器也沒有那么只能，畢竟是也不是VS2077。
? 這里產(chǎn)生問題的原因是什么呢？
?? 編譯器原則：編譯器認(rèn)識 int，因為 int 是一個內(nèi)置類型。但是 BTNode* 編譯器并不認(rèn)識，就需要 "往上面" 去找這個類型。這里顯然往上找，是找不到它的定義的，所以編譯器會報錯。
如果你要用這個類型，你就需要先定義這個類型。test.c文件中 #include "Queue.h" ，相當(dāng)于把這里的代碼拷貝過去了。這時，由于BTNode*會在上面展開，導(dǎo)致找不到 BTNode* 。
? 我把 #include 移到 定義類型的代碼 的后面，可以解決問題嗎？
可以！遺憾的是只能解決這里 typedef BTNode* 的問題，還有 Queue.c 里的問題……
那我們該怎么做，能徹底解決呢？
?? 解決方案：前置聲明。 這樣就不會帶來問題了，滿足了先聲明后使用。
?? Queue.h （修改后）：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
// 前置聲明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QueueDataType;
typedef struct QueueNode {
struct QueueNode* next;
QueueDataType data;
} QueueNode;
typedef struct Queue {
QueueNode* pHead;
QueueNode* pTail;
} Queue;
void QueueInit(Queue* pQ); //隊列初始化
void QueueDestroy(Queue* pQ); //銷毀隊列
bool QueueIfEmpty(Queue* pQ); //判斷隊列是否為空
void QueuePush(Queue* pQ, QueueDataType x); //入隊
void QueuePop(Queue* pQ); //出隊
QueueDataType QueueFront(Queue* pQ); //返回隊頭數(shù)據(jù)
QueueDataType QueueBack(Queue* pQ); //返回隊尾數(shù)據(jù)
int QueueSize(Queue* pQ); //求隊列大小似乎有些扯遠(yuǎn)了，這塊在《維生素C語言》中沒有詳細(xì)的說，所以這里還是需要說一下的。解決了這個報錯的問題后，我們就可以正式開始寫層序遍歷了。
?? 思路如下：
① 讓根節(jié)點先入隊。
② 記錄當(dāng)前隊頭后打印，并讓隊頭出隊，然后檢測，如過孩子不為空就把孩子帶進(jìn)去。
（上一層節(jié)點出隊時帶入下一層節(jié)點入隊）
③ 只要隊列不為空就說明還沒完。如果隊列為空，說明下面最后一層沒有節(jié)點，遍歷結(jié)束。
?? 注意事項：使用完隊列后別忘了要銷毀！
?? 代碼實現(xiàn)：
void BinaryTreeLevelOrder(BTNode* root) {
if (root == NULL) { // 判斷根是否為空
return;
}
Queue pQ; // 建立隊列
QueueInit(&pQ); // 初始化隊列
QueuePush(&pQ, root); // 先讓根進(jìn)入隊列
while (!QueueIfEmpty(&pQ)) { // 只要隊列內(nèi)還有元素，就進(jìn)入循環(huán)
BTNode* front = QueueFront(&pQ); // 記錄當(dāng)前對頭數(shù)據(jù)
printf("%c ", front->data); // 打印隊頭數(shù)據(jù)
QueuePop(&pQ); // 當(dāng)隊頭出隊
if (front->left != NULL) { // 如果隊頭元素的左子樹不為空
QueuePush(&pQ, front->left); // 讓左子樹進(jìn)入隊列
}
if (front->right != NULL) { // 如果對頭元素的右子樹不為空
QueuePush(&pQ, front->right); // 讓右子樹進(jìn)入隊列
}
}
QueueDestroy(&pQ); // 銷毀隊列
}?? 解讀：
① 首先判斷根是否為空，如果為空就沒有必要往下走了。
② 建立和初始化隊列后，首先讓根節(jié)點進(jìn)入隊列。只要隊列內(nèi)還有元素存在（說明還沒遍歷完）就進(jìn)入循環(huán)。每次循環(huán)進(jìn)入后都記錄一下當(dāng)前隊頭，這里使用 QueueFront 取隊頭數(shù)據(jù)即可。之后打印對頭的數(shù)據(jù)。
③ 打印完后讓隊頭出隊，隨后判斷它的左子樹和右子樹，如果不為空就允許它們進(jìn)隊。我們先判斷 left，再判斷 right，這樣就可以做到一層一層從左往右走的效果了。
④ 最后使用完隊列后，別忘了銷毀隊列！
參考資料：
Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .
百度百科[EB/OL]. []. https://baike.baidu.com/.
?? 筆者：王亦優(yōu)
?? 更新： 2022.1.12
? 勘誤： 無
?? 聲明： 由于作者水平有限，本文有錯誤和不準(zhǔn)確之處在所難免，本人也很想知道這些錯誤，懇望讀者批評指正！
本篇完。
到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)系列篇二叉樹的遍歷的文章就介紹到這了,更多相關(guān)C語言 二叉樹遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言實現(xiàn)字符串轉(zhuǎn)浮點函數(shù)的示例
字符串不僅可以轉(zhuǎn)換為整數(shù)，也可以轉(zhuǎn)換為浮點數(shù)，本文主要介紹了C語言實現(xiàn)字符串轉(zhuǎn)浮點函數(shù)的示例，具有一定的參考價值，感興趣的可以了解一下2022-02-02
這篇文章主要為大家詳細(xì)介紹了基于c++ ege圖形庫實現(xiàn)五子棋游戲，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-12-12
C++實現(xiàn)LeetCode(692.前K個高頻詞)
這篇文章主要介紹了C++實現(xiàn)LeetCode(692.前K個高頻詞),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
這里我們不涉及容器的基本操作之類，只是要討論一下各個容器其各自的特點STL中的常用容器包括：順序性容器（vector、deque、list）、關(guān)聯(lián)容器（map、set）、容器適配器（queue、stac）2013-09-09
法是程序的靈魂,無論學(xué)習(xí)什么語言,做什么工程項目,都要考慮算法的效率實現(xiàn),下面這篇文章主要給大家介紹了關(guān)于C++實現(xiàn)十大排序算法及排序算法常見問題的相關(guān)資料,需要的朋友可以參考下2021-09-09
詳解c語言實現(xiàn)的內(nèi)存池(適用于兩個線程、不加鎖、效率高)
這篇文章主要介紹了c語言實現(xiàn)的內(nèi)存池（適用于兩個線程、不加鎖、效率高）,設(shè)計一個內(nèi)存池，要求效率比系統(tǒng)調(diào)用的效率要高（測試1萬次），同時支持一個線程申請，另外一個線程釋放，需要的朋友可以參考下2024-02-02
這篇文章主要介紹了C語言 指針的初始化賦值案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
C++?Boost?MultiArray簡化使用多維數(shù)組庫
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴展的一些C++程序庫的總稱2022-11-11
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)高校教室管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了C語言中qsort函數(shù)的用法實例詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家理解掌握這部分內(nèi)容，需要的朋友可以參考下2021-08-08