C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹遞歸
" 梧桐更兼細(xì)雨，到黃昏、點(diǎn)點(diǎn)滴滴。"
C語言朱武大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)專欄
C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)快速排序圖文示例
C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)希爾排序算法
C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例
前言
本篇用C語言遞歸來實(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語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹遞歸的詳細(xì)內(nèi)容，更多關(guān)于C語言二叉樹遞歸的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++開發(fā)在IOS環(huán)境下運(yùn)行的LRUCache緩存功能
本文著重介紹如何在XCODE中，通過C++開發(fā)在IOS環(huán)境下運(yùn)行的緩存功能。算法基于LRU,最近最少使用,需要的朋友可以參考下2012-11-11
這篇文章主要介紹了C++調(diào)用Go方法的字符串傳遞問題及解決方案，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
詳解c++11以正確的姿勢(shì)輸出enum class的值
這篇文章主要介紹了詳解c++11以正確的姿勢(shì)輸出enum class的值，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
C語言實(shí)現(xiàn)最簡(jiǎn)單的剪刀石頭布小游戲示例
這篇文章主要介紹了C語言實(shí)現(xiàn)最簡(jiǎn)單的剪刀石頭布小游戲,涉及C語言數(shù)組、隨機(jī)數(shù)與數(shù)值運(yùn)算等相關(guān)操作技巧,需要的朋友可以參考下2017-09-09
C語言數(shù)據(jù)結(jié)構(gòu)之線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表（linear list）是數(shù)據(jù)結(jié)構(gòu)的一種，一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列，這篇文章帶你學(xué)習(xí)下線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2021-11-11
這篇文章主要為大家詳細(xì)介紹了基于easyx的C++實(shí)現(xiàn)貪吃蛇，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
這篇文章主要介紹了C/C++中獲取數(shù)組長(zhǎng)度的方法,很實(shí)用的一種方法,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了詳解C++中的自動(dòng)存儲(chǔ)，幫助大家更好的理解和學(xué)習(xí)C++,感興趣的朋友可以了解下2020-09-09
本篇文章小編為大家介紹，基于條件變量的消息隊(duì)列 說明介紹。需要的朋友參考一下2013-04-04
C++ 基數(shù)排序的實(shí)現(xiàn)實(shí)例代碼
這篇文章主要介紹了C++ 基數(shù)排序的實(shí)現(xiàn)實(shí)例代碼的相關(guān)資料,這里附有實(shí)例代碼，幫助大家學(xué)習(xí)理解，需要的朋友可以參考下2016-11-11