W...Y的主頁???
代碼倉庫分享 ??
之前我們實現(xiàn)了用順序表完成二叉樹(也就是堆)，順序二叉樹的實際作用就是解決堆排序以及Topk問題。
今天我們要學(xué)習(xí)的內(nèi)容是鏈?zhǔn)蕉鏄?，并且實現(xiàn)鏈?zhǔn)蕉鏄洌@篇博客與遞歸息息相關(guān)！
目錄
鏈?zhǔn)酱鎯?/p>
二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實現(xiàn)
鏈?zhǔn)蕉鏄涞目焖賱?chuàng)建
二叉樹的遍歷
前序、中序以及后序遍歷
前序遍歷的實現(xiàn)
中序遍歷的實現(xiàn)
后序遍歷實現(xiàn)
節(jié)點個數(shù)以及高度
總結(jié)點個數(shù)
葉子節(jié)點個數(shù)
第k層節(jié)點個數(shù)
整個代碼模板以及驗證
鏈?zhǔn)酱鎯?/h2>
什么是鏈?zhǔn)酱鎯?，就是用鏈來指示元素的邏輯關(guān)系。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，而我們今天學(xué)習(xí)的是二叉鏈表，又稱鏈?zhǔn)蕉鏄洹?br>
我們一般用鏈表來表示一棵二叉樹，通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址 。
typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點左孩子
struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點右孩子
BTDataType _data; // 當(dāng)前節(jié)點值域
}對于鏈?zhǔn)蕉鏄?，我們與其他前面的鏈表、順序表、堆……數(shù)據(jù)結(jié)構(gòu)有所不同，我們針對這一塊并不是增刪查改，為什么呢?
因為鏈?zhǔn)蕉鏄涞拇鎯Ψ绞?，就是把每一個節(jié)點封裝在結(jié)構(gòu)體中然后進(jìn)行鏈接，?而我們進(jìn)行增刪查改沒有必要在這么復(fù)雜的結(jié)構(gòu)中實現(xiàn)，當(dāng)我有每個節(jié)點的左右指針時，我可以隨心所欲，在哪里都可以進(jìn)行插入刪除。如果非得使用增刪查改，我們就可以使用簡單一些的數(shù)據(jù)結(jié)構(gòu)進(jìn)行。
所以我們學(xué)習(xí)鏈?zhǔn)蕉鏄涫菫榱私o我們后面的高級數(shù)據(jù)結(jié)構(gòu)AVL、紅黑樹打基礎(chǔ)的。所以我們也要認(rèn)真學(xué)?。?！
二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實現(xiàn)
鏈?zhǔn)蕉鏄涞目焖賱?chuàng)建
我們?yōu)榱丝焖賹崿F(xiàn)鏈?zhǔn)蕉鏄洌瑥闹懈惺艿芥準(zhǔn)蕉鏄涞慕Y(jié)構(gòu)，我們快速手動生成一個鏈?zhǔn)蕉鏄洹?/p>
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
int val;
}BTNode;
BTNode* BuyNode(int x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
int main(void)
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return 0;
}我們創(chuàng)建了鏈?zhǔn)蕉鏄涞幕窘Y(jié)構(gòu)，左指針右指針以及存儲的值，然后開辟空間將里面的所有內(nèi)容初始化。在main函數(shù)中手動插入了1、2、3、4、5、6封裝在結(jié)構(gòu)體中，然后依照下圖進(jìn)行鏈接快速得到一個鏈?zhǔn)蕉鏄洹?img src="https://imgs.yssmx.com/Uploads/2023/10/725131-4.png" alt="模擬實現(xiàn)鏈?zhǔn)蕉鏄浼捌浣Y(jié)構(gòu)學(xué)習(xí)——【數(shù)據(jù)結(jié)構(gòu)】,數(shù)據(jù)結(jié)構(gòu),c語言,算法" referrerpolicy="no-referrer" />
?下面依照創(chuàng)建完成的鏈?zhǔn)蕉鏄淅^續(xù)學(xué)習(xí)。
二叉樹的遍歷
前序、中序以及后序遍歷
學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進(jìn)行相應(yīng)的操作，并且每個節(jié)點只操作一次。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。
按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：
1. 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹前。
2. 中序遍歷(Inorder Traversal)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間）。
3. 后序遍歷(Postorder Traversal)——訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后。
由于被訪問的結(jié)點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。?
前序遍歷的實現(xiàn)
針對前序遍歷，我們記住先訪問左樹，再訪問根，最后再訪問右樹。我們可以先手動遍歷一遍，將一顆大樹分解成三部分（左樹、根、右樹），再將左樹看作樹繼續(xù)分成左樹右樹與根，右數(shù)也一樣，將其一直進(jìn)行分解，直到左右樹為空為止即可停止。
// 二叉樹前序遍歷
void PreOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}?在前序遍歷中，我們使用遞歸進(jìn)行。如果root為NULL證明樹為空，直接返回即可。當(dāng)進(jìn)入下面代碼時，前序遵循的是根、左樹、右樹。所以我們先將根打印出來，然后遍歷左樹。當(dāng)進(jìn)入左樹遞歸時，root->left進(jìn)入左樹，那根的左子節(jié)點就變成了左樹的根，打印出來繼續(xù)遞歸，依次類推。而右樹也是一樣的，將左樹遍歷完后，我們將遞歸右數(shù)，先將左樹遞歸的所有函數(shù)銷毀，進(jìn)入root->right中進(jìn)行遞歸，根的右子節(jié)點成為右樹的根，打印出進(jìn)行遞歸，一直遵循根、左樹、右樹進(jìn)行。
遞歸圖解如下：
?雖然代碼非常簡潔，但是理解起來不太容易，我們不能只記住代碼如何寫，應(yīng)該理解其中的原理才行。
中序遍歷的實現(xiàn)
只要我們理解了前序遍歷，那么中序后序都是非常簡單的存在。只需記?。鹤髽洹⒏?、右樹，然后寫出遞歸即可
void InOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}?有沒有發(fā)現(xiàn)這串代碼與前序遍歷非常相似，只是將兩行代碼交換位置就可以實現(xiàn)。我們先將左樹的內(nèi)容遞歸完然后打印，再打印根的，最后再打印右樹的即可?？梢詤⒖记爸帽闅v進(jìn)行推理。
這里如果實在理解不了的可以認(rèn)為調(diào)用InOrder(root->left)是遍歷打印左樹，printf是打印根，而調(diào)用遞歸InOrder(root->right)是為了遍歷打印右樹。
后序遍歷實現(xiàn)
我相信大家已經(jīng)知道函數(shù)怎么寫了，那我就直接給模板：
void PostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}?下面我們更進(jìn)一步的學(xué)習(xí)鏈?zhǔn)蕉鏄涞慕Y(jié)構(gòu)，上強(qiáng)度?。?！
節(jié)點個數(shù)以及高度
總結(jié)點個數(shù)
我們需要建立一個函數(shù)，求出整個二叉樹所有的節(jié)點個數(shù)。
有人一定會想直接全部遍歷一遍然后創(chuàng)建一個全局變量用來統(tǒng)計個數(shù)就可以了。沒錯這個方法是可行的，我們剛才說的二叉樹的遍歷，然后在這里用一遍不就拿下來了。
int size = 0;
int TreeSize(BTNode* root)
{
if (root == NULL)
return 0;
else
++size;
TreeSize(root->left);
TreeSize(root->right);
return size;
}我們直接遍歷整棵樹，先遍歷左樹、再遍歷右數(shù)，每遍歷一個節(jié)點size++即可。
但是這個函數(shù)有一個極大的缺點，當(dāng)我們使用函數(shù)時，我們可以在任意一個位置去調(diào)用，全局變量是存儲在靜態(tài)區(qū)的，不會隨著函數(shù)的結(jié)束而銷毀，當(dāng)我們調(diào)用過一次后，?再一次去調(diào)用此函數(shù)，如果沒有及時將size歸零，結(jié)果將會累加起來成為錯誤的結(jié)果。
我們應(yīng)該優(yōu)化一下程序：
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}直接使用遞歸，將左右子樹包含在返回值中，我們在后面加上1，如果遞歸成功將+1，然后返回最后遞歸之和。
我們可以做個比喻：在一個大學(xué)中校長想要統(tǒng)計全校的人數(shù)，校長不可能親自挨家挨戶訪問查人，它會通知每個院的院長，然后院長通知每個系的系主任，由系主任通知導(dǎo)員，最后由導(dǎo)員通知每個班的班長來統(tǒng)計人數(shù)。一級一級的下放任務(wù)。而這個遞歸也是如此，統(tǒng)計總節(jié)點個數(shù)就是一級一級下方給各個節(jié)點計數(shù)。
?
葉子節(jié)點個數(shù)
需要求出鏈?zhǔn)蕉鏄涞娜~子節(jié)點個數(shù)，葉節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點；
大致原理都是一樣的，只是條件不同。我們需要葉子節(jié)點就必須是度為0的節(jié)點，所以一個節(jié)點的root->right == NULL && root->left == NULL?這是必要條件，然后我們就應(yīng)該去遍歷二叉樹的左子樹與右子樹去尋找滿足條件的節(jié)點。最后求出左右子樹的葉子節(jié)點之和即可。
代碼實現(xiàn)：
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->right == NULL && root->left == NULL)
return 1;
return TreeLeafSize(root->right) + TreeLeafSize(root->left);
}第k層節(jié)點個數(shù)
當(dāng)我們需要某一層的節(jié)點個數(shù)，我們也需要創(chuàng)建一個函數(shù)來進(jìn)行，那我們應(yīng)該怎么弄呢？
還是一級一級去派遣，假設(shè)我們需要第三層的節(jié)點個數(shù)，當(dāng)我們剛進(jìn)入在第一層時，我們距離目標(biāo)層數(shù)還有兩層之差，當(dāng)我們遍歷到第二層時，我們距離目標(biāo)還有一層，當(dāng)我們進(jìn)入目標(biāo)層后我們就要進(jìn)行遍歷節(jié)點， 統(tǒng)計出左右子樹k層節(jié)點之和返回即可。
int TreeKLevel(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}需要注意的是我們先得使用assert進(jìn)行斷言，防止樹為空。
整個代碼模板以及驗證
下面是增章全部代碼以及測試用例：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
int val;
}BTNode;
BTNode* BuyNode(int x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
void PostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
//總節(jié)點個數(shù)
//int TreeSize(BTNode* root)
//{
// static int size = 0;
// if (root == NULL)
// return 0;
// else
// ++size;
// TreeSize(root->left);
// TreeSize(root->right);
// return size;
//}
//int size = 0;
//int TreeSize(BTNode* root)
//{
// if (root == NULL)
// return 0;
// else
// ++size;
// TreeSize(root->left);
// TreeSize(root->right);
// return size;
//}
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//葉子節(jié)點個數(shù)
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->right == NULL && root->left == NULL)
return 1;
return TreeLeafSize(root->right) + TreeLeafSize(root->left);
}
//第k層節(jié)點個數(shù)
int TreeKLevel(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}
int main(void)
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
PrevOrder(node1);
printf("\n");
InOrder(node1);
printf("\n");
PostOrder(node1);
printf("\n%d", TreeSize(node1));
printf("\n%d", TreeSize(node1));
printf("\n%d", TreeLeafSize(node1));
printf("\n%d", TreeKLevel(node1, 2));
return 0;
}代碼運(yùn)行結(jié)果如下：
運(yùn)行結(jié)果分別為前置遍歷、中序遍歷、后序遍歷、總節(jié)點個數(shù)(兩次)、葉子節(jié)點個數(shù)、第二層節(jié)點個數(shù)
?參考下圖均正確?。?！文章來源：http://www.zghlxwxcb.cn/news/detail-725131.html
以上就是本次博客的全部內(nèi)容，希望可以幫助到大家?。?！支持博主的一鍵三連一下，謝謝大家??文章來源地址http://www.zghlxwxcb.cn/news/detail-725131.html
到了這里，關(guān)于模擬實現(xiàn)鏈?zhǔn)蕉鏄浼捌浣Y(jié)構(gòu)學(xué)習(xí)——【數(shù)據(jù)結(jié)構(gòu)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
