C語言詳解實現(xiàn)鏈?zhǔn)蕉鏄涞谋闅v與相關(guān)接口
前言
二叉樹的順序結(jié)構(gòu)就是用數(shù)組來存儲，而「數(shù)組」一般只適合表示「滿二叉樹」或「完全二叉樹」，因為不是完全二叉樹會有「空間的浪費」。
普通二叉樹的增刪查改沒有意義，主要學(xué)習(xí)它的結(jié)構(gòu)，要加上搜索樹的規(guī)則，才有價值。
一、二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)
在學(xué)習(xí)二叉樹的基本操作前，需先要創(chuàng)建一棵二叉樹，此處我們手動快速創(chuàng)建一棵簡單的二叉樹，快速進入二叉樹操作學(xué)習(xí)，等二叉樹結(jié)構(gòu)了解的差不多時，我們反過頭再來研究二叉樹真正的創(chuàng)建方式。
#include<stdio.h> // perror, printf
#include<stdlib.h> // malloc
typedef char BTDataType;
// 定義二叉樹的節(jié)點
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 動態(tài)申請一個新節(jié)點
BTNode* BuyNode(BTDataType x)
{
//
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->left = newnode->right = NULL;
return newnode;
}
// 二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)
BTNode* CreatBinaryTree()
{
// 創(chuàng)建多個節(jié)點
BTNode* node_A = BuyNode('A');
BTNode* node_B = BuyNode('B');
BTNode* node_C = BuyNode('C');
BTNode* node_D = BuyNode('D');
BTNode* node_E = BuyNode('E');
BTNode* node_F = BuyNode('F');
// 用鏈來指示節(jié)點間的邏輯關(guān)系
node_A->left = node_B;
node_A->right = node_C;
node_B->left = node_D;
node_C->left = node_E;
node_C->right = node_F;
return node_A;
}注意：上述代碼并不是創(chuàng)建二叉樹的方式，真正創(chuàng)建二叉樹方式后續(xù)講解。
二、二叉樹的遍歷方式
1.1 遍歷方式的規(guī)則
學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進行相應(yīng)的操作，并且每個節(jié)點只操作一次。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎(chǔ)。
按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷 和 層序遍歷：
- 前序遍歷(Preorder Traversal) ：訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前。
根 --> 左子樹 --> 右子樹
（比如上圖中，訪問的路徑為：A B D NULL NULL NULL C E NULL NULL F NULL NULL）
- 中序遍歷(Inorder Traversal) ：訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間）。
左子樹 --> 根 --> 右子樹
（比如上圖中，訪問的路徑為：NULL D NULL B NULL A NULL E NULL C NULL F NULL）
計算中序遍歷訪問路徑可以用簡單直觀的投影法：
- 后序遍歷(Postorder Traversal)：訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后。
左子樹 --> 右子樹 --> 根
（比如上圖中，訪問的路徑為：NULL NULL D NULL B NULL NULL E NULL NULL F C A）
- 層序遍歷(LevelOrder traversal)：一層一層的走
（比如上圖中，訪問的路徑為：A B C D NULL E F NULL NULL NULL NULL NULL NULL）
由于被訪問的結(jié)點必是「某子樹的根」，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。
深度優(yōu)先遍歷：前序、中序、后序
廣度優(yōu)先遍歷：層序
【理解前/中/后序遍歷的思路】
前中后序遍歷中，每一顆子樹都會被分為（根、左子樹、右子樹）三部分來看待，分而治之。
舉個栗子：
校長想要統(tǒng)計全校學(xué)生的人數(shù)，他并不會自己挨個挨個去數(shù)，而是把每個年級的負(fù)責(zé)人叫過來，各年級負(fù)責(zé)人又把各班的班主任叫過來，各班主任又把各班班長叫過來，班長統(tǒng)計人數(shù)后，大家把結(jié)果再層層上報，最終傳回到校長這里，就知道學(xué)校總?cè)藬?shù)了。
1.2 前序遍歷
代碼是非常簡單的：
// 二叉樹前序遍歷
void PreOrder(BTNode* root)
{
if (root) // 先判斷樹是否為空
{
// 根 --> 左子樹 --> 右子樹
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
}
int main()
{
// 創(chuàng)建一顆鏈?zhǔn)蕉鏄?
BTNode* root = CreatBinaryTree();
// 前序遍歷
PreOrder(root); // A B D C E F
return 0;
}
前序遍歷函數(shù)遞歸調(diào)用圖解：每個函數(shù)調(diào)用，都會建立一個自己的棧幀。
前序遍歷遞歸圖解：
1.3 中序遍歷
// 二叉樹中序遍歷
void InOrder(BTNode* root)
{
if (root) // 先判斷樹是否為空
{
// 左子樹 --> 根 --> 右子樹
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
}
1.4 后序遍歷
// 二叉樹后序遍歷
void PostOrder(BTNode* root)
{
if (root) // 先判斷樹是否為空
{
// 左子樹 --> 右子樹 --> 根
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
}
1.5 層序遍歷
層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設(shè)二叉樹的根節(jié)點所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第2層上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點的過程就是層序遍歷。
核心思路：
用一個隊列來進行層序遍歷：
- 先入第一層的節(jié)點（根節(jié)點）
- 上一層出來后，再入下一層（即它的左右孩子節(jié)點）
比如：
先入根節(jié)點 A
根節(jié)點 A 出來后，再入它的孩子節(jié)點 B 和 C
節(jié)點 B 出來后，再入它的孩子節(jié)點 D 和 E，節(jié)點 C 出來后，再入它的孩子節(jié)點 F ……
// 二叉樹的層序遍歷
void LevelOrder(BTNode* root)
{
LinkQueue q; // 鏈?zhǔn)疥犃?
QueueInit(&q); // 初始化隊列
// 樹的根節(jié)點root不為空，把根節(jié)點入隊
if (root)
{
QueuePush(&q, root);
}
// 當(dāng)隊列不為空時，不斷的出隊，以及入隊根節(jié)點root的左右子樹
while (!QueueEmpty(&q))
{
// 當(dāng)前樹的根節(jié)點出隊
BTNode* front = QueueFront(&q); // 獲取隊頭元素
printf("%c ", front->data); // 打印節(jié)點值
QueuePop(&q); // 出隊
// 如果當(dāng)前樹根的左右孩子不為空，則分別入隊
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestroy(&q); // 銷毀隊列
}
三、二叉樹的相關(guān)接口實現(xiàn)
3.1 二叉樹節(jié)點個數(shù)
// 二叉樹節(jié)點個數(shù)
/* 方法一：
1、遞歸遍歷 -- 用全局變量/靜態(tài)局部變量來記錄節(jié)點個數(shù)
2、遞歸遍歷 -- 函數(shù)外定義一個局部變量記錄節(jié)點個數(shù)，傳址給函數(shù)
*/
// 方法二：分而治之的思路
int BinaryTreeSize(BTNode* root)
{
if (root == NULL) // 1. 先判斷當(dāng)前訪問的節(jié)點是否為空
{
return 0;
}
// 2. 當(dāng)前節(jié)點不為空，節(jié)點個數(shù)累+1，則繼續(xù)訪問其左右子樹
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
3.2 二叉樹葉子節(jié)點個數(shù)
// 二叉樹葉子節(jié)點個數(shù)
/* 方法一：
1、遞歸遍歷 -- 用全局變量/靜態(tài)局部變量來記錄節(jié)點個數(shù)
2、遞歸遍歷 -- 函數(shù)外定義一個局部變量記錄節(jié)點個數(shù)，傳址給函數(shù)
*/
// 方法二：分而治之的思路
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL) // 1. 先判斷當(dāng)前訪問的節(jié)點是否為空
{
return 0;
}
// 2. 當(dāng)前節(jié)點不為空，它的左右孩子都為空，說明該節(jié)點是葉子節(jié)點
if (root->left == NULL && root->right == NULL)
{
return 1;
}
// 3. 當(dāng)前節(jié)點不為空，左右孩子不都為空，則繼續(xù)往下遍歷
return BinaryTreeLeafSize(root->left)
+ BinaryTreeLeafSize(root->right);
}3.3 二叉樹第 k 層節(jié)點個數(shù)
核心思路：
- 求當(dāng)前樹第 k 層的節(jié)點個數(shù) = 求左子樹第 k-1 層的節(jié)點個數(shù) + 求右子樹第 k-1 層的節(jié)點個數(shù)
- 比如：
- 求當(dāng)前樹（A）第 2 層的節(jié)點個數(shù)
- = 求左子樹（B）第 1 層的節(jié)點個數(shù) + 求右子樹（C）第 1 層的節(jié)點個數(shù)
- = 1 + 1
- = 2
如何知道這個節(jié)點是不是第 k 層的？我自己復(fù)習(xí)時是用的這個思路來寫，感覺容易理解些：
求二叉樹第 k 層的節(jié)點個數(shù)，我們從根節(jié)點開始往下遍歷（我在代碼中是根左右的順序），每遍歷一次 k 減 1一次，當(dāng) k == 1 時，說明我們遍歷到了第 k 層，我們此時訪問該層的節(jié)點，如果它不為空，則二叉樹第 k 層的節(jié)點個數(shù)就要+1。
// 二叉樹第k層節(jié)點個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL) // 1. 先判斷當(dāng)前訪問的節(jié)點是否為空
{
return 0;
}
if (k == 1) // 2. 當(dāng)前節(jié)點不為空，而k已經(jīng)減到1了，說明遍歷到了第k層，說明該節(jié)點是第k層的
{
return 1;
}
// 3. 還沒有遍歷到第k層，我們就繼續(xù)往下遍歷
return BinaryTreeLevelKSize(root->left, k - 1)
+ BinaryTreeLevelKSize(root->right, k - 1);
}
3.4 二叉樹的深度(高度)
核心思想：
當(dāng)前樹的深度 = Max(左子樹的深度，右子樹的深度) + 1
- root 是空節(jié)點：height ( root ) = 0
- root 是非空節(jié)點：height ( root ) = max ( height ( root->left ), height ( root->right ) ) + 1
// 二叉樹的深度(高度)
int BinaryTreeDepth(BTNode* root)
{
// 1. 先判斷當(dāng)前樹的根節(jié)點是否為空
if (root == NULL)
{
return 0;
}
// 2. 當(dāng)前樹的根節(jié)點不為空，分別計算其左右子樹的深度
int leftDepth = BinaryTreeDepth(root->left);
int rightDepth = BinaryTreeDepth(root->right);
// 3. 比較當(dāng)前樹左右子樹的深度，最大的那個+1 就是當(dāng)前樹的深度
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
有一道OJ題考到了該算法，鏈接如下：二叉樹的最大深度
3.5 二叉樹查找值為 x 的節(jié)點
核心思路：
先判斷是不是當(dāng)前節(jié)點，是就返回，不是就先去該節(jié)點的左子樹找，找到了就返回，左子樹沒找到，再去該節(jié)點的右子樹找。
// 二叉樹查找值為x的節(jié)點，若有則返回該節(jié)點的地址，若沒有則返回NULL
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL) // 1. 先判斷當(dāng)前訪問的節(jié)點是否為空
{
return NULL;
}
if (root->data == x) // 2. 判斷要找的x值節(jié)點是不是當(dāng)前節(jié)點
{
return root;
}
// 3. 不是當(dāng)前節(jié)點，則繼續(xù)去該節(jié)點的左子樹中找
BTNode* ret = BinaryTreeFind(root->left, x);
if (ret != NULL)
{
return ret; // 找到了返回地址
}
// 3. 還沒找到，再繼續(xù)去該節(jié)點的右子樹中找
ret = BinaryTreeFind(root->right, x);
if (ret != NULL)
{
return ret; // 找到了返回地址
}
// 4. 當(dāng)前節(jié)點及其左右子樹中都沒找到，返回NULL
return NULL;
}3.6 總結(jié) & 注意
二叉樹相關(guān)的算法，如果用的是遞歸遍歷，且代碼中需要一個變量在整個遞歸過程中去記錄什么信息，一定要注意，不要把這個變量直接定義成了局部變量。（因為每次遞歸調(diào)用，都會建立一個棧幀，各棧幀中的局部變量是彼此獨立的）
所以需要下面這樣做：
1、遞歸遍歷 – 用全局變量/靜態(tài)局部變量來記錄節(jié)點個數(shù)
2、遞歸遍歷 – 函數(shù)外定義一個局部變量記錄節(jié)點個數(shù)，傳址給函數(shù)
四、二叉樹的創(chuàng)建和銷毀
4.1 通過前序遍歷的字符串來構(gòu)建二叉樹
// 通過前序遍歷的字符串?dāng)?shù)組arr "ABD##E#H##CF##G##" 構(gòu)建二叉樹 BTNode* BinaryTreeCreate(BTDataType* arr, int size, int* pi);
4.2 二叉樹銷毀
// 二叉樹銷毀
// 一級指針(頭節(jié)點指針)，形參是實參的一份拷貝，函數(shù)內(nèi)改變形參的值，無法改變外部實參的值
// 所以我們需要在函數(shù)外置頭節(jié)點指針為NULL
void BinaryTreeDestroy(BTNode* root)
{
// 不建議使用前中序遍歷銷毀，如果節(jié)點先被銷毀，就變成隨機值了，不知道它的左右子樹位置了
// 所以我們采用后序遍歷銷毀
if (root)
{
BinaryTreeDestroy(root->left);
BinaryTreeDestroy(root->right);
free(root);
}
}
int main()
{
// 創(chuàng)建一顆鏈?zhǔn)蕉鏄?
BTNode* root = CreatBinaryTree();
// 銷毀二叉樹
BinaryTreeDestroy(root);
// 頭節(jié)點指針置NULL
root = NULL;
return 0;
}4.3 判斷二叉樹是否是完全二叉樹
核心思路：
層序遍歷時，把空節(jié)點也入隊列
- 完全二叉樹，「非空節(jié)點」是連續(xù)的，則「空節(jié)點」是連續(xù)的。
- 非完全二叉樹，「非空節(jié)點」不是連續(xù)的，則「空節(jié)點」不是連續(xù)的。
所以在出隊時，判斷一下，出到第一個「空節(jié)點」時，跳出循環(huán)；
在下面重新寫一個循環(huán)繼續(xù)出隊，并檢查出隊元素：
- 如果「第一個空節(jié)點」后面的全是「空節(jié)點」，說明是完全二叉樹
- 如果「第一個空節(jié)點」后面的有「非空節(jié)點」，說明是非完全二叉樹
// 判斷二叉樹是否是完全二叉樹（利用層序遍歷的思想來判斷）
bool BinaryTreeComplete(BTNode* root)
{
LinkQueue q; // 鏈?zhǔn)疥犃?
QueueInit(&q); // 初始化隊列
// 樹的根節(jié)點root不為空，把根節(jié)點入隊
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
// 當(dāng)前樹的根節(jié)點出隊
BTNode* front = QueueFront(&q); // 獲取隊頭元素
QueuePop(&q); // 出隊
// @@@ 出隊的節(jié)點中，出到第一個空節(jié)點時，跳出循環(huán) @@@
if (front == NULL)
{
break;
}
// 不管當(dāng)前樹根的左右孩子是否為空，都分別入隊
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
// @@@ 出隊的節(jié)點中，出到第一個空節(jié)點時，跳出上面循環(huán) @@@
// 在這里繼續(xù)出隊：
// 1、如果隊列中全是空節(jié)點，則是完全二叉樹
// 2、如果隊列中有非空節(jié)點，則是非完全二叉樹
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q); // 獲取隊頭元素
QueuePop(&q); // 出隊
// @@@ 出隊的節(jié)點中，如果出現(xiàn)非空節(jié)點，說明是非完全二叉樹 @@@
if (front)
{
QueueDestroy(&q); // 銷毀隊列
return false;
}
}
QueueDestroy(&q); // 銷毀隊列
// @@@ 出隊的節(jié)點中，如果沒有出現(xiàn)非空節(jié)點，說明是完全二叉樹 @@@
return true;
}到此這篇關(guān)于C語言詳解實現(xiàn)鏈?zhǔn)蕉鏄涞谋闅v與相關(guān)接口的文章就介紹到這了,更多相關(guān)C語言鏈?zhǔn)蕉鏄浔闅v內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本篇文章是對c語言知識點的一些補遺進行詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++通過循環(huán)實現(xiàn)猜數(shù)字小游戲
這篇文章主要為大家詳細(xì)介紹了C++通過循環(huán)實現(xiàn)猜數(shù)字小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-09-09
c語言中單引號和雙引號的區(qū)別(順利解決從字符串中提取IP地址的困惑)
c語言中的單引號和雙引號可是有很大區(qū)別的，使用之前一定要了解他們之間到底有什么不同，下面小編就給大家詳細(xì)的介紹一下吧，對此還不是很了解的朋友可以過來參考下2013-07-07
vc++ 監(jiān)控指定路徑下文件變化實現(xiàn)代碼
這篇文章主要介紹了vc++ 監(jiān)控指定路徑下文件變化實現(xiàn)代碼,需要的朋友可以參考下2019-04-04
這篇文章主要介紹了C++編程中對設(shè)計模式中的策略模式的運用,需要的朋友可以參考下2016-03-03
C++線性表深度解析之動態(tài)數(shù)組與單鏈表和棧及隊列的實現(xiàn)
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)動態(tài)數(shù)組、單鏈表、棧、隊列，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要介紹了C++中頭文件的概念與基本編寫方法,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-12-12
折半查找法也叫做?分查找,顧名思義就是把數(shù)據(jù)分成兩半,再判斷所查找的key在哪?半中,再重復(fù)上述步驟知道找到?標(biāo)key,下面這篇文章主要給大家介紹了關(guān)于C語言折半查找法的相關(guān)資料,需要的朋友可以參考下2022-06-06
這篇文章主要為大家介紹了C語言多功能動態(tài)通訊錄實現(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-01-01
這篇文章主要為大家詳細(xì)介紹了opencv幀差法找出相差大的圖像，包含訪問mat的像素值，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03