=========================================================================
相關(guān)代碼gitee自取：
C語(yǔ)言學(xué)習(xí)日記: 加油努力 (gitee.com)
?=========================================================================
接上期：
【數(shù)據(jù)結(jié)構(gòu)初階】七、非線性表里的二叉樹(shù)（堆的實(shí)現(xiàn) -- C語(yǔ)言順序結(jié)構(gòu)）-CSDN博客
?=========================================================================
? ? ? ? ? ? ? ? ? ? ?
回顧
二叉樹(shù)的概念及結(jié)構(gòu)：
? ? ? ? ? ? ? ? ?
二叉樹(shù)的概念
一棵二叉樹(shù)是節(jié)點(diǎn)的一個(gè)有限集合，該集合滿足以下條件：
- 或者為空
- 或者由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成
? ? ? ? ? ? ? ??
二叉樹(shù)的結(jié)構(gòu)
- 二叉樹(shù)不存在度大于2的節(jié)點(diǎn)
（所以節(jié)點(diǎn)的度可能是 0 即空樹(shù)，也可能是 1 或 2?）
? ? ? ? ? ? ? ? ? ?- 二叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒，因此二叉樹(shù)是有序樹(shù)
? ? ? ? ? ? ? ? ??- 這次使用C語(yǔ)言鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)二叉樹(shù)，
要會(huì)把二叉樹(shù)分為 根、左子樹(shù) 和 右子樹(shù) ，
把 左子樹(shù)（右子樹(shù)）看成一個(gè)新的二叉樹(shù)，再把其分為?根、左子樹(shù) 和 右子樹(shù) ，
依次分類下去……圖示：
? ? ? ? ? ? ? ??
注意
對(duì)于任意二叉樹(shù)，都是由以下幾種情況復(fù)合而成：
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ??
二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（補(bǔ)充）
? ? ? ? ? ? ? ? ?
二叉樹(shù)一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，
一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)? ? ? ? ? ? ??
鏈?zhǔn)浇Y(jié)構(gòu)
- 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是指用鏈表來(lái)表示一棵二叉樹(shù)，
即用鏈來(lái)表示元素的邏輯關(guān)系
? ? ? ? ? ??- 通常的方法是：鏈表中每個(gè)節(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，
左右指針分別用來(lái)給出該節(jié)點(diǎn)左孩子和右孩子所在的鏈節(jié)點(diǎn)的存儲(chǔ)地址?
? ? ? ? ? ?- 鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，
初階數(shù)據(jù)結(jié)構(gòu)一般都是二叉鏈，高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹(shù)等會(huì)用到三叉鏈圖示：
? ? ? ? ?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
? ? ? ? ? ? ?
二叉樹(shù)的遍歷
遞歸結(jié)構(gòu)遍歷
? ? ? ? ? ? ? ? ? ?
二叉樹(shù)遍歷(Traversal)是按照某種特定的規(guī)則，
依次對(duì)二叉樹(shù)中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)只操作一次。
訪問(wèn)節(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn)題。
遍歷是二叉樹(shù)上最重要的運(yùn)算之一，也是二叉樹(shù)上進(jìn)行其它運(yùn)算的基礎(chǔ)。
? ? ? ? ? ? ? ? ? ? ? ?
- 引入一個(gè)概念 -- 深度優(yōu)先遍歷（DFS）
簡(jiǎn)單理解就是從某個(gè)位置開(kāi)始遍歷，往“深處”遍歷到無(wú)路可退再往回遍歷，
嚴(yán)格來(lái)說(shuō)，在深度優(yōu)先遍歷時(shí)是先訪問(wèn)再往“深處”走，一般配合遞歸使用
（這里前序遞歸遍歷是最符合深度優(yōu)先遍歷的）
? ? ? ? ? ? ? ? ? ? ?- 有三種遞歸遍歷方式：前序（先序）/? 中序? /??后序?
如果按照遞歸的邏輯來(lái)說(shuō)，這三種遞歸遍歷方式都算是一種深度優(yōu)先遍歷，
它們都是往“深處”遍歷，只是各自訪問(wèn)節(jié)點(diǎn)值的時(shí)機(jī)不一樣? ? ? ? ? ? ? ? ? ? ??
前序(先序)?/ 中序 / 后序 的遞歸結(jié)構(gòu)遍歷
- 前序(先序)遍歷(Preorder Traversal)——訪問(wèn)根節(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之前
[即先訪問(wèn)根節(jié)點(diǎn)，再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)]
? ? ? ? ? ? ??- 中序遍歷(Inorder Traversal)——訪問(wèn)根節(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之中（間）
[即先訪問(wèn)左子樹(shù)，再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)]
? ? ? ? ? ? ?- 后序遍歷(Postorder Traversal)——訪問(wèn)根節(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之后
[即先訪問(wèn)左子樹(shù)，再訪問(wèn)右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)]
? ? ? ? ? ? ? ? ??- 因?yàn)槲覀円?span style="color:#fe2c24;">不斷的把二叉樹(shù)分為 根、左子樹(shù) 和 右子樹(shù)?，
所以被訪問(wèn)的節(jié)點(diǎn)必是某子樹(shù)的根，
于是有：
N（Node）--? 根節(jié)點(diǎn)
L（Left subtree）--? 根的左子樹(shù)
R（Right subtree）--? 根的右子樹(shù)
再安照上面的 前序(先序) / 中序 / 后序 的遞歸結(jié)構(gòu)遍歷，又有：
NLR -- 先根(序)遍歷? ? ? ?；? ? ?LNR -- 中跟(序)遍歷? ? ? ?；? ? ?LRN -- 后根(序)遍歷前序(先序)遍歷圖示：
中序遍歷圖示：
后序遍歷圖示：
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ??
層序遍歷
? ? ? ? ? ? ? ? ? ?
- 除了先序遍歷、中序遍歷、后序遍歷外，還可以對(duì)二叉樹(shù)進(jìn)行層序遍歷
? ? ? ? ? ? ? ? ? ? ? ?- 設(shè)二叉樹(shù)的根節(jié)點(diǎn)所在層數(shù)為第?1?層，層序遍歷就是從所在二叉樹(shù)的根節(jié)點(diǎn)出發(fā)，
首先訪問(wèn)第一層的樹(shù)根節(jié)點(diǎn)，
然后訪問(wèn)左到右訪問(wèn)第 2 層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)
以此類推，自上而下，自左至右逐層訪問(wèn)樹(shù)的節(jié)點(diǎn)的過(guò)程就是層序遍歷
? ? ? ? ? ? ? ? ??- 再引入一個(gè)概念 -- 廣度優(yōu)先遍歷（BFS）
簡(jiǎn)單理解就是從當(dāng)前“層”開(kāi)始，一層一層進(jìn)行遍歷，和這里的層序遍歷相似，
因?yàn)?/span>隊(duì)列有“先進(jìn)先出”的特點(diǎn)，所以進(jìn)行廣度優(yōu)先遍歷時(shí)常由隊(duì)列進(jìn)行配合層序遍歷圖示：
? ? ? ? ?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
? ? ? ? ? ? ?
鏈?zhǔn)蕉鏄?shù)的實(shí)現(xiàn)
（詳細(xì)解釋在圖片的注釋中，代碼分文件放下一標(biāo)題處）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
實(shí)現(xiàn)具體功能前的準(zhǔn)備工作
- 在鏈?zhǔn)蕉鏄?shù)頭文件中包含之后所需頭文件
? ? ? ? ? ? ? ? ? ? ? ?- 定義鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)將要存儲(chǔ)的值的類型
? ? ? ? ? ? ? ? ? ??- 創(chuàng)建鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)類型（結(jié)構(gòu)體）--? BTNode（重命名后）
? ? ? ? ? ? ? ? ? ? ? ??- 因?yàn)?span style="color:#fe2c24;">之后要借助隊(duì)列實(shí)現(xiàn)層序遍歷，
所以要將之前寫的隊(duì)列頭文件和隊(duì)列函數(shù)實(shí)現(xiàn)文件復(fù)制一份放入指定文件夾，
? ? ? ? ? ? ? ? ? ? ? ? ??- 在鏈?zhǔn)蕉鏄?shù)頭文件BTNode類型下方包含復(fù)制的隊(duì)列頭文件，
（這樣復(fù)制的隊(duì)列頭文件展開(kāi)后才能找到BTNode類型并使用它）
在復(fù)制的隊(duì)列頭文件中也包含鏈?zhǔn)蕉鏄?shù)頭文件
? ? ? ? ? ? ? ? ? ? ? ? ??- 利用隊(duì)列對(duì)鏈?zhǔn)蕉鏄?shù)進(jìn)行層序遍歷時(shí)，要將鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)指針存放在隊(duì)列中，
所以要將隊(duì)列中數(shù)據(jù)域存儲(chǔ)的數(shù)據(jù)類型改為鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)指針類型 -- BTNode*圖示：
? ? ? ? ? ??文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-713783.html
? ? ? ? ? ??
---------------------------------------------------------------------------------------------文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-713783.html
? ? ? ? ? ??
BuyNode函數(shù) --?創(chuàng)建鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)并對(duì)其初始化
- 開(kāi)辟動(dòng)態(tài)空間 并 檢查空間是否開(kāi)辟成功
? ? ? ? ? ? ? ? ? ? ? ?- 將要放入節(jié)點(diǎn)的值x放入節(jié)點(diǎn)，
將節(jié)點(diǎn)的左右指針初始化為NULL
? ? ? ? ? ? ? ? ? ??- 返回開(kāi)辟的節(jié)點(diǎn)地址
圖示：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
PrevOrder函數(shù) --?前序（先序）遍歷函數(shù)
- 遞歸遍歷到空指針NULL的話，打印當(dāng)前為空節(jié)點(diǎn)，再返回到上層遞歸
? ? ? ? ? ? ? ? ? ? ? ?- 進(jìn)行前序遍歷：
先訪問(wèn)根節(jié)點(diǎn)，再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)圖示：
（配合這個(gè)圖如果還是不能理解的話，可以看下TreeSize函數(shù)后面的遞歸步驟圖了解遞歸）
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
InOrder函數(shù) --?中序遍歷函數(shù)
- 遞歸遍歷到空指針NULL的話，打印當(dāng)前為空節(jié)點(diǎn)，再返回到上層遞歸
? ? ? ? ? ? ? ? ? ? ? ?- 進(jìn)行中序遍歷：
先訪問(wèn)左子樹(shù)，再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)圖示：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
PostOrder函數(shù) --?后序遍歷函數(shù)
- 遞歸遍歷到空指針NULL的話，打印當(dāng)前為空節(jié)點(diǎn)，再返回到上層遞歸
? ? ? ? ? ? ? ? ? ? ? ?- 進(jìn)行后序遍歷：
先訪問(wèn)左子樹(shù)，再訪問(wèn)右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)圖示：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
TreeSize函數(shù) --?計(jì)算鏈?zhǔn)蕉鏄?shù)中的節(jié)點(diǎn)個(gè)數(shù)
- 使用三目操作符，如果根節(jié)點(diǎn)為空返回0（個(gè)節(jié)點(diǎn)），
如果不為空則返回 TreeSize(root->left) + TreeSize(root->right) + 1
即 左子樹(shù)節(jié)點(diǎn)的個(gè)數(shù) + 右子樹(shù)節(jié)點(diǎn)的個(gè)數(shù) + 1（根節(jié)點(diǎn)） -- ?后序遍歷圖示：
該函數(shù)遞歸步驟圖：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
TreeLeafSize函數(shù) --?計(jì)算鏈?zhǔn)蕉鏄?shù)中的葉子節(jié)點(diǎn)個(gè)數(shù)
- 先判斷當(dāng)前節(jié)點(diǎn)是不是空節(jié)點(diǎn)（是不是空樹(shù)），是的話返回0（個(gè)葉子節(jié)點(diǎn)）
? ? ? ? ? ? ? ? ? ? ? ?- 如果(遞歸后)當(dāng)前節(jié)點(diǎn)的 左子樹(shù)(左孩子) 和?右子樹(shù)(右孩子) 都為空，
說(shuō)明當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，返回1（個(gè)葉子節(jié)點(diǎn)）
? ? ? ? ? ? ? ? ? ??- 如果(遞歸后)當(dāng)前節(jié)點(diǎn)為分支節(jié)點(diǎn)（非空樹(shù)非葉子）,
使用遞歸返回其左子樹(shù)和右子樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)圖示：
該函數(shù)遞歸步驟圖：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
TreeKLevel函數(shù) --?計(jì)算鏈?zhǔn)蕉鏄?shù)中第k層的節(jié)點(diǎn)個(gè)數(shù)
- 鏈?zhǔn)蕉鏄?shù)層數(shù)默認(rèn)從第1層開(kāi)始（根節(jié)點(diǎn)所在層數(shù)）
assert斷言接收的要求鏈?zhǔn)蕉鏄?shù)的層數(shù)應(yīng)大于0
? ? ? ? ? ? ? ? ? ? ? ?- （遞歸時(shí)）遇到空節(jié)點(diǎn)就返回上一層遞歸，返回0（個(gè)節(jié)點(diǎn)）
? ? ? ? ? ? ? ? ? ??- 到達(dá)目標(biāo)層數(shù)后如果節(jié)點(diǎn)不為空，返回1（個(gè)當(dāng)層節(jié)點(diǎn)）
? ? ? ? ? ? ? ? ? ? ? ??- 運(yùn)用“相對(duì)層數(shù)”：
當(dāng)前樹(shù)的第k層 = 左子樹(shù)的第k-1層 + 右子樹(shù)的第k-1層
進(jìn)行遞歸遍歷并統(tǒng)計(jì)第k層的節(jié)點(diǎn)個(gè)數(shù)圖示：
該函數(shù)遞歸步驟圖：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
TreeDestory函數(shù) --?對(duì)鏈?zhǔn)蕉鏄?shù)類型進(jìn)行銷毀
- 遞歸遍歷銷毀鏈?zhǔn)蕉鏄?shù)時(shí)，
如果遇到 空樹(shù) 或 遞歸到葉子節(jié)點(diǎn)的“左右NULL節(jié)點(diǎn)”，
則返回結(jié)束函數(shù) 或 返回上層遞歸
? ? ? ? ? ? ? ? ? ? ? ?- 使用后序遞歸遍歷銷毀鏈?zhǔn)蕉鏄?shù)，
先遍歷銷毀當(dāng)前左子樹(shù)，再遍歷銷毀當(dāng)前右子樹(shù)，最后銷毀當(dāng)前節(jié)點(diǎn)
（置空操作放在調(diào)用該函數(shù)后手動(dòng)進(jìn)行）圖示：
該函數(shù)遞歸步驟圖：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
TreeFind函數(shù) --?在鏈?zhǔn)蕉鏄?shù)中查找值為x的節(jié)點(diǎn)
- 遞歸遍歷對(duì)鏈?zhǔn)蕉鏄?shù)中節(jié)點(diǎn)進(jìn)行查找時(shí)，
如果遇到 空樹(shù) 或 遞歸到葉子節(jié)點(diǎn)的“左右NULL節(jié)點(diǎn)”，
則返回結(jié)束函數(shù) 或 返回上層遞歸
? ? ? ? ? ? ? ? ? ? ? ?- 如果遞歸遍歷過(guò)程中找到對(duì)應(yīng)節(jié)點(diǎn)了，就返回該節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ??- 為了防止找到對(duì)應(yīng)節(jié)點(diǎn)后遞歸還未結(jié)束繼續(xù)查找，
要創(chuàng)建一個(gè)鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)類型指針變量（ret），存放遞歸時(shí)的返回值
? ? ? ? ??- 先使用遞歸遍歷當(dāng)前左子樹(shù)進(jìn)行查找，左子樹(shù)查找完后檢查ret情況看是否已經(jīng)找到
未找到的話再對(duì)當(dāng)前右子樹(shù)進(jìn)行相同操作，如果都未找到則返回空NULL圖示：
該函數(shù)遞歸步驟圖：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
LevelOrder函數(shù) --?對(duì)鏈?zhǔn)蕉鏄?shù)進(jìn)行層序遍歷
- 先創(chuàng)建一個(gè)隊(duì)列類型，并對(duì)其進(jìn)行初始化，
再將鏈?zhǔn)蕉鏄?shù)結(jié)點(diǎn)指針放入隊(duì)列中
? ? ? ? ? ? ? ? ? ? ? ?- 使用while循環(huán)進(jìn)行層序遍歷
? ? ? ? ? ? ? ??- （在while循環(huán)中：）
先創(chuàng)建一個(gè)節(jié)點(diǎn)類型指針變量front存放隊(duì)列中的當(dāng)前節(jié)點(diǎn)地址，
再通過(guò)變量front打印當(dāng)前節(jié)點(diǎn)值
? ? ? ? ? ? ? ??- （在while循環(huán)中：）
然后再分別將當(dāng)前節(jié)點(diǎn)的左右孩子錄入隊(duì)列中，
最后執(zhí)行出隊(duì)操作，出隊(duì)已打印的當(dāng)前節(jié)點(diǎn)值，
這樣一遍循環(huán)下來(lái)就遍歷了一個(gè)節(jié)點(diǎn)并從左往右存儲(chǔ)其兩個(gè)子節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ??- 層序遍歷完成后進(jìn)行換行并銷毀隊(duì)列
圖示：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
TreeComplete函數(shù) --?判斷該鏈?zhǔn)蕉鏄?shù)是不是完全二叉樹(shù)
- 先創(chuàng)建一個(gè)隊(duì)列類型，并對(duì)其進(jìn)行初始化，
再將鏈?zhǔn)蕉鏄?shù)結(jié)點(diǎn)指針放入隊(duì)列中
? ? ? ? ? ? ? ? ? ? ? ?- 使用while循環(huán)進(jìn)行層序遍歷：
先創(chuàng)建一個(gè)節(jié)點(diǎn)類型指針變量front存放隊(duì)列中的當(dāng)前節(jié)點(diǎn)地址，
再判斷當(dāng)前節(jié)點(diǎn)是不是空節(jié)點(diǎn)，是就終止循環(huán)，
然后再分別將當(dāng)前節(jié)點(diǎn)的左右孩子錄入隊(duì)列中，
最后執(zhí)行出隊(duì)操作，出隊(duì)已判斷的當(dāng)前節(jié)點(diǎn)值
? ? ? ? ? ? ? ? ? ??- 再使用一個(gè)while循環(huán)繼續(xù)進(jìn)行遍歷：
先創(chuàng)建一個(gè)節(jié)點(diǎn)類型指針變量front存放隊(duì)列中的當(dāng)前節(jié)點(diǎn)地址，
再對(duì)上個(gè)while循環(huán)中找到的空節(jié)點(diǎn)進(jìn)行出隊(duì)，
這時(shí)如果隊(duì)列之后如果還有非空節(jié)點(diǎn)，
說(shuō)明該鏈?zhǔn)蕉鏄?shù)不是連續(xù)的，不是完全二叉樹(shù)，返回false
? ? ? ? ? ? ? ? ? ? ? ??- 如果第二個(gè)while循環(huán)能夠順利循環(huán)結(jié)束，
說(shuō)明該鏈?zhǔn)蕉鏄?shù)的非空節(jié)點(diǎn)是連續(xù)的，是完全二叉樹(shù)，返回true圖示：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
TreeHeight函數(shù) --?計(jì)算當(dāng)前鏈?zhǔn)蕉鏄?shù)的高度
- 先判斷當(dāng)前節(jié)點(diǎn)是不是空節(jié)點(diǎn)，是的話返回0（層）
? ? ? ? ? ? ? ? ? ? ? ?- 使用遞歸分別計(jì)算左右子樹(shù)的高度并記錄，再返回樹(shù)的高度
? ? ? ? ? ? ? ? ? ??- 再使用三目操作符判斷出較高樹(shù)并返回樹(shù)的高度
（樹(shù)的高度 = 左右子樹(shù)中較高樹(shù)的高度 + 1）圖示：
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
總體測(cè)試：
? ? ? ? ?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
? ? ? ? ? ? ?
對(duì)應(yīng)代碼
BinaryTree.h
#pragma once //包含之后所需的頭文件： #include <stdio.h> #include <stdlib.h> #include <assert.h> //二叉樹(shù)的增刪查改操作并不重要，應(yīng)該重點(diǎn)了解二叉樹(shù)的結(jié)構(gòu) // 為后面了解高階數(shù)據(jù)結(jié)構(gòu)做鋪墊 //（之后高階數(shù)據(jù)結(jié)構(gòu)的搜索二叉樹(shù)、AVL和紅黑樹(shù)才是專業(yè)的） //指定二叉樹(shù)節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的類型： typedef int BTDataType; //創(chuàng)建二叉樹(shù)節(jié)點(diǎn)類型： typedef struct BinaryTreeNode { //左指針：指向該節(jié)點(diǎn)的左孩子 struct BinaryTreeNode* left; //該節(jié)點(diǎn)存儲(chǔ)的值： BTDataType val; //右指針：指向該節(jié)點(diǎn)的右孩子 struct BinaryTreeNode* right; }BTNode; //從命名為BTNode //包含之前寫的隊(duì)列頭文件 //（層序遍歷需要用到隊(duì)列） #include "Queue_BT.h" //（要包含在二叉樹(shù)節(jié)點(diǎn)類型BTNode下方） //（這樣隊(duì)列頭文件展開(kāi)后才能 //找到要存儲(chǔ)的鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)類型） //創(chuàng)建節(jié)點(diǎn)函數(shù) -- 創(chuàng)建鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)并對(duì)其初始化 //接收要放入節(jié)點(diǎn)中的值（x） BTNode* BuyNode(int x); //遞歸結(jié)構(gòu)遍歷 -- 前序（先序）遍歷函數(shù) //先訪問(wèn)根節(jié)點(diǎn) - 再訪問(wèn)左子樹(shù) - 最后訪問(wèn)右子樹(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） void PrevOrder(BTNode* root); //遞歸結(jié)構(gòu)遍歷 -- 中序遍歷函數(shù) //先訪問(wèn)左子樹(shù) - 再訪問(wèn)根節(jié)點(diǎn) - 最后訪問(wèn)右子樹(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） void InOrder(BTNode* root); //遞歸結(jié)構(gòu)遍歷 -- 后序遍歷函數(shù) //先訪問(wèn)左子樹(shù) - 再訪問(wèn)右子樹(shù) - 最后訪問(wèn)根節(jié)點(diǎn) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） void PostOrder(BTNode* root); //節(jié)點(diǎn)數(shù)函數(shù) -- 計(jì)算二叉樹(shù)中的節(jié)點(diǎn)個(gè)數(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） int TreeSize(BTNode* root); //葉子節(jié)點(diǎn)數(shù)函數(shù) -- 計(jì)算二叉樹(shù)中的葉子節(jié)點(diǎn)個(gè)數(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） int TreeLeafSize(BTNode* root); //第k層節(jié)點(diǎn)數(shù)函數(shù) -- 計(jì)算二叉樹(shù)中第k層的節(jié)點(diǎn)個(gè)數(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root）和層數(shù)（k） int TreeKLevel(BTNode* root, int k); //二叉樹(shù)銷毀函數(shù) -- 對(duì)二叉樹(shù)類型進(jìn)行銷毀 //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） void TreeDestory(BTNode* root); //查找指定節(jié)點(diǎn)值函數(shù) -- 在二叉樹(shù)中查找值為x的節(jié)點(diǎn) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root）和 要查找的節(jié)點(diǎn)值（x） BTNode* TreeFind(BTNode* root, BTDataType x); //層序遍歷函數(shù) -- 對(duì)二叉樹(shù)進(jìn)行層序遍歷 //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） void LevelOrder(BTNode* root); //判斷完全二叉樹(shù)函數(shù) -- //判斷該樹(shù)是不是完全二叉樹(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） int TreeComplete(BTNode* root); //計(jì)算高度函數(shù) -- 計(jì)算當(dāng)前鏈?zhǔn)蕉鏄?shù)的高度 //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） int TreeHeight(BTNode* root);? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
Queue_BT.h
#pragma once //包含之后需要的頭文件： #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //包含鏈?zhǔn)蕉鏄?shù)頭文件： #include "BinaryTree.h" //以鏈表（鏈?zhǔn)浇Y(jié)構(gòu)）實(shí)現(xiàn)隊(duì)列： //雙向+循環(huán) 的鏈表可以解決找尾結(jié)點(diǎn)的問(wèn)題， //定義一個(gè)尾指針也可以解決該問(wèn)題， //哨兵位 可以解決二級(jí)指針的問(wèn)題， //且尾插時(shí)可以少一層判斷，但還有方法可以解決 //定義隊(duì)列(鏈?zhǔn)浇Y(jié)構(gòu))中數(shù)據(jù)域存儲(chǔ)的數(shù)據(jù)類型： typedef BTNode* QDataType; //因?yàn)橐獙㈥?duì)列應(yīng)用到存儲(chǔ)鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)指針上 //（直接存儲(chǔ)其節(jié)點(diǎn)太費(fèi)空間，所以存儲(chǔ)其節(jié)點(diǎn)指針） //所以要把隊(duì)列存儲(chǔ)的數(shù)據(jù)類型改掉 //改為和二叉樹(shù)節(jié)點(diǎn)指針一致 -- BTNode* //定義隊(duì)列(鏈?zhǔn)浇Y(jié)構(gòu))結(jié)點(diǎn)類型： typedef struct QueueNode { //隊(duì)列指針域： struct QueueNode* next; //隊(duì)列數(shù)據(jù)域： QDataType data; }QNode; //將類型重命名為Qnode //定義隊(duì)列類型： typedef struct Queue { //因?yàn)橛面湵砦膊鍖?shí)現(xiàn)入隊(duì)， //用鏈表頭刪實(shí)現(xiàn)出隊(duì)， //那么就需要頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的指針， //所以可以直接將這兩個(gè)指針?lè)庋b為一個(gè)類型， //隊(duì)列類型： //頭結(jié)點(diǎn)指針： QNode* head; //尾結(jié)點(diǎn)指針： QNode* tail; //記錄隊(duì)列結(jié)點(diǎn)(元素)個(gè)數(shù)： int size; //這樣之后在出隊(duì)和入隊(duì)操作時(shí)， //就不需要用到二級(jí)指針， //直接接收這個(gè)結(jié)構(gòu)體指針， //通過(guò)結(jié)構(gòu)體指針運(yùn)用結(jié)構(gòu)體里的頭尾結(jié)點(diǎn)指針， //再用頭尾結(jié)點(diǎn)指針定義頭尾結(jié)點(diǎn) //來(lái)實(shí)現(xiàn) 二級(jí)指針、帶哨兵位頭結(jié)點(diǎn) 和 返回值 的作用 //所以現(xiàn)在已知的通過(guò)指針定義結(jié)點(diǎn)的方法就有4種： // 1. 結(jié)構(gòu)體包含結(jié)點(diǎn)指針 // 2. 二級(jí)指針調(diào)用結(jié)點(diǎn)指針 // 3. 哨兵位頭結(jié)點(diǎn)指針域next指向結(jié)點(diǎn)地址 // 4. 返回值返回改變的結(jié)點(diǎn)指針 }Que; //重命名為Que //隊(duì)列初始化函數(shù) -- 將隊(duì)列進(jìn)行初始化 //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) void QueueInit(Que* pq); //隊(duì)列銷毀函數(shù) -- 將隊(duì)列銷毀 //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) void QueueDestroy(Que* pq); //隊(duì)列入隊(duì)函數(shù) -- 用鏈表的尾插操作實(shí)現(xiàn)入隊(duì) //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) 、尾插值 void QueuePush(Que* pq, QDataType x); //隊(duì)列出隊(duì)函數(shù) -- 用鏈表的頭刪操作實(shí)現(xiàn)出隊(duì) //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) void QueuePop(Que* pq); //隊(duì)頭函數(shù) -- 返回隊(duì)頭結(jié)點(diǎn)的數(shù)據(jù)域數(shù)據(jù) //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) QDataType QueueFront(Que* pq); //隊(duì)尾函數(shù) -- 返回隊(duì)尾結(jié)點(diǎn)的數(shù)據(jù)域數(shù)據(jù) //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) QDataType QueueBack(Que* pq); //判空函數(shù) -- 判斷隊(duì)列是否為空 //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) bool QueueEmpty(Que* pq); //隊(duì)列大小函數(shù) -- 判斷隊(duì)列結(jié)點(diǎn)(元素)個(gè)數(shù) //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) int QueueSize(Que* pq);? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS 1 //包含二叉樹(shù)頭文件： #include "BinaryTree.h" //創(chuàng)建節(jié)點(diǎn)函數(shù) -- 創(chuàng)建鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)并對(duì)其初始化 //接收要放入節(jié)點(diǎn)中的值（x） BTNode* BuyNode(int x) { //開(kāi)辟動(dòng)態(tài)空間： BTNode* node = (BTNode*)malloc(sizeof(BTNode)); //檢查是否開(kāi)辟成功： if (node == NULL) { //開(kāi)辟失敗則打印錯(cuò)誤信息： perror("malloc fail"); //終止程序： exit(-1); } //將要放入節(jié)點(diǎn)的值x放入節(jié)點(diǎn)： node->val = x; //將節(jié)點(diǎn)的左右指針初始化為NULL： node->left = NULL; node->right = NULL; //返回開(kāi)辟的節(jié)點(diǎn)地址： return node; } //遞歸結(jié)構(gòu)遍歷 -- 前序（先序）遍歷 //先訪問(wèn)根節(jié)點(diǎn) - 再訪問(wèn)左子樹(shù) - 最后訪問(wèn)右子樹(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） void PrevOrder(BTNode* root) { //遞歸遍歷到空指針NULL（或空樹(shù)）： if (root == NULL) { //打印當(dāng)前為空節(jié)點(diǎn)： printf("NULL "); //返回結(jié)束當(dāng)前遞歸： return; } //進(jìn)行前序遍歷： //先訪問(wèn)根節(jié)點(diǎn) -- 打印當(dāng)前節(jié)點(diǎn)的值： printf("%d ", root->val); //再訪問(wèn)左子樹(shù) -- 使用遞歸打印左子樹(shù)： PrevOrder(root->left); //最后訪問(wèn)右子樹(shù) -- 使用遞歸打印右子樹(shù)： PrevOrder(root->right); } //遞歸結(jié)構(gòu)遍歷 -- 中序遍歷 //先訪問(wèn)左子樹(shù) - 再訪問(wèn)根節(jié)點(diǎn) - 最后訪問(wèn)右子樹(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） void InOrder(BTNode* root) { //遞歸遍歷到空指針NULL： if (root == NULL) { //打印當(dāng)前為空節(jié)點(diǎn)： printf("NULL "); //返回結(jié)束當(dāng)前遞歸： return; } //進(jìn)行中序遍歷： //先訪問(wèn)左子樹(shù) -- 使用遞歸打印左子樹(shù)： InOrder(root->left); //再訪問(wèn)根節(jié)點(diǎn) -- 打印當(dāng)前節(jié)點(diǎn)的值： printf("%d ", root->val); //最后訪問(wèn)右子樹(shù) -- 使用遞歸打印右子樹(shù)： InOrder(root->right); } //遞歸結(jié)構(gòu)遍歷 -- 后序遍歷 //先訪問(wèn)左子樹(shù) - 再訪問(wèn)右子樹(shù) - 最后訪問(wèn)根節(jié)點(diǎn) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） void PostOrder(BTNode* root) { //遞歸遍歷到空指針NULL： if (root == NULL) { //打印當(dāng)前為空節(jié)點(diǎn)： printf("NULL "); //返回結(jié)束當(dāng)前遞歸： return; } //進(jìn)行后序遍歷： //先訪問(wèn)左子樹(shù) -- 使用遞歸打印左子樹(shù)： PostOrder(root->left); //再訪問(wèn)右子樹(shù) -- 使用遞歸打印右子樹(shù)： PostOrder(root->right); //最后訪問(wèn)根節(jié)點(diǎn) -- 打印當(dāng)前節(jié)點(diǎn)的值： printf("%d ", root->val); } //節(jié)點(diǎn)數(shù)函數(shù) -- 計(jì)算二叉樹(shù)中的節(jié)點(diǎn)個(gè)數(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） int TreeSize(BTNode* root) { //第二種方法：“分治”思想 return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; //使用三目操作符，如果根節(jié)點(diǎn)為空返回0（個(gè)節(jié)點(diǎn)） //如果不為空則返回 TreeSize(root->left) + TreeSize(root->right) + 1 //即 左子樹(shù)節(jié)點(diǎn)的個(gè)數(shù) + 右子樹(shù)節(jié)點(diǎn)的個(gè)數(shù) + 1（根節(jié)點(diǎn)） -- 后序遍歷 } //第一種方法：遞歸遍歷統(tǒng)計(jì)二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù) /* //節(jié)點(diǎn)數(shù)函數(shù) -- 計(jì)算二叉樹(shù)中的節(jié)點(diǎn)個(gè)數(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） int TreeSize(BTNode* root) { //遞歸時(shí)每遞歸一次就會(huì)創(chuàng)建一次棧幀， //如果有初始化普通變量，每遞歸一次就會(huì)初始化一次， //所以要賦予普通變量常屬性，使其成為靜態(tài)成員變量， //局部的靜態(tài)成員變量只會(huì)被初始化一次： static int size = 0; //但是這樣該函數(shù)就只能調(diào)用一次，因?yàn)檎{(diào)用一次后， //該變量不會(huì)再初始化為0，直到程序結(jié)束才被銷毀 //那么可以把size定義為全局變量， //在主函數(shù)調(diào)用該函數(shù)前就要先將size初始化為0 if (root == NULL) //如果根節(jié)點(diǎn)為空： { return 0; //返回0表0個(gè)節(jié)點(diǎn) } else { ++size; //root不為空則個(gè)數(shù)++ } //使用遞歸遍歷計(jì)算（類似前序遍歷）： TreeSize(root->left); //先遍歷左子樹(shù) TreeSize(root->right); //再遍歷右子樹(shù) //返回二叉樹(shù)中節(jié)點(diǎn)個(gè)數(shù)： return size; } */ //葉子節(jié)點(diǎn)數(shù)函數(shù) -- 計(jì)算二叉樹(shù)中的葉子節(jié)點(diǎn)個(gè)數(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） int TreeLeafSize(BTNode* root) { if (root == NULL) //如果當(dāng)前根節(jié)點(diǎn)為空： //（當(dāng)前為空樹(shù)） { //返回0 -- 無(wú)葉子節(jié)點(diǎn)： return 0; } if (root->left == NULL && root->right == NULL) //如果當(dāng)前節(jié)點(diǎn)的左子樹(shù)(左孩子)和右子樹(shù)(右孩子)都為空： { //說(shuō)明當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，左右指針都指向NULL： return 1; //返回1 } //能執(zhí)行到這說(shuō)明當(dāng)前節(jié)點(diǎn)為非空樹(shù)非葉子節(jié)點(diǎn) -- 分支節(jié)點(diǎn) //如果遞歸后當(dāng)前節(jié)點(diǎn)為分支節(jié)點(diǎn)（非空樹(shù)非葉子）, //使用遞歸返回其左子樹(shù)和右子樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)： return TreeLeafSize(root->left) + TreeLeafSize(root->right); } //第k層節(jié)點(diǎn)數(shù)函數(shù) -- 計(jì)算二叉樹(shù)中第k層的節(jié)點(diǎn)個(gè)數(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root）和層數(shù)（k） int TreeKLevel(BTNode* root, int k) { //層數(shù)默認(rèn)從第1層開(kāi)始（根節(jié)點(diǎn)所在層數(shù)） //assert斷言二叉樹(shù)的層數(shù)大于0: assert(k > 0); //（遞歸時(shí)）遍歷過(guò)程遇到空節(jié)點(diǎn)： if (root == NULL) { //已經(jīng)遇到空節(jié)點(diǎn)就返回上一層遞歸 return 0; } //到達(dá)目標(biāo)層數(shù)后如果節(jié)點(diǎn)不為空： if (k == 1) { //返回1個(gè)當(dāng)層節(jié)點(diǎn)： return 1; } //需知：“相對(duì)層數(shù)” //我們說(shuō)的第k層是以根節(jié)點(diǎn)（第1層）為準(zhǔn)的 // "第一層的第三層 等于 第二層的第二層 等于 第三層的第一層" // 爺爺找孫子，可以先找孫子的爸爸，再讓爸爸找兒子（爺爺?shù)膶O子） //所以有：當(dāng)前樹(shù)的第k層 = 左子樹(shù)的第k-1層 + 右子樹(shù)的第k-1層 // （遞歸的降級(jí)） //當(dāng)前樹(shù)的第k層 = 左子樹(shù)的第k-1層 + 右子樹(shù)的第k-1層 ： return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1); } //二叉樹(shù)銷毀函數(shù) -- 對(duì)二叉樹(shù)類型進(jìn)行銷毀 //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） void TreeDestory(BTNode* root) { //分三部分進(jìn)行銷毀： //當(dāng)前節(jié)點(diǎn)、左子樹(shù)、右子樹(shù) //使用后序銷毀二叉樹(shù)： //最后才銷毀根節(jié)點(diǎn)， //防止先銷毀根節(jié)點(diǎn)后找不到左右子樹(shù)， //導(dǎo)致最后不能銷毀左右1子樹(shù) if (root == NULL) //如果遇到空樹(shù)， //或者遞歸到葉子節(jié)點(diǎn)的“左右NULL節(jié)點(diǎn)”： { //直接返回： return; } //使用后序遍歷： //先遍歷銷毀當(dāng)前左子樹(shù)： TreeDestory(root->left); //再遍歷銷毀當(dāng)前右子樹(shù)： TreeDestory(root->right); //最后銷毀當(dāng)前節(jié)點(diǎn)： free(root); //置空操作放在調(diào)用該函數(shù)后手動(dòng)進(jìn)行 } //查找指定節(jié)點(diǎn)值函數(shù) -- 在二叉樹(shù)中查找值為x的節(jié)點(diǎn) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root）和 要查找的節(jié)點(diǎn)值（x） BTNode* TreeFind(BTNode* root, BTDataType x) { //如果是空樹(shù)（或“左右NULL子樹(shù)”）： if (root == NULL) { //那就不用找了，直接返回空： return NULL; } //遞歸過(guò)程中找到對(duì)應(yīng)節(jié)點(diǎn)了： if (root->val == x) { //返回該節(jié)點(diǎn)指針： return root; } //為了防止找到后往回遞歸又返回 //覆蓋掉了找到的節(jié)點(diǎn)指針， //所以要?jiǎng)?chuàng)建一個(gè)變量存儲(chǔ)找到的節(jié)點(diǎn)指針 //方便最終返回該指針： //創(chuàng)建二叉樹(shù)節(jié)點(diǎn)類型指針變量： BTNode* ret = NULL; //進(jìn)行遞歸并用變量ret存儲(chǔ)： //（如果在左子樹(shù)中找到） ret = TreeFind(root->left, x); //如果找到了就不用再遞歸遍歷右子樹(shù)了， //判斷并返回在左子樹(shù)中找到的對(duì)應(yīng)節(jié)點(diǎn)地址： if (ret != NULL) //ret不為空說(shuō)明已經(jīng)在左子樹(shù)中找到了對(duì)應(yīng)節(jié)點(diǎn)： { //進(jìn)行返回，不在進(jìn)行下面的右子樹(shù)遍歷： return ret; } //執(zhí)行到這里說(shuō)明左子樹(shù)中未找到相應(yīng)節(jié)點(diǎn)， //需再遍歷右子樹(shù)進(jìn)行查找： ret = TreeFind(root->right, x); //如果在右邊找到了： if (ret != NULL) //此時(shí)ret不為空， //說(shuō)明在右子樹(shù)中找到了對(duì)應(yīng)節(jié)點(diǎn)： { //返回找到的節(jié)點(diǎn)地址： return ret; } //如果能執(zhí)行到這，說(shuō)明二叉樹(shù)中沒(méi)有該節(jié)點(diǎn)： return NULL; //返回空 } //層序遍歷函數(shù) -- 對(duì)二叉樹(shù)進(jìn)行層序遍歷 //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） void LevelOrder(BTNode* root) { //使用 隊(duì)列 存儲(chǔ)二叉樹(shù)：“上一層帶下一層” //（從上到下、從左到右存儲(chǔ)二叉樹(shù)） //先創(chuàng)建一個(gè)隊(duì)列類型： Que q; //對(duì)隊(duì)列進(jìn)行初始化： QueueInit(&q); //先將二叉樹(shù)根節(jié)點(diǎn)root放入隊(duì)列中： if (root != NULL) //二叉樹(shù)根節(jié)點(diǎn)不為空才能放入隊(duì)列： { //使用隊(duì)列入隊(duì)函數(shù)QueuePush將根節(jié)點(diǎn)（指針）錄入： QueuePush(&q, root); } //之后再使用while循環(huán)，進(jìn)行層序遍歷： while (QueueEmpty(&q) != true) //只要當(dāng)前隊(duì)列不為空（隊(duì)列中還有節(jié)點(diǎn)指針）就繼續(xù)層序遍歷： { //使用隊(duì)列的隊(duì)頭函數(shù)QueueFront獲取隊(duì)頭的節(jié)點(diǎn)指針： BTNode* front = QueueFront(&q); //打印當(dāng)前隊(duì)頭節(jié)點(diǎn)值： printf("%d ", front->val); //先錄入當(dāng)前節(jié)點(diǎn)左孩子： //如果當(dāng)前節(jié)點(diǎn)左孩子不為空，就將其左孩子錄入隊(duì)列： if (front->left != NULL) { //使用隊(duì)列入隊(duì)函數(shù)QueuePush將當(dāng)前左孩子錄入隊(duì)列： QueuePush(&q, front->left); } //再錄入當(dāng)前節(jié)點(diǎn)右孩子： //如果當(dāng)前節(jié)點(diǎn)右孩子不為空，就將其右孩子錄入隊(duì)列： if (front->right != NULL) { //使用隊(duì)列入隊(duì)函數(shù)QueuePush將當(dāng)前右孩子錄入隊(duì)列： QueuePush(&q, front->right); } //打印當(dāng)前節(jié)點(diǎn)值 且 錄入新左后節(jié)點(diǎn)指針 后， //將當(dāng)前節(jié)點(diǎn)出隊(duì)(隊(duì)列出隊(duì)函數(shù)QueuePop)， //對(duì)下個(gè)隊(duì)頭二叉樹(shù)節(jié)點(diǎn)指針進(jìn)行相同操作： QueuePop(&q); //（完成“上一層帶下一層”，從上到下、從左到右存儲(chǔ)二叉樹(shù)） } //層序遍歷完成后換行： printf("\n"); //使用隊(duì)列對(duì)二叉樹(shù)遍歷完成后，銷毀隊(duì)列： QueueDestroy(&q); } //判斷完全二叉樹(shù)函數(shù) -- 判斷該樹(shù)是不是完全二叉樹(shù) //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） int TreeComplete(BTNode* root) { /* 思路：利用層序遍歷的特征進(jìn)行判斷 遍歷時(shí)如果有空節(jié)點(diǎn)，將空節(jié)點(diǎn)也進(jìn)行遍歷， 看最終空節(jié)點(diǎn)的分布情況就能判斷是不是完全二叉樹(shù) 1、遍歷時(shí)如果非空節(jié)點(diǎn)是連續(xù)的，就是完全二叉樹(shù) 2、遍歷時(shí)如果非空節(jié)點(diǎn)不連續(xù)，遍歷時(shí)中間右出現(xiàn)空節(jié)點(diǎn)，就是非完全二叉樹(shù) */ //先創(chuàng)建一個(gè)隊(duì)列類型： Que q; //對(duì)隊(duì)列進(jìn)行初始化： QueueInit(&q); //先將二叉樹(shù)根節(jié)點(diǎn)root放入隊(duì)列中： if (root != NULL) //二叉樹(shù)根節(jié)點(diǎn)不為空才能放入隊(duì)列： { //使用隊(duì)列入隊(duì)函數(shù)QueuePush將根節(jié)點(diǎn)（指針）錄入： QueuePush(&q, root); } //之后再使用while循環(huán)，進(jìn)行層序遍歷： while (QueueEmpty(&q) != true) //只要當(dāng)前隊(duì)列不為空（隊(duì)列中還有節(jié)點(diǎn)指針）就繼續(xù)層序遍歷： { //使用隊(duì)列的隊(duì)頭函數(shù)QueueFront獲取隊(duì)頭的節(jié)點(diǎn)指針： BTNode* front = QueueFront(&q); //循環(huán)遍歷過(guò)程中如果遇到空節(jié)點(diǎn)就終止循環(huán)： if (front == NULL) //front為空節(jié)點(diǎn)： { break; //終止循環(huán) } //使用隊(duì)列入隊(duì)函數(shù)QueuePush將當(dāng)前左孩子錄入隊(duì)列： QueuePush(&q, front->left); //使用隊(duì)列入隊(duì)函數(shù)QueuePush將當(dāng)前右孩子錄入隊(duì)列： QueuePush(&q, front->right); //將當(dāng)前隊(duì)頭的節(jié)點(diǎn)類型出隊(duì)，判斷下個(gè)節(jié)點(diǎn)： QueuePop(&q); } /* 執(zhí)行到這時(shí)，隊(duì)列中隊(duì)頭節(jié)點(diǎn)即空節(jié)點(diǎn)（NULL） 這時(shí)再看該空節(jié)點(diǎn) 后面的所有節(jié)點(diǎn) 還有沒(méi)有非空節(jié)點(diǎn)， 后面的所有節(jié)點(diǎn)還有 非空節(jié)點(diǎn) 的話 -- 說(shuō)明該二叉樹(shù)不是連續(xù)的，不是完全二叉樹(shù) 后面的所有節(jié)點(diǎn)沒(méi)有 非空節(jié)點(diǎn) 的話 -- 說(shuō)明該樹(shù)非空節(jié)點(diǎn)都是連續(xù)的，是完全二叉樹(shù) */ //同樣使用while循環(huán)進(jìn)行操作： while (QueueEmpty(&q) != true) //只要當(dāng)前隊(duì)列不為空（隊(duì)列中還有節(jié)點(diǎn)指針）就繼續(xù)循環(huán)判斷： { //使用隊(duì)列的隊(duì)頭函數(shù)QueueFront獲取隊(duì)頭的節(jié)點(diǎn)指針： BTNode* front = QueueFront(&q); //使用出隊(duì)函數(shù)QueuePop進(jìn)行出隊(duì)操作： //（第一次出隊(duì)時(shí)將隊(duì)頭的空節(jié)點(diǎn)NULL出隊(duì)） QueuePop(&q); /* 出隊(duì)后如果當(dāng)前隊(duì)頭節(jié)點(diǎn)為非空節(jié)點(diǎn)的話， 說(shuō)明該二叉樹(shù)不是連續(xù)的，不是完全二叉樹(shù)， 則銷毀隊(duì)列并返回false: */ if (front != NULL) //當(dāng)前隊(duì)頭節(jié)點(diǎn)為非空節(jié)點(diǎn)： { //銷毀隊(duì)列： QueueDestroy(&q); //返回false： return false; } } /* 執(zhí)行到這，說(shuō)明之后已經(jīng)沒(méi)有非空節(jié)點(diǎn)了 說(shuō)明該樹(shù)非空節(jié)點(diǎn)都是連續(xù)的，是完全二叉樹(shù)， 則銷毀隊(duì)列并返回true: */ //銷毀隊(duì)列： QueueDestroy(&q); //返回true： return true; //（ true 以int類型返回 -- 1） //（ false 以int類型返回 -- 0） } //計(jì)算高度函數(shù) -- 計(jì)算當(dāng)前鏈?zhǔn)蕉鏄?shù)的高度 //接收二叉樹(shù)根節(jié)點(diǎn)地址（root） int TreeHeight(BTNode* root) { //思路：樹(shù)的高度 = 左右子樹(shù)中較高樹(shù)的高度 + 1(根節(jié)點(diǎn)) //如果該樹(shù)是空樹(shù)，返回 0（層）： if (root == NULL) //根節(jié)點(diǎn)為空： { //返回 0（層）： return 0; } //方法二：使用遞歸計(jì)算左右子樹(shù)高度并記錄，再返回樹(shù)的高度 //遞歸計(jì)算左子樹(shù)高度： int leftHeight = TreeHeight(root->left); //遞歸計(jì)算右子樹(shù)高度： int rightHeight = TreeHeight(root->right); //再使用三目操作符判斷后返回樹(shù)的高度： return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; //樹(shù)的高度 = 左右子樹(shù)中較高樹(shù)的高度 + 1(根節(jié)點(diǎn)) /* //方法一：使用三目操作符返回樹(shù)的高度 return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1; //三目操作符選出較高樹(shù)，再 計(jì)算其高度 + 1 = 樹(shù)的高度 */ /* 這樣可以計(jì)算出該樹(shù)的高度，但是其中含有大量的重復(fù)計(jì)算， 判斷較高樹(shù)時(shí)已經(jīng)遞歸求了左右子樹(shù)的高度， 在返回樹(shù)的高度時(shí)又重新計(jì)算了一遍左右子樹(shù)的高度， 是極其不好的代碼 */ }? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
Queue_BT.c
#define _CRT_SECURE_NO_WARNINGS 1 //包含隊(duì)列頭文件： #include "Queue_BT.h" //隊(duì)列初始化函數(shù) -- 將隊(duì)列進(jìn)行初始化 //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) void QueueInit(Que* pq) { //assert斷言隊(duì)列類型指針不為空： assert(pq != NULL); //將隊(duì)頭結(jié)點(diǎn)置為空： pq->head = NULL; //將隊(duì)尾結(jié)點(diǎn)置為空： pq->tail = NULL; //隊(duì)列結(jié)點(diǎn)(元素)個(gè)數(shù)置為0： pq->size = 0; } //隊(duì)列銷毀函數(shù) -- 將隊(duì)列銷毀 //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) void QueueDestroy(Que* pq) { //assert斷言隊(duì)列類型指針不為空： assert(pq != NULL); //釋放隊(duì)列跟單鏈表的釋放一樣 //先創(chuàng)建一個(gè)在隊(duì)列進(jìn)行遍歷的指針： QNode* cur = pq->head; //從隊(duì)頭結(jié)點(diǎn)開(kāi)始 //使用while循環(huán)進(jìn)行遍歷釋放隊(duì)列結(jié)點(diǎn)： while (cur != NULL) { //先保存下個(gè)結(jié)點(diǎn)： QNode* next = cur->next; //再釋放當(dāng)前結(jié)點(diǎn)： free(cur); //再指向下個(gè)結(jié)點(diǎn)： cur = next; } //結(jié)點(diǎn)都釋放后，把隊(duì)頭隊(duì)尾指針都置空： pq->head = NULL; pq->tail = NULL; //再把隊(duì)列結(jié)點(diǎn)(元素)個(gè)數(shù)置為0： pq->size = 0; } //隊(duì)列入隊(duì)函數(shù) -- 用鏈表的尾插操作實(shí)現(xiàn)入隊(duì) //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) 、尾插值 void QueuePush(Que* pq, QDataType x) { //assert斷言隊(duì)列類型指針不為空： assert(pq != NULL); //入隊(duì)放入元素需要空間， //所以要先為隊(duì)列結(jié)點(diǎn)開(kāi)辟動(dòng)態(tài)空間： QNode* newnode = (QNode*)malloc(sizeof(QNode)); //檢查是否開(kāi)辟成功： if (newnode == NULL) { //開(kāi)辟失敗則打印錯(cuò)誤信息： perror("malloc fail"); //終止程序： exit(-1); } //隊(duì)列結(jié)點(diǎn)完成后將尾插值(x) //賦給隊(duì)列結(jié)點(diǎn)數(shù)據(jù)域： newnode->data = x; //指針域指向空： newnode->next = NULL; //空間開(kāi)辟后進(jìn)行尾插： if (pq->tail == NULL) //如果隊(duì)列剛初始化，隊(duì)列為空， //頭結(jié)點(diǎn)指針和尾結(jié)點(diǎn)指針都為空： { //那么將剛開(kāi)辟的結(jié)點(diǎn)newnode地址 //賦給頭結(jié)點(diǎn)指針和尾結(jié)點(diǎn)指針 pq->head = newnode; pq->tail = newnode; } else //隊(duì)列不為空，進(jìn)行尾插： { //將目前隊(duì)尾結(jié)點(diǎn)指針域next指向尾插結(jié)點(diǎn)： pq->tail->next = newnode; //然后再指向尾插結(jié)點(diǎn)，成為新隊(duì)尾結(jié)點(diǎn)： pq->tail = newnode; } //插入數(shù)據(jù)后隊(duì)列結(jié)點(diǎn)(元素)個(gè)數(shù)++： pq->size++; } //隊(duì)列出隊(duì)函數(shù) -- 用鏈表的頭刪操作實(shí)現(xiàn)出隊(duì) //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) void QueuePop(Que* pq) { //assert斷言隊(duì)列類型指針不為空： assert(pq != NULL); //assert斷言隊(duì)列不為空，沒(méi)數(shù)據(jù)不能刪除： assert(QueueEmpty != true); //不為空就繼續(xù)程序 //如果隊(duì)列中只剩一個(gè)結(jié)點(diǎn)： if (pq->head->next == NULL) //隊(duì)頭指針指向空，說(shuō)明只剩一個(gè)結(jié)點(diǎn)， //只剩一個(gè)結(jié)點(diǎn)說(shuō)明隊(duì)頭隊(duì)尾指針都指向這一個(gè)結(jié)點(diǎn)， //所以這時(shí)頭刪后頭指針移動(dòng)，尾指針也要移動(dòng) { //先釋放("刪除")隊(duì)列目前頭結(jié)點(diǎn)： free(pq->head); //刪除后將隊(duì)頭隊(duì)尾指針都置為空： pq->head = NULL; pq->tail = NULL; } else //隊(duì)列不止一個(gè)結(jié)點(diǎn)，則頭刪后只需移動(dòng)隊(duì)頭結(jié)點(diǎn)： { //用鏈表的頭刪操作實(shí)現(xiàn)出隊(duì), //先保存第二個(gè)結(jié)點(diǎn)地址： QNode* next = pq->head->next; //釋放("刪除")隊(duì)列目前頭結(jié)點(diǎn)： free(pq->head); //再將隊(duì)頭結(jié)點(diǎn)指針指向原本第二個(gè)結(jié)點(diǎn)next， //讓其成為新的隊(duì)頭結(jié)點(diǎn)： pq->head = next; } //“刪除”后隊(duì)列結(jié)點(diǎn)(元素)個(gè)數(shù)--： pq->size--; } //隊(duì)頭函數(shù) -- 返回隊(duì)頭結(jié)點(diǎn)的數(shù)據(jù)域數(shù)據(jù) //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) QDataType QueueFront(Que* pq) { //assert斷言隊(duì)列類型指針不為空： assert(pq != NULL); //assert斷言隊(duì)列不為空，沒(méi)數(shù)據(jù)不能查找： assert(QueueEmpty != true); //不為空就繼續(xù)程序 //隊(duì)列有數(shù)據(jù)，則直接返回隊(duì)頭結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)： return pq->head->data; } //隊(duì)尾函數(shù) -- 返回隊(duì)尾結(jié)點(diǎn)的數(shù)據(jù)域數(shù)據(jù) //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) QDataType QueueBack(Que* pq) { //assert斷言隊(duì)列類型指針不為空： assert(pq != NULL); //assert斷言隊(duì)列不為空，沒(méi)數(shù)據(jù)不能查找： assert(QueueEmpty != true); //不為空就繼續(xù)程序 //隊(duì)列有數(shù)據(jù)，則直接返回隊(duì)尾結(jié)點(diǎn)數(shù)據(jù)域數(shù)據(jù)： return pq->tail->data; } //判空函數(shù) -- 判斷隊(duì)列是否為空 //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) bool QueueEmpty(Que* pq) { //assert斷言隊(duì)列類型指針不為空： assert(pq != NULL); //直接判斷隊(duì)頭結(jié)點(diǎn)指向的下個(gè)結(jié)點(diǎn)是否為空： return pq->head == NULL; //是則返回true -- 隊(duì)列為空 //是則返回false -- 隊(duì)列不為空 } //隊(duì)列大小函數(shù) -- 判斷隊(duì)列結(jié)點(diǎn)(元素)個(gè)數(shù) //接收隊(duì)列類型指針(包含鏈表頭尾結(jié)點(diǎn)) int QueueSize(Que* pq) { //assert斷言隊(duì)列類型指針不為空： assert(pq != NULL); //直接返回size隊(duì)列結(jié)點(diǎn)(元素)個(gè)數(shù)： return pq->size; }? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
Test.c
#define _CRT_SECURE_NO_WARNINGS 1 //包含二叉樹(shù)頭文件： #include "BinaryTree.h" //測(cè)試函數(shù) -- 鏈?zhǔn)蕉鏄?shù)： void Test() { //手動(dòng)創(chuàng)建多個(gè)鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)： BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); //將多個(gè)鏈?zhǔn)蕉鏄?shù)節(jié)點(diǎn)按自己需要連接成鏈?zhǔn)蕉鏄?shù)： node1->left = node2; //節(jié)點(diǎn)1的左指針指向節(jié)點(diǎn)2 node1->right = node3; //節(jié)點(diǎn)1的右指針指向節(jié)點(diǎn)3 node2->left = node4; //節(jié)點(diǎn)2的左指針指向節(jié)點(diǎn)4 node3->left = node5; //節(jié)點(diǎn)3的左指針指向節(jié)點(diǎn)5 node3->right = node6; //節(jié)點(diǎn)3的右指針指向節(jié)點(diǎn)6 //使用PrevOrder函數(shù)進(jìn)行前序（先序）遍歷： printf("對(duì)當(dāng)前二叉樹(shù)進(jìn)行先序遍歷:> "); PrevOrder(node1); //接收根節(jié)點(diǎn) printf("\n\n"); //使用InOrder函數(shù)進(jìn)行中序遍歷： printf("對(duì)當(dāng)前二叉樹(shù)進(jìn)行中序遍歷:> "); InOrder(node1); //接收根節(jié)點(diǎn) printf("\n\n"); //使用PostOrder函數(shù)進(jìn)行后序遍歷： printf("對(duì)當(dāng)前二叉樹(shù)進(jìn)行后序遍歷:> "); PostOrder(node1); //接收根節(jié)點(diǎn) printf("\n\n"); //使用TreeSize計(jì)算當(dāng)前二叉樹(shù)節(jié)點(diǎn)數(shù)： printf("當(dāng)前二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)為:> %d\n", TreeSize(node1)); printf("\n"); //使用TreeLeafSize計(jì)算當(dāng)前二叉樹(shù)節(jié)點(diǎn)數(shù)： printf("當(dāng)前二叉樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)為:> %d\n", TreeLeafSize(node1)); printf("\n"); //使用TreeKLevel計(jì)算二叉樹(shù)中第k層的節(jié)點(diǎn)個(gè)數(shù)： printf("當(dāng)前二叉樹(shù)中第3層的節(jié)點(diǎn)個(gè)數(shù)為:> %d\n", TreeKLevel(node1, 3)); printf("\n"); //使用LevelOrder使用隊(duì)列進(jìn)行層序遍歷： printf("使用層序遍歷遍歷打印當(dāng)前二叉樹(shù):> "); LevelOrder(node1); printf("\n"); //使用TreeComplete判斷當(dāng)前鏈?zhǔn)蕉鏄?shù)是不是完全二叉樹(shù)： printf("當(dāng)前二叉樹(shù)是不是完全二叉樹(shù):> %d\n", TreeComplete(node1)); printf("\n"); //使用TreeHeight函數(shù)計(jì)算當(dāng)前二叉樹(shù)的高度： printf("當(dāng)前二叉樹(shù)的高度為:> %d\n", TreeHeight(node1)); printf("\n"); //銷毀二叉樹(shù)類型： TreeDestory(node1); //銷毀后將其置為空： node1 = NULL; } //主函數(shù)： int main() { Test(); return 0; }
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)初階】八、非線性表里的二叉樹(shù)（二叉樹(shù)的實(shí)現(xiàn) -- C語(yǔ)言鏈?zhǔn)浇Y(jié)構(gòu)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
