C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹遞歸
" 梧桐更兼細(xì)雨，到黃昏、點(diǎn)點(diǎn)滴滴。"
C語(yǔ)言朱武大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)專欄
C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)快速排序圖文示例
C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)希爾排序算法
C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例
前言
本篇用C語(yǔ)言遞歸來實(shí)現(xiàn)二叉樹的基本操作。主要用到分治思想
1.本篇文章和代碼旨在用于鏈?zhǔn)蕉鏄浠静僮鞯膹?fù)習(xí)。主要是遞歸的應(yīng)用。
2.深刻理解二叉樹是遞歸定義的這一概念。
分治遞歸思想：
1.把大問題分割為不可再分割的子問題。。
2.然后一步一步的返回
一、二叉樹的遍歷算法
二叉樹的精髓在于遍歷。遍歷掌握了后，剩下的問題迎刃而解。
1.構(gòu)造二叉樹
“工欲善其事必利其器”
1.所以先創(chuàng)建一個(gè)結(jié)構(gòu)體。
2.手動(dòng)先構(gòu)造一顆如圖所示的二叉樹。
typedef int BTDataType;//定義二叉樹結(jié)構(gòu)體typedef struct BinaryTreeNode{<!--{C}%3C!%2D%2D%20%2D%2D%3E-->int data;//節(jié)點(diǎn)數(shù)據(jù)struct BinartTreeNode* left;//左子樹struct BinartTreeNode* right;//右子樹}BTNode;//構(gòu)造一棵二叉樹BTNode* BuyBTNode(BTDataType x){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->printf("malloc fail\n");exit(-1);}node->data = x;node->left = NULL;node->right = NULL;return node;}BTNode* CreatBinaryTree(){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->BTNode* node1 = BuyBTNode(1);BTNode* node2 = BuyBTNode(2);BTNode* node3 = BuyBTNode(3);BTNode* node4 = BuyBTNode(4);BTNode* node5 = BuyBTNode(5);BTNode* node6 = BuyBTNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;}int main(){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->BTNode* tree = CreatBinaryTree();return 0;}typedef int BTDataType;
//定義二叉樹結(jié)構(gòu)體
typedef struct BinaryTreeNode
{
int data;//節(jié)點(diǎn)數(shù)據(jù)
struct BinartTreeNode* left;//左子樹
struct BinartTreeNode* right;//右子樹
}BTNode;
//構(gòu)造一棵二叉樹
BTNode* BuyBTNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
printf("malloc fail\n");
exit(-1);
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyBTNode(1);
BTNode* node2 = BuyBTNode(2);
BTNode* node3 = BuyBTNode(3);
BTNode* node4 = BuyBTNode(4);
BTNode* node5 = BuyBTNode(5);
BTNode* node6 = BuyBTNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}
int main()
{
BTNode* tree = CreatBinaryTree();
return 0;
}
2.前序遍歷(遞歸圖是重點(diǎn).)
遍歷順序：根 左子樹 右子樹
思路：
1.把每個(gè)節(jié)點(diǎn)都想成是一棵樹。
2.當(dāng)樹為空時(shí)。
3.當(dāng)樹不為空時(shí)，先遍歷左子樹，后遍歷右子樹
注意：前中后序遍歷不同處只在printf打印的順序的位置。
// 二叉樹前序遍歷
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
//打印在前
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
打印結(jié)果：
1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
遞歸分析圖：
遞歸題目的萬能的解法。就是畫遞歸圖。
二叉樹的所有題目，假如你不會(huì)，趕快 畫遞歸圖 吧
由于遞歸太龐大，圖片太小看不清，所以我把左子樹和右子樹分開又截了圖
1.紅線部分代表壓棧遞歸。
2.綠線部分代表 返回
左子樹
右子樹
3.中序遍歷
遍歷順序：左子樹 根 右子樹
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
//打印在中間
printf("%d ", root->data);
InOrder(root->right);
}
打印結(jié)果
NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
4.后序遍歷
遍歷順序：左子樹 右子樹 根
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
//打印在最后
printf("%d ", root->data);
}
打印結(jié)果
NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1
5.層序遍歷
思路：
借助先進(jìn)先出的性質(zhì)，上一層節(jié)點(diǎn)出的時(shí)候，帶下一層的節(jié)點(diǎn)進(jìn)去。
1.先把根入隊(duì)列。
2.根節(jié)點(diǎn)出來的時(shí)候，左右孩子進(jìn)去。
// 層序遍歷
void LevelOrder(BTNode* root)
{
//初始化隊(duì)列，注意隊(duì)列里面存的是 指針類型。
Queue q;
QueueInit(&q);
//如果樹不為空開始入隊(duì)
if (root)
{
QueuePush(&q, root);
}
//樹不為空開始出對(duì)頭數(shù)據(jù)，同時(shí)入隊(duì)左子樹和右子樹，直到隊(duì)列為空。
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
//如果還有左右子樹，繼續(xù)入隊(duì)，否則不入隊(duì)
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
//記得銷毀隊(duì)列
printf("\n");
QueueDestory(&q);
}
二、二叉樹遍歷算法的應(yīng)用
1.求節(jié)點(diǎn)個(gè)數(shù)
思想：把大問題逐步分割為子問題。
思路：
1.樹為空時(shí)返回0個(gè)節(jié)點(diǎn)。(樹為空不意味著才開始就是空樹，而是遞歸到最后一個(gè)為NULL的樹返回)
2.樹不為空時(shí)返回自己的1個(gè)節(jié)點(diǎn)+上一顆樹返回的節(jié)點(diǎn)的個(gè)數(shù)。
// 二叉樹節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root)
{
//當(dāng)樹為空時(shí)
if (root == NULL)
return 0;
//當(dāng)樹不為空時(shí)
return BinaryTreeSize(root->left) +
BinaryTreeSize(root->right) + 1;
}
2.求葉子節(jié)點(diǎn)個(gè)數(shù)
思路：
1.樹為NULL時(shí)，返回0.
2.兩顆子樹都不為NULL時(shí)，返回1.
3.不滿足以上兩種情況，繼續(xù)遞歸左右子樹。
// 二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
//當(dāng)樹為空時(shí)
if (root == NULL)
return 0;
//當(dāng)兩棵 子 樹都為空時(shí)
if (root->left == NULL && root->right == NULL)
return 1;
/*程序都到這一行, 意味著樹不滿足返回的情況，
所以繼續(xù)遞歸 左子樹和 右子樹。*/
return BinaryTreeLeafSize(root->left)+
BinaryTreeLeafSize(root->right);
}
3.求第k層節(jié)點(diǎn)個(gè)數(shù)
思想：求上圖第3層節(jié)點(diǎn)個(gè)數(shù)。
1.站在第1層來看，就是求第3層節(jié)點(diǎn)的個(gè)數(shù)
2.站在第2層的角度來看，就是求第2層節(jié)點(diǎn)的個(gè)數(shù)
3.站在第3層的角度來看，就是求第1層節(jié)點(diǎn)的個(gè)數(shù)
思路：
1.當(dāng)樹為空時(shí)返回0
2.當(dāng)k為1時(shí)返回1。
3.不滿足1和2，繼續(xù)遞歸左右子樹。
// 二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
//當(dāng)樹為空時(shí)
if (root == NULL)
return 0;
//當(dāng)k為1時(shí)
if (k == 1)
return 1;
//程序能走到這一行，說明樹不為空，k也不為1.繼續(xù)遞歸
return BinaryTreeLevelKSize(root->left, k-1)+
BinaryTreeLevelKSize(root->right, k - 1);
}
4.查找值為x的節(jié)點(diǎn)
思想：
1.把最小規(guī)模的問題寫在最前面作為限制
2.不滿足最小規(guī)模的問題，則繼續(xù)遞歸。將問題一步一步拆分為不可分割的子問題。
// 二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
//當(dāng)樹為空時(shí)
if (root == NULL)
return NULL;
//當(dāng)樹的值等于x時(shí)
if (root->data == x)
return root;
/*走到這一行，說明不滿足以上條件。
開始遞歸左右子樹，如果找到了，直接一步一步往回返*/
BTNode* a = BinaryTreeFind(root->left, x);
if (a)
{
return a;
}
BTNode* b = BinaryTreeFind(root->right, x);
if (b)
{
return b;
}
//沒有x，則返回空
return NULL;
}
5.二叉樹銷毀
思路：相當(dāng)于二叉樹的后序遍歷。
先把左右子樹遍歷完后，開始遍歷根，對(duì)根進(jìn)行free。
// 二叉樹銷毀
void BinaryTreeDestory(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
//free掉根
free(root);
}
6.前序遍歷構(gòu)建二叉樹
思路：
對(duì)一串字符進(jìn)行先序遍歷，遞歸遍歷二叉樹，當(dāng)遇見#時(shí)開始返回 連接 樹。
通過前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹
#include <stdio.h>
#include <stdlib.h>
typedef struct BTNodeTree
{
struct BTNodeTree* left;
struct BTNodeTree* right;
char val;
}BTNode;
//創(chuàng)建二叉樹
BTNode* CreateTree(char* a, int* pi)
{
//如果樹為#則返回null
if(a[*pi] == '#')
{
(*pi)++;
return NULL;
}
//否則構(gòu)建節(jié)點(diǎn)，同時(shí)讓pi++,以便繼續(xù)遞歸
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->val = a[(*pi)++];
//構(gòu)建左右子樹
root->left = CreateTree(a, pi);
root->right = CreateTree(a, pi);
//構(gòu)建完后返回根節(jié)點(diǎn)。
return root;
}
//中序遍歷打印。
void inorder(BTNode* root)
{
if(root == NULL)
return;
inorder(root->left);
printf("%c ", root->val);
inorder(root->right);
}
int main()
{
char a[100];
scanf("%s", a);
int i = 0;
BTNode* tree = CreateTree(a, &i);
inorder(tree);
return 0;
}
7.判斷二叉樹是否是完全二叉樹
思路：
1.層序遍歷，空節(jié)點(diǎn)也進(jìn)隊(duì)列
2.出到空節(jié)點(diǎn)以后，出隊(duì)列中所有數(shù)據(jù)，如果全是空，則是完全二叉樹
8.求二叉樹的深度
思路：二叉樹的最大深度等價(jià)于：左右子樹的最大深度 + 1
int maxDepth(struct TreeNode* root)
{
if(root == NULL)
{
return 0;
}
size_t left = maxDepth(root->left) + 1;
size_t right = maxDepth(root->right) + 1;
if(right > left)
{
return right;
}
return left;
}
//判斷二叉樹是否是完全二叉樹
bool BTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
break;
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//空后面出到非空，那說明不是完全二叉樹
if (front)
return false;
}
//否則是完全二叉樹
return true;
}
三、二叉樹LeetCode題目
以下題目均屬于LeetCode的 簡(jiǎn)單 題目
1.單值二叉樹
如果二叉樹每個(gè)節(jié)點(diǎn)都具有相同的值，那么該二叉樹就是單值二叉樹。
只有給定的樹是單值二叉樹時(shí)，才返回 true；否則返回 false。
思想：
1.看一棵樹的三個(gè)部分是否相同，相同則繼續(xù)遞歸下一顆樹，直到樹為空。
bool isUnivalTree(struct TreeNode* root)
{
//當(dāng)樹為空時(shí)。
if(root == NULL)
{
return true;
}
//當(dāng)右樹不為空，并且 根 != 左樹
//當(dāng)右樹不為空，并且 根 != 右樹時(shí)
if(root->left != NULL && root->val != root->left->val)
return false;
if(root->right != NULL && root->val != root->right->val)
return false;
//能走到這一行，說明第一層樹的值相同了。接著遞歸左右子樹。
return isUnivalTree(root->left) &&
isUnivalTree(root->right);
}
2. 檢查兩顆樹是否相同
給你兩棵二叉樹的根節(jié)點(diǎn) p 和 q ，編寫一個(gè)函數(shù)來檢驗(yàn)這兩棵樹是否相同。
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
//當(dāng)兩樹都為空時(shí)
if(p == NULL && q== NULL)
return true;
//當(dāng)其中一個(gè)樹為空時(shí)
if(p == NULL || q == NULL)
return false;
//走到這里說明兩樹存在，比較兩樹的值
if(p->val != q->val)
return false;
//走到這里說明兩樹的根節(jié)點(diǎn)相同，繼續(xù)遞歸，直到判斷完左右子樹為止。
return isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
3. 對(duì)稱二叉樹
給你一個(gè)二叉樹的根節(jié)點(diǎn) root ， 檢查它是否軸對(duì)稱。
bool isSym(struct TreeNode* q, struct TreeNode* p)
{
//當(dāng)只有一個(gè)根節(jié)點(diǎn)時(shí)
if(q == NULL && p == NULL)
return true;
//當(dāng)其中一個(gè)子樹為空時(shí)
if(q == NULL ||p ==NULL)
return false;
//程序走到一這行，說明左右節(jié)點(diǎn)存在。當(dāng)兩個(gè)根節(jié)點(diǎn)不相等時(shí)
if(q->val != p->val)
return false;
//走到這一步說明左右節(jié)點(diǎn)相同，開始遞歸左右子樹
return isSym(q->left, p->right) && isSym(q->right, p->left);
}
bool isSymmetric(struct TreeNode* root)
{
//當(dāng)是空樹時(shí)
if(root == NULL)
return true;
return isSym(root->left, root->right);
}
4.另一顆樹的子樹
思路：
用到了上一題判斷兩棵樹是否相同的思想。
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
//當(dāng)兩樹都為空時(shí)
if(p == NULL && q== NULL)
return true;
//當(dāng)其中一個(gè)樹為空時(shí)
if(p == NULL || q == NULL)
return false;
//走到這里說明兩樹存在，比較兩樹的值
if(p->val != q->val)
return false;
//走到這里說明兩樹的根節(jié)點(diǎn)相同，繼續(xù)遞歸
return isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
//遞歸結(jié)束條件。當(dāng)根為空時(shí)，并不是說明沒有節(jié)點(diǎn)，可能是所有的子樹都遍歷過了。然后不相等返回false
if(root == NULL)
return false;
//走到這里說明子樹不為空，開始比較子樹和sub相同不。
bool a = isSameTree(root, subRoot);
if(a)
return a;
//走到這里說明不相同，繼續(xù)遞歸左子樹和右子樹，其中一個(gè)相同就返回true。
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
5.二叉樹的前序遍歷
題目思路
1.求節(jié)點(diǎn)個(gè)數(shù)，開辟數(shù)組大小。
2.前序遍歷存放到數(shù)組中
int treeSize(struct TreeNode* root)
{
if(root == NULL)
return 0;
return treeSize(root->left) + treeSize(root->right)+1;
}
void preorder(int* a, struct TreeNode* root, int* i)
{
if(root == NULL)
{
return;
}
a[(*i)++] = root->val;
preorder(a,root->left, i);
preorder(a,root->right, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
//計(jì)算樹有幾個(gè)節(jié)點(diǎn),然后開辟相應(yīng)的空間
int size = treeSize(root);
int* a = (int*)malloc(sizeof(int)* size);
int i = 0;//設(shè)置下標(biāo)i
*returnSize = size;//需要返回的數(shù)組大小
//前序遍歷依次存放到數(shù)組中。
preorder(a, root, &i);
return a;
}
6.反轉(zhuǎn)二叉樹
給你一棵二叉樹的根節(jié)點(diǎn) root ，翻轉(zhuǎn)這棵二叉樹，并返回其根節(jié)點(diǎn)。
我犯的BUG：只是對(duì)二叉樹里面的值進(jìn)行交換，但是無法避免空指針。一直都是空指針的錯(cuò)誤，因?yàn)閞oot總會(huì)為空，root->data總會(huì)遇見空指針
所以以后盡量要多想著交換地址。
void _invertTree(struct TreeNode* root)
{
if(root)
{
struct TreeNode* tmp = root->left;
root->left = root->right;
root->right = tmp;
_invertTree(root->left);
_invertTree(root->right);
}
}
struct TreeNode* invertTree(struct TreeNode* root)
{
_invertTree(root);
return root;
}
以上就是C語(yǔ)言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹遞歸的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言二叉樹遞歸的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++新特性詳細(xì)分析基于范圍的for循環(huán)
C++11這次的更新帶來了令很多C++程序員期待已久的for?range循環(huán)，每次看到j(luò)avascript，?lua里的for?range，心想要是C++能有多好，心里別提多酸了。這次C++11不負(fù)眾望，再也不用羨慕別家人的for?range了。下面看下C++11的for循環(huán)的新用法2022-04-04
c語(yǔ)言大小端(數(shù)據(jù)在內(nèi)存中的存儲(chǔ))
大小端是內(nèi)存存儲(chǔ)字節(jié)的兩種方式,一個(gè)是大端存儲(chǔ),一個(gè)是小端存儲(chǔ),本文主要介紹了c語(yǔ)言大小端,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09
C語(yǔ)言左旋轉(zhuǎn)字符串與翻轉(zhuǎn)字符串中單詞順序的方法
這篇文章主要介紹了C語(yǔ)言左旋轉(zhuǎn)字符串與翻轉(zhuǎn)字符串中單詞順序的方法,給出了相關(guān)的兩道算法題目作為例子,需要的朋友可以參考下2016-02-02
如果沒有計(jì)算器，我們?nèi)绾吻?的平方根2013-05-05
本文主要介紹了Qt6安裝教程(使用國(guó)內(nèi)源)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
大家好，本篇文章主要講的是C語(yǔ)言循環(huán)控制入門介紹，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
C++日期類(Date)實(shí)現(xiàn)的示例代碼
這篇文章主要為大家詳細(xì)介紹了如何利用C++語(yǔ)言實(shí)現(xiàn)日期類(Date)，可以實(shí)現(xiàn)確定某年某月有多少天、打印日期等功能，感興趣的可以了解一下2022-07-07
C++中的構(gòu)造函數(shù)與析造函數(shù)詳解
這篇文章主要介紹了C++中的構(gòu)造函數(shù)與析造函數(shù)詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06
這篇文章主要為大家介紹了C語(yǔ)言直接插入排序算法的方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
這篇文章主要給大家介紹了關(guān)于C/C++混合編程之extern “C”使用的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-09-09