文章目錄
1.二叉樹的概念
1.1概念
1.2存儲(chǔ)方式
1.3特殊的二叉樹?
1.4規(guī)律
2.二叉樹的實(shí)現(xiàn)
2.1表現(xiàn)方式
2.2遍歷
? ??2.2.1前序遍歷
??思想
??代碼
??詳細(xì)分析?
? ??2.2.2中序遍歷
? ??2.2.3后序遍歷
? ??2.2.4層序遍歷
? 思想
??代碼
??詳細(xì)過(guò)程
1.二叉樹的概念
1.1概念
? ? ? ? 一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合為空，或者是由一個(gè)根節(jié)點(diǎn)加上兩棵稱為左子樹和右子樹的二叉樹組成。
二叉樹的特點(diǎn)：
（1）每個(gè)結(jié)點(diǎn)最多有兩棵子樹，即二叉樹不存在度大于2的結(jié)點(diǎn)。
（2）二叉樹的子樹有左右之分，其子樹的次序不能顛倒。
1.2存儲(chǔ)方式
? ? ? ? 二叉樹可以采用線性結(jié)構(gòu)或者非線性結(jié)構(gòu)實(shí)現(xiàn)。線性結(jié)構(gòu)有 比如堆，本文使用非線性結(jié)構(gòu)實(shí)現(xiàn)。既然非線性，那就肯定要使用類似鏈表的結(jié)構(gòu)。在這里，由于二叉樹每個(gè)節(jié)點(diǎn)都有最多兩個(gè)孩子，我們使用有 一個(gè)數(shù)據(jù)域 和 兩個(gè)指針域 的結(jié)構(gòu)來(lái)表示。
? ? ? ? 如下圖，左邊紅色框內(nèi)分別表示二叉樹的定義，以及每一個(gè)節(jié)點(diǎn)的結(jié)構(gòu)。右邊表示二叉樹的邏輯結(jié)構(gòu)。
1.3特殊的二叉樹?
（1）滿二叉樹
? ? ? ? 每一層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。
? ? ? ? 也就是說(shuō)，如果一個(gè)二叉樹的層數(shù)為h（根節(jié)點(diǎn)是第1層），且結(jié)點(diǎn)總數(shù)是(2^h) -1 ，則它就是滿二叉樹。比如下圖：
（2）完全二叉樹
? ? ? ? 完全二叉樹的葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)從左到右連續(xù)；前K-1層是滿的二叉樹。
? ? ? ? 如下四種，都是完全二叉樹。值得注意的是，滿二叉樹也是完全二叉樹，其倒數(shù)第二層是滿的，最后一層葉子節(jié)點(diǎn)從左到右連續(xù)，滿足。
（3）非完全二叉樹
? ? ? ? 非完全二叉樹也很好理解，不滿足完全二叉樹的條件。比如下面兩種，左邊是最后一層葉子節(jié)點(diǎn)從左到右不連續(xù)，右邊是倒數(shù)第二層沒(méi)有滿。
1.4規(guī)律
1.有h層（根節(jié)點(diǎn)算第一層）的滿二叉樹，最后一層的節(jié)點(diǎn)個(gè)數(shù)為 2^(h-1) 。
? ? ? ? 這并不難理解，由于每一個(gè)節(jié)點(diǎn)都有兩個(gè)孩子節(jié)點(diǎn)，相當(dāng)于每一層的節(jié)點(diǎn)個(gè)數(shù)都是上一層的兩倍。第一層是1個(gè)，第二層2個(gè)……第h層是2^(h-1) 個(gè)。觀察下圖結(jié)構(gòu)可以驗(yàn)證。
2.有h層（根節(jié)點(diǎn)為第一層）的滿二叉樹總結(jié)點(diǎn)個(gè)數(shù) 為 2^h -1 。
? ? ? ? ?這并不難理解。2^h -1 可以看作 2^(h-1) + 2^(h-1) -1 。2^(h-1) 就是滿二叉樹最后一層的節(jié)點(diǎn)個(gè)數(shù)，所以? 2^(h-1) -1 可以看作，前 h-1 層的節(jié)點(diǎn)個(gè)數(shù)，事實(shí)上也是這樣，對(duì)照上面的滿二叉樹或者任一滿二叉樹都可以得到這樣的結(jié)論。
3.二叉樹總節(jié)點(diǎn)個(gè)數(shù)=總度數(shù)+1。
? ? ? ? 如下，把除了根節(jié)點(diǎn)之外，所有節(jié)點(diǎn)都和鏈接它的那根線相連，當(dāng)作一個(gè)小整體。有多少個(gè)小整體，就有多少個(gè)節(jié)點(diǎn)（不包括根節(jié)點(diǎn)）。由于每一個(gè)小整體里面有一根線和一個(gè)節(jié)點(diǎn)，這條線可以看作度，所以有多少個(gè)節(jié)點(diǎn)就有多少個(gè)度（除去根節(jié)點(diǎn)）。所以，總節(jié)點(diǎn)個(gè)數(shù)=度數(shù)+1。相當(dāng)于其他所有節(jié)點(diǎn)個(gè)數(shù)+1。
2.二叉樹的實(shí)現(xiàn)
2.1表現(xiàn)方式
? ? ? ? 上文已有說(shuō)明，用結(jié)構(gòu)體，里面包含一個(gè)數(shù)據(jù)域和兩個(gè)指針域，指針域分別指向左右孩子節(jié)點(diǎn)。
typedef char BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
}BTNode;2.2遍歷
? ? ? ? 本文講述的是遞歸實(shí)現(xiàn)遍歷，所以要關(guān)注遞歸的幾個(gè)注意點(diǎn)：
?遞歸的兩個(gè)基本要素：
????1、遞歸關(guān)系式：確定關(guān)系式，即原問(wèn)題是如何分解為子問(wèn)題的
????2、遞歸出口：確定遞歸到什么時(shí)候終止。同時(shí)、一個(gè)遞歸函數(shù)我們是默認(rèn)它能夠完成所需功能的。
2.2.1前序遍歷
思想
前序遍歷順序：根、左子樹、右子樹。
? ? ? ? 上述二叉樹，前序遍歷順序是：A -> B -> D -> E -> C。從遞歸兩個(gè)基本要素來(lái)看，遞歸關(guān)系式就是：先打印根節(jié)點(diǎn)數(shù)據(jù)，然后前序遍歷根節(jié)點(diǎn)的左子樹，遍歷完之后，再前序遍歷根節(jié)點(diǎn)的右子樹。? ?遞歸出口：當(dāng)遍歷到的節(jié)點(diǎn)為空，那么就return。
? ? ? ? 如下代碼，為什么前序遍歷左右子樹可以直接 PrevOrder(root->left) ;? 和? PrevOrder(root->right)；? ?因?yàn)?，我?strong>默認(rèn)這個(gè)遞歸函數(shù)是可以實(shí)現(xiàn)其功能的，現(xiàn)在暫時(shí)不要進(jìn)行更深層次的思考。
代碼
//前序遍歷
void PrevOrder(BTNode* root)
{
if (root == NULL) //終止條件
{
printf("NULL ");
return;
}
printf("%c ", root->data); // 先打印當(dāng)前節(jié)點(diǎn)
PrevOrder(root->left); // 前序遍歷左子樹
PrevOrder(root->right); // 前序遍歷右子樹
}詳細(xì)分析?
? ? ? ? 看到代碼，先不要疑惑，一步一步走，最開始一定是要生成一個(gè)對(duì)應(yīng)的二叉樹，然后才可以前序遍歷，如下：
? ? ? ? 一開始傳入的 a 節(jié)點(diǎn)，就是根節(jié)點(diǎn)為PrevOrder() 的root參數(shù)，進(jìn)入該?函數(shù)之后，會(huì)判斷其是否為空？不為空，那么打印該節(jié)點(diǎn)的數(shù)據(jù)，即"A"，然后PrevOrder(root->left); 注意，現(xiàn)在的 root 是 a，那么 a 節(jié)點(diǎn)的左孩子是 b 節(jié)點(diǎn)，相當(dāng)于以 b 節(jié)點(diǎn)為 root 參數(shù)，又進(jìn)入了 PrevOrder() 函數(shù)，并進(jìn)行和之前類似的操作。
? ? ? ? 但是，這里要注意，進(jìn)入PrevOrder(root->left); 之后，以 a 節(jié)點(diǎn)為函數(shù)的 root 參數(shù)那塊并沒(méi)有結(jié)束，因?yàn)樵谀菈K函數(shù)里進(jìn)入了以 b 節(jié)點(diǎn)為 root 的函數(shù)，如下過(guò)程。一直到進(jìn)入 d 節(jié)點(diǎn)的左孩子，d 節(jié)點(diǎn)的左孩子為NULL，那么NULL為參數(shù) root ，進(jìn)入 PrevOrder()?函數(shù)，毫無(wú)疑問(wèn)根據(jù) if 語(yǔ)句會(huì)打印NULL并return。
? ? ? ? ?這里又來(lái)問(wèn)題了，上圖的 return 是 return 到哪里呢？是直接return 到以根節(jié)點(diǎn)為 root 參數(shù)那里嗎？顯然不是，實(shí)際上是返回"上一級(jí)"，如下圖，通過(guò)步驟4（黑色數(shù)字標(biāo)記），返回到 d 節(jié)點(diǎn)為root參數(shù)的那里，那么返回之后執(zhí)行什么呢？根據(jù)前序遍歷函數(shù)的代碼，還要PrevOrder(root->right); 由于 root 是 d 節(jié)點(diǎn)，其右孩子也是NULL，所以也直接返回，即步驟5、6。
? ? ? ? 到這里，以 d 節(jié)點(diǎn)為參數(shù) root 的過(guò)程算是執(zhí)行完畢，但是，該過(guò)程也是以 b 節(jié)點(diǎn)為 root參數(shù)的中間過(guò)程，所以該過(guò)程結(jié)束后，也要返回以 b節(jié)點(diǎn)為 root 參數(shù)的進(jìn)程當(dāng)中。如步驟7。
? ? ? ??把上圖的最后一步，當(dāng)作第一步來(lái)看，繼續(xù)分析接下來(lái)的過(guò)程。如下圖：
? ? ? ? 既然以 b 節(jié)點(diǎn)為 root 參數(shù)的這個(gè)過(guò)程，其 PrevOrder(root->left);? 過(guò)程已經(jīng)完成，接下來(lái)就是執(zhí)行??PrevOrder(root->right);? ?這里 b 節(jié)點(diǎn)的右孩子是 e 節(jié)點(diǎn)，如下，過(guò)程和上面比較相似，也就不詳細(xì)說(shuō)明，步驟按順序來(lái)即可。?
? ? ? ? 在以 b 節(jié)點(diǎn)為 root 參數(shù)的過(guò)程中，PrevOrder(root->right); 也結(jié)束之后，該過(guò)程就結(jié)束了，返回“上一級(jí)”，其上一級(jí)是以根節(jié)點(diǎn)為root 參數(shù)。那么返回到哪里呢？
? ? ? ? 如下圖，由于以b節(jié)點(diǎn)為root 參數(shù)的過(guò)程，實(shí)際上也是以根節(jié)點(diǎn)為root 參數(shù)的過(guò)程里面的一部分，所以該過(guò)程結(jié)束之后，自然是執(zhí)行下面的代碼。執(zhí)行 PrevOrder(root->right);? 在該過(guò)程里面，root是根節(jié)點(diǎn)，所以其右孩子是c 節(jié)點(diǎn)。
? ? ? ? 以 c 節(jié)點(diǎn)為root 參數(shù)的過(guò)程也不詳細(xì)展開，都大體差不多，按照下面標(biāo)記的順序來(lái)看即可。最后，執(zhí)行完該過(guò)程，那么以根節(jié)點(diǎn)為root 參數(shù)的過(guò)程才算是執(zhí)行完畢，整個(gè)函數(shù)也就執(zhí)行完，前序遍歷結(jié)束。
? ? ? ? 其整個(gè)過(guò)程大致如下所示，可以看到是一層一層下去，然后返回來(lái)。
? ? ? ? 當(dāng)然，也可以如下一樣理解，順序按照標(biāo)記的順序來(lái)即可：
2.2.2中序遍歷
中序遍歷順序：左子樹、根，右子樹。
? ? ? ? 中序遍歷實(shí)際上和前序遍歷差不多，也就是打印數(shù)據(jù)的順序有所區(qū)別，代碼如下?？梢钥闯?，和前序遍歷的區(qū)別僅僅在于：先遍歷左子樹，還是先打印當(dāng)前節(jié)點(diǎn)的值。
? ? ? ? 其根據(jù)遞歸的思想來(lái)看也是。遞歸終止條件自然一樣。那么遞歸關(guān)系式：先中序遍歷左子樹，遍歷完之后，打印根節(jié)點(diǎn)，然后中序遍歷右子樹，整個(gè)中序遍歷結(jié)束。 就是如此簡(jiǎn)單，從代碼上來(lái)看也是，默認(rèn)其能實(shí)現(xiàn)遞歸過(guò)程，直接這樣寫。
? ? ? ? 其詳細(xì)分析過(guò)程和前序遍歷差不多，可以自己嘗試畫一畫，對(duì)理解遞歸遍歷二叉樹很有幫助?。?！
//中序遍歷
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}2.2.3后序遍歷
后序遍歷順序：左子樹、右子樹，根。
? ? ? ? 后序遍歷和中序遍歷同理。其遞歸關(guān)系式：先遍歷左子樹，遍歷結(jié)束之后，再遍歷右子樹，最后打印根節(jié)點(diǎn)。
//后序遍歷
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}2.2.4層序遍歷
思想
層序遍歷：按照層數(shù) 從上到下，每一層從左到右來(lái)遍歷。
? ? ? ? 層序遍歷，又被稱作廣度優(yōu)先遍歷。遍歷結(jié)果如下圖，這樣子的遍歷方式，當(dāng)然不是直接遞歸就可以實(shí)現(xiàn)的，而是要根據(jù)隊(duì)列 “先入先出” 的特點(diǎn)，借助隊(duì)列來(lái)完成。
? ? ? ? 其主要完成的方法就是：先把節(jié)點(diǎn) a 入隊(duì)，然后取到該節(jié)點(diǎn)，并出隊(duì)，打印該節(jié)點(diǎn)的值（"A"），并且將節(jié)點(diǎn) a 的左孩子入隊(duì)，右孩子入隊(duì)。接下來(lái)就是重復(fù)類似的過(guò)程：取隊(duì)頭節(jié)點(diǎn)，然后出隊(duì)，打印取出的節(jié)點(diǎn)數(shù)據(jù)，將取出節(jié)點(diǎn)的左右孩子分別入隊(duì)。 一直到隊(duì)列為空。
代碼
? ? ? ? 如下，由于while 循環(huán)結(jié)束條件是隊(duì)列為空，所以一開始要先入隊(duì)一個(gè)數(shù)據(jù)。
? ? ? ? 循環(huán)過(guò)程，每次都把隊(duì)頭數(shù)據(jù)取出來(lái)，用temp 指針指向該數(shù)據(jù)，然后出隊(duì)，打印temp 指向的節(jié)點(diǎn)的數(shù)據(jù)。然后把temp 左右孩子節(jié)點(diǎn)入隊(duì)。
? ? ? ? 注意，這里入隊(duì)順序不能變，必須是先入左孩子，再入右孩子。因?yàn)槊總€(gè)節(jié)點(diǎn)最多只有兩個(gè)孩子節(jié)點(diǎn)，每次按順序先入左孩子，隊(duì)列里每個(gè)節(jié)點(diǎn)的左孩子就先出，這才符合層序遍歷的要求。
//層序遍歷 廣度優(yōu)先遍歷
void LeafSort(BTNode* root)
{
assert(root);
//創(chuàng)建一個(gè)隊(duì)列
Queue p;
QueueInit(&p);
if (root)
QueuePush(&p, root);
while (!QueueEmpty(&p))
{
BTNode* temp = QueueFront(&p);//先把第一個(gè)取出來(lái)
QueuePop(&p);
printf("%c ", temp->data);
if (temp->left)
{
QueuePush(&p, temp->left);
}
if (temp->right)
{
QueuePush(&p, temp->right);
}
}
return;
}詳細(xì)過(guò)程
? ? ? ? 過(guò)程推導(dǎo)如下，相較二叉樹遞歸很容易。
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-855969.html
? ? ? ? 關(guān)于二叉樹的遍歷就先介紹到這里啦?。?span toymoban-style="hidden">文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-855969.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹的前序遍歷、中序遍歷、后序遍歷、層序遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
