網(wǎng)站首頁 編程語言 正文
前言
前面我們已經(jīng)對(duì)堆進(jìn)行學(xué)習(xí)，堆就是一個(gè)順序結(jié)構(gòu)的二叉樹，把數(shù)組看成二叉樹，下面一起學(xué)習(xí)一下鏈?zhǔn)浇Y(jié)構(gòu)的二叉樹，這里是用遞歸實(shí)現(xiàn)功能
1. 鏈?zhǔn)蕉鏄浣Y(jié)構(gòu)
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
2. 二叉樹的遍歷
首先，我要說明一下遞歸實(shí)現(xiàn)；遞歸實(shí)現(xiàn)一般分為三個(gè)步驟（遞歸三要素）：初步明確函數(shù)功能，限制條件，找到實(shí)現(xiàn)此功能的等式
單項(xiàng)遞歸和二叉樹遞歸（多項(xiàng)遞歸）的區(qū)別？
單項(xiàng)遞歸并沒有分支，多項(xiàng)遞歸是有分支的，這就意味著二叉樹更看中整體，單項(xiàng)遞歸更看重分治。
單項(xiàng)遞歸和二叉樹遞歸的共同點(diǎn)？
都是分治思想，子問題再分子問題再分子問題的思想
2.1 前序遍歷
思想：把樹看成整體：根、左子樹、右子樹，先遍歷根再走左子樹再走右子樹
void BinaryTreePrevOrder(BTNode* root)
{
//根的情況(到底的限制條件)
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);
BinaryTreePrevOrder(root->right);
}
2.2 中序遍歷
思想：把樹看成整體：根、左子樹、右子樹，先遍歷左子樹再走根再走右子樹
void BinaryTreeInOrder(BTNode* root)
{
//根的情況(到底的限制條件)
if (root == NULL)
{
printf("NULL ");
return;
}
BinaryTreeInOrder(root->left);
printf("%c ", root->data);
BinaryTreeInOrder(root->right);
}
2.3 后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
//根的情況(到底的限制條件)
if (root == NULL)
{
printf("NULL ");
return;
}
BinaryTreePostOrder(root->left);
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}
2.4 層序遍歷
思想：出上一層的同時(shí)帶著下一層入隊(duì)列
//鏈?zhǔn)疥?duì)列的結(jié)構(gòu)
typedef struct BinaryTreeNode* QueueDataType;
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QueueNode;
//因?yàn)橐苯拥玫疥?duì)頭的元素和隊(duì)尾的元素
typedef struct QueueLinkList
{
QueueNode* head; //隊(duì)頭
QueueNode* tail; //隊(duì)尾
int size; //元素總數(shù)
}QLL;
//隊(duì)列初始化
void QLLInit(QLL* queue)
{
assert(queue);
queue->head = NULL;
queue->tail = NULL;
queue->size = 0;
}
//進(jìn)隊(duì)
void QLLPush(QLL* queue, QueueDataType x)
{
assert(queue);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("QLLPush:malloc is failed!\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (queue->head == NULL)
{
queue->head = queue->tail = newnode;
}
else
{
queue->tail->next = newnode;
queue->tail = newnode;
}
queue->size++;
}
//出隊(duì)
void QLLPop(QLL* queue)
{
assert(queue != NULL);
assert(QLLEmpty(queue) != true);
//只有一個(gè)結(jié)點(diǎn)時(shí)
if (queue->head->next == NULL)
{
free(queue->head); //free的是這個(gè)結(jié)點(diǎn)的空間，并不是指針
queue->head = queue->tail = NULL;
}
else
{
//通常情況
QueueNode* del = queue->head;
queue->head = queue->head->next;
free(del);
//無需置空
}
queue->size--;
}
//拿取隊(duì)頭數(shù)據(jù)
QueueDataType QLLFront(QLL* queue)
{
assert(queue != NULL);
assert(QLLEmpty(queue) != true);
return queue->head->data;
}
//判空
bool QLLEmpty(QLL* queue)
{
assert(queue);
//return queue->size == 0;
return queue->head == NULL && queue->tail == NULL;
}
//銷毀
void QLLDestroy(QLL* queue)
{
assert(queue);
QueueNode* cur = queue->head;
while (cur != NULL)
{
QueueNode* del = cur;
cur = cur->next;
free(del);
del = NULL;
}
queue->head = queue->tail = NULL;
queue->size = 0;
}
//層序遍歷實(shí)現(xiàn)
void BinaryTreeLevelOrder(BTNode* root)
{
QLL queue;
QLLInit(&queue);
//根先入隊(duì)列
if (root != NULL) {
QLLPush(&queue, root);
}
//隊(duì)列不為NULL的時(shí)候進(jìn)行出隊(duì)頭帶下層數(shù)據(jù)入隊(duì)操作
while (QLLEmpty(&queue) != true)
{
//出隊(duì)頭操作
BTNode* front = QLLFront(&queue);
printf("%c ", front->data);
QLLPop(&queue);
//帶下一層進(jìn)隊(duì)
if (front->left != NULL)
{
QLLPush(&queue, front->left);
}
if (front->right != NULL)
{
QLLPush(&queue, front->right);
}
}
printf("\n");
QLLDestroy(&queue);
}
說明：為什么遞歸不畫圖來解決呢？
多項(xiàng)遞歸畫圖是很難理解的，因?yàn)樗皇俏覀冞壿嬌舷氲模湍们靶虮闅v來說，首先是根，再遍歷左子樹再遍歷右子樹這樣循環(huán)來走，但是在實(shí)際遞歸中邏輯是左子樹走到底，直到NULL時(shí)返回訪問右子樹，如果說是畫圖是理解不了二叉樹遞歸的，這里我們就要扣住樹的結(jié)構(gòu)：根、左子樹、右子樹，這樣是我們邏輯上的實(shí)現(xiàn)，并不是實(shí)際中的過程實(shí)現(xiàn)，這里我需要說明一下，畫圖是為了在原有基礎(chǔ)上來進(jìn)行糾錯(cuò)，這里糾正的錯(cuò)也是和根的限制條件有關(guān)，這里我還會(huì)出幾期二叉樹的相關(guān)練習(xí)，到時(shí)候希望大佬們看看就能理解了二叉樹遞歸！
3. 常見功能
3.1 二叉樹結(jié)點(diǎn)個(gè)數(shù)
遞歸三要素解決問題
- 首先二叉樹想到整體結(jié)構(gòu)：根、左子樹、右子樹
- 函數(shù)功能：求二叉樹結(jié)點(diǎn)的個(gè)數(shù)
- 限制條件：根為NULL的時(shí)候就不是一個(gè)結(jié)點(diǎn)（起初的結(jié)束條件：針對(duì)根來說）
- 等式：計(jì)算左子樹中的結(jié)點(diǎn)個(gè)數(shù)和右子樹的結(jié)點(diǎn)個(gè)數(shù)，最后加上根這個(gè)結(jié)點(diǎn)
int BinaryTreeSize(BTNode* root)
{
if (root == NULL) {
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
代碼分析
上述列出來的思路就是實(shí)現(xiàn)思路，這里注意的是樹的整體結(jié)構(gòu)，我一直扣的就是整體結(jié)構(gòu)，等式中寫的也是整體結(jié)構(gòu)的邏輯；這里來看代碼很簡單就是根和左子樹和右子樹結(jié)構(gòu)
為什么不寫子結(jié)構(gòu)：根、左孩子、右孩子？
原因就是如果寫成子結(jié)構(gòu)的話就不是整體，而是把整體分為多個(gè)相同的結(jié)構(gòu)來討論，這里就不是整體觀念就很容易陷進(jìn)去，為什么二叉樹遞歸難，難就難在你沒扣住整體，而是扣住的是子結(jié)構(gòu)，如果扣住子結(jié)構(gòu)那就很容易陷進(jìn)去，只要陷進(jìn)去了就不是我們自己想的邏輯，而是實(shí)際遞歸的過程邏輯，實(shí)際遞歸的過程邏輯和我們想的邏輯有很大的區(qū)別
為什么首先要有個(gè)前提：樹的結(jié)構(gòu)：根、左子樹、右子樹？
原因很簡單，我們考慮整體就少不了這個(gè)結(jié)構(gòu)，這是我們首先要考慮的問題；另外也是因?yàn)檫@里三要素中的實(shí)現(xiàn)是離不開這個(gè)整體結(jié)構(gòu)的，如果離開了整體結(jié)構(gòu)就又被陷進(jìn)去了
限制條件是怎么來限制的？
首先我們考慮的結(jié)構(gòu)就是樹的整體結(jié)構(gòu)：根、左子樹、右子樹，我們不可能是來對(duì)左右子樹來限制吧，因?yàn)樽笥易訕渲杏泻芏嘟Y(jié)點(diǎn)，從整體上來說是考慮不到的，另外你只要考慮左右子樹中的結(jié)點(diǎn)恭喜你，你又被陷進(jìn)去出不來了哈哈，所以這里的限制條件是針對(duì)根來講的：也就是根的起初的結(jié)束條件以及和題意的聯(lián)系
3.2 二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)
遞歸三要素解決問題
- 前提：樹的結(jié)構(gòu)：根、左子樹、右子樹
- 函數(shù)功能：求二叉樹葉子節(jié)點(diǎn)的個(gè)數(shù)
- 限制條件：root=NULL的時(shí)候就不是葉子結(jié)點(diǎn)，根的左右孩子是空的時(shí)候但根不是空的時(shí)候就是葉子結(jié)點(diǎn)
- 等式：在左右子樹中找葉子節(jié)點(diǎn)，左右子樹中的葉子結(jié)點(diǎn)之和也就是樹的葉子結(jié)點(diǎn)
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
代碼分析
3.3 第K層結(jié)點(diǎn)的個(gè)數(shù)
遞歸三要素解決問題
- 前提：樹的結(jié)構(gòu)：根、左子樹、右子樹
- 函數(shù)功能：求第K層結(jié)點(diǎn)的個(gè)數(shù)
- 限制條件：root=NULL(起初的結(jié)束條件)，根所處的是第一層所以K=1的時(shí)候返回1（題意結(jié)束條件）
- 等式：在左右子樹的第k-1層中的結(jié)點(diǎn)個(gè)數(shù)（因?yàn)榈谝粚邮歉缘贙-1層才是我們要求的第K層）
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1)
+ BinaryTreeLevelKSize(root->right, k - 1);
}
代碼分析
3.4 二叉樹的深度
遞歸三要素解決問題
- 前提：樹的結(jié)構(gòu)：根、左子樹、右子樹
- 函數(shù)功能：求樹的深度
- 限制條件：根為NULL時(shí)結(jié)束
- 等式：樹的根是第一層，那么我們只用計(jì)算出左子樹和右子樹的哪個(gè)深度大就再加上1（根的深度）就是樹的深度
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int LeftTreeDepth = BinaryTreeDepth(root->left);
int RightTreeDepth = BinaryTreeDepth(root->right);
if (LeftTreeDepth > RightTreeDepth) {
return LeftTreeDepth + 1;
}
else {
return RightTreeDepth + 1;
}
}
代碼分析
沒進(jìn)行優(yōu)化的代碼：
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right)) {
return BinaryTreeDepth(root->left) + 1;
}
else {
return BinaryTreeDepth(root->right) + 1;
}
}
這個(gè)代碼也是對(duì)的，但是時(shí)間復(fù)雜就要多了1倍，因?yàn)榕袛嘀杏玫竭f歸了，找到了并沒有記錄深度，也就進(jìn)入判斷中的遞歸，再此遞歸一次，這樣時(shí)間復(fù)雜度就增了1倍。
3.5 判斷是不是樹是不是完全二叉樹
思路：
完全二叉樹的性質(zhì)：前K-1層是滿二叉樹，最后一層是從左到右是連續(xù)的
思路：用層序遍歷來解決，出上一層的同時(shí)帶下一層的數(shù)據(jù)，知道遇到NULL的時(shí)候就要進(jìn)行判斷隊(duì)列中是不是還有不為NULL的值，如果有就不是完全二叉樹，沒有則是
bool BinaryTreeComplete(BTNode* root)
{
QLL queue;
QLLInit(&queue);
if (root != NULL)
{
QLLPush(&queue, root);
}
//拿到每層的
while (QLLEmpty(&queue) != true)
{
BTNode* front = QLLFront(&queue);
QLLPop(&queue);
//當(dāng)這層遇到NULL的時(shí)候進(jìn)行判斷
if (front == NULL)
{
break;
}
else
{
QLLPush(&queue, front->left);
QLLPush(&queue, front->right);
}
}
//出到NULL進(jìn)行檢查
//如果后面有非NULL就不是完全二叉樹
while (QLLEmpty(&queue) != true)
{
BTNode* front = QLLFront(&queue);
QLLPop(&queue);
//不為NULL說明最后一層不是連續(xù)的
if (front != NULL)
{
QLLDestroy(&queue);
return false;
}
}
QLLDestroy(&queue);
return true;
}
3.6 在二叉樹中查找值為x的結(jié)點(diǎn)
遞歸三要素解決問題
前提：樹的結(jié)構(gòu)：根、左子樹、右子樹
函數(shù)功能： 在二叉樹中查找值為x的結(jié)點(diǎn)
限制條件：root=NULL時(shí)結(jié)束，root->val=x時(shí)找到了就結(jié)束
等式：在根里面找，在左子樹和右子樹里面找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1 != NULL)
{
return ret1;
}
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2 != NULL)
{
return ret2;
}
return NULL;
}
代碼分析
錯(cuò)誤列舉
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
return BinaryTreeFind(root->left, x) || BinaryTreeFind(root->right, x);
}
為什么邏輯上是對(duì)的，但是是錯(cuò)的？
最后的return的意思翻譯過來就是在左子樹里面找，找到了就返回，不進(jìn)右子樹，如果左子樹中沒找到就進(jìn)右子樹，找到了返回，如果都沒找到就直接返回NULL；邏輯上是對(duì)的，但是呢，這里我們返回的是指針，指針的的關(guān)系不能用邏輯關(guān)系來表達(dá)，所以是錯(cuò)的
3.7 拿到每一層的數(shù)據(jù)
思路
也是圍繞層序遍歷來寫：記錄每一層的結(jié)點(diǎn)樹來出隊(duì)列就行了，這里也是層序遍歷的知識(shí)是主要的，就不再進(jìn)行討論了
void EveryLayer(BTNode* root)
{
QLL queue;
int levelCount = 0;
QLLInit(&queue);
if (root != NULL) {
QLLPush(&queue, root);
//第一層就是一個(gè)數(shù)據(jù)
levelCount = 1;
}
while (QLLEmpty(&queue) != true)
{
while (levelCount--)
{
BTNode* front = QLLFront(&queue);
printf("%c ", front->data);
QLLPop(&queue);
if (front->left != NULL)
{
QLLPush(&queue, front->left);
}
if (front->right != NULL)
{
QLLPush(&queue, front->right);
}
}
//下一層的個(gè)數(shù)
levelCount = QLLSize(&queue);
printf("\n");
}
QLLDestroy(&queue);
}
結(jié)合上述題就很容易看出實(shí)際上我們寫代碼來劃分的話也是樹的整體結(jié)構(gòu)：根、左子樹、右子樹，時(shí)刻把握著樹的整體結(jié)構(gòu)，這個(gè)結(jié)構(gòu)充分體現(xiàn)在等式中，同時(shí)也影響到了限制條件，限制條件中只用管根的結(jié)束條件以及形成條件，其他的不用管，這就是在代碼中實(shí)現(xiàn)的過程，這里我就不在畫圖，覺得這個(gè)過程不能實(shí)現(xiàn)我說的對(duì)應(yīng)的功能的時(shí)候你就畫圖去嘗試?yán)斫庖幌拢x謝
4. 二叉樹的創(chuàng)建和銷毀
4.1 二叉樹的創(chuàng)建
思路：
這里用到前序遍歷來創(chuàng)建，也就是數(shù)組的元素按個(gè)放進(jìn)根的數(shù)據(jù)域中
限制條件：就是當(dāng)元素為#，代表的是二叉樹中的NULL
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
//形成條件
if (a[(*pi)] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (root == NULL)
{
perror("BinaryTreeCreate: malloc is failed!\n");
exit(-1);
}
//根
root->data = a[(*pi)++];
//左右子樹
root->left = BinaryTreeCreate(a, pi);
root->right = BinaryTreeCreate(a, pi);
return root;
}
void Test2()
{
char str[] = { 'A','B','D','#','#','E','#','H','#','#','C','F','#','#','G','#','#' };
int i = 0;
BTNode* root = BinaryTreeCreate(str, &i);
}
4.2 二叉樹的銷毀
//二級(jí)指針
void BinaryTreeDestory(BTNode** root)
{
if ((*root) == NULL)
{
return;
}
BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));
free((*root));
*root = NULL;
}
void FirstPointBinaryTreeDestory(BTNode* root)
{
if (root == NULL)
{
return;
}
FirstPointBinaryTreeDestory(root->left);
FirstPointBinaryTreeDestory(root->right);
free(root);
//root = NULL;(沒必要）
}//需要說明的是用這個(gè)函數(shù)調(diào)用后要對(duì)root置空
為什么采用后序遍歷來銷毀二叉樹？
因?yàn)楹笮虮闅v最開始走到的就是左子樹的最后一層，然后逐次向上銷毀，并不會(huì)影響每個(gè)結(jié)點(diǎn)的指向；如果采用前序遍歷呢？采用前序遍歷上來就是free掉了根結(jié)點(diǎn)，就找到不到這個(gè)根結(jié)點(diǎn)的左右孩子了
原文鏈接：https://blog.csdn.net/m0_46343224/article/details/128095808
相關(guān)推薦
- 2022-07-11 Android?ListView列表優(yōu)化的方法詳解_Android
- 2023-03-27 Android?BroadcastReceiver傳輸機(jī)制詳解_Android
- 2022-06-12 python實(shí)現(xiàn)微信小程序的多種支付方式_python
- 2023-02-25 C++?move()函數(shù)及priority_queue隊(duì)列使用記錄_C 語言
- 2023-11-11 Python測(cè)網(wǎng)絡(luò)連通性、能否訪問某個(gè)網(wǎng)絡(luò)或者端口號(hào)＜網(wǎng)絡(luò)檢測(cè)、ping主機(jī)、測(cè)試端口＞
- 2022-02-18 RuntimeError: CUDA error: invalid device ordinal
- 2023-04-03 Python數(shù)據(jù)結(jié)構(gòu)隊(duì)列解決約瑟夫斯問題_python
- 2023-04-07 React?styled?components樣式組件化使用流程_React
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速