C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)遞歸的方法

本篇內(nèi)容介紹了“C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)遞歸的方法”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

一、二叉樹(shù)的遍歷算法

二叉樹(shù)的精髓在于遍歷。遍歷掌握了后，剩下的問(wèn)題迎刃而解。

1.構(gòu)造二叉樹(shù)

“工欲善其事必利其器”

1.所以先創(chuàng)建一個(gè)結(jié)構(gòu)體。

2.手動(dòng)先構(gòu)造一顆如圖所示的二叉樹(shù)。

typedef int BTDataType;//定義二叉樹(shù)結(jié)構(gòu)體typedef struct BinaryTreeNode{<!--{C}%3C!%2D%2D%20%2D%2D%3E-->int data;//節(jié)點(diǎn)數(shù)據(jù)struct BinartTreeNode* left;//左子樹(shù)struct BinartTreeNode* right;//右子樹(shù)}BTNode;//構(gòu)造一棵二叉樹(shù)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;
//定義二叉樹(shù)結(jié)構(gòu)體
typedef struct BinaryTreeNode
{
	int data;//節(jié)點(diǎn)數(shù)據(jù)
	struct BinartTreeNode* left;//左子樹(shù)
	struct BinartTreeNode* right;//右子樹(shù)
}BTNode;
//構(gòu)造一棵二叉樹(shù)
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).)

遍歷順序：根 左子樹(shù) 右子樹(shù)

思路：

1.把每個(gè)節(jié)點(diǎn)都想成是一棵樹(shù)。

2.當(dāng)樹(shù)為空時(shí)。

3.當(dāng)樹(shù)不為空時(shí)，先遍歷左子樹(shù)，后遍歷右子樹(shù)

注意：前中后序遍歷不同處只在printf打印的順序的位置。

// 二叉樹(shù)前序遍歷
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

遞歸分析圖：

遞歸題目的萬(wàn)能的解法。就是畫(huà)遞歸圖。

二叉樹(shù)的所有題目，假如你不會(huì)，趕快 畫(huà)遞歸圖 吧

由于遞歸太龐大，圖片太小看不清，所以我把左子樹(shù)和右子樹(shù)分開(kāi)又截了圖

1.紅線部分代表壓棧遞歸。

2.綠線部分代表 返回

左子樹(shù)

右子樹(shù)

3.中序遍歷

遍歷順序：左子樹(shù) 根 右子樹(shù)

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.后序遍歷

遍歷順序：左子樹(shù) 右子樹(shù) 根

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)出來(lái)的時(shí)候，左右孩子進(jìn)去。

// 層序遍歷
void LevelOrder(BTNode* root)
{
	//初始化隊(duì)列，注意隊(duì)列里面存的是 指針類(lèi)型。
	Queue q;
	QueueInit(&q);
	//如果樹(shù)不為空開(kāi)始入隊(duì)
	if (root)
	{
		QueuePush(&q, root);
	}
	//樹(shù)不為空開(kāi)始出對(duì)頭數(shù)據(jù)，同時(shí)入隊(duì)左子樹(shù)和右子樹(shù)，直到隊(duì)列為空。
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		//如果還有左右子樹(shù)，繼續(xù)入隊(duì)，否則不入隊(duì)
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	//記得銷(xiāo)毀隊(duì)列
	printf("\n");
	QueueDestory(&q);
}

二、二叉樹(shù)遍歷算法的應(yīng)用

1.求節(jié)點(diǎn)個(gè)數(shù)

思想：把大問(wèn)題逐步分割為子問(wèn)題。

思路：

1.樹(shù)為空時(shí)返回0個(gè)節(jié)點(diǎn)。(樹(shù)為空不意味著才開(kāi)始就是空樹(shù)，而是遞歸到最后一個(gè)為NULL的樹(shù)返回)

2.樹(shù)不為空時(shí)返回自己的1個(gè)節(jié)點(diǎn)+上一顆樹(shù)返回的節(jié)點(diǎn)的個(gè)數(shù)。

// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root)
{
	//當(dāng)樹(shù)為空時(shí)
	if (root == NULL)
		return 0;
	//當(dāng)樹(shù)不為空時(shí)
	return BinaryTreeSize(root->left) +
		BinaryTreeSize(root->right) + 1;
}

2.求葉子節(jié)點(diǎn)個(gè)數(shù)

思路：

1.樹(shù)為NULL時(shí)，返回0.

2.兩顆子樹(shù)都不為NULL時(shí)，返回1.

3.不滿足以上兩種情況，繼續(xù)遞歸左右子樹(shù)。

// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
	//當(dāng)樹(shù)為空時(shí)
	if (root == NULL)
		return 0;
	//當(dāng)兩棵 子 樹(shù)都為空時(shí)
	if (root->left == NULL && root->right == NULL)
		return 1;
	/*程序都到這一行, 意味著樹(shù)不滿足返回的情況，
	所以繼續(xù)遞歸 左子樹(shù)和 右子樹(shù)。*/
	return BinaryTreeLeafSize(root->left)+
		BinaryTreeLeafSize(root->right);
}

3.求第k層節(jié)點(diǎn)個(gè)數(shù)

思想：求上圖第3層節(jié)點(diǎn)個(gè)數(shù)。

1.站在第1層來(lái)看，就是求第3層節(jié)點(diǎn)的個(gè)數(shù)

2.站在第2層的角度來(lái)看，就是求第2層節(jié)點(diǎn)的個(gè)數(shù)

3.站在第3層的角度來(lái)看，就是求第1層節(jié)點(diǎn)的個(gè)數(shù)

思路：

1.當(dāng)樹(shù)為空時(shí)返回0

2.當(dāng)k為1時(shí)返回1。

3.不滿足1和2，繼續(xù)遞歸左右子樹(shù)。

// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//當(dāng)樹(shù)為空時(shí)
	if (root == NULL)
		return 0;
	//當(dāng)k為1時(shí)
	if (k == 1)
		return 1;
	//程序能走到這一行，說(shuō)明樹(shù)不為空，k也不為1.繼續(xù)遞歸
	return BinaryTreeLevelKSize(root->left, k-1)+
	BinaryTreeLevelKSize(root->right, k - 1);
}

4.查找值為x的節(jié)點(diǎn)

思想：

1.把最小規(guī)模的問(wèn)題寫(xiě)在最前面作為限制

2.不滿足最小規(guī)模的問(wèn)題，則繼續(xù)遞歸。將問(wèn)題一步一步拆分為不可分割的子問(wèn)題。

// 二叉樹(shù)查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	//當(dāng)樹(shù)為空時(shí)
	if (root == NULL)
		return NULL;
	//當(dāng)樹(shù)的值等于x時(shí)
	if (root->data == x)
		return root;
	/*走到這一行，說(shuō)明不滿足以上條件。
	開(kāi)始遞歸左右子樹(shù)，如果找到了，直接一步一步往回返*/
	BTNode* a = BinaryTreeFind(root->left, x);
	if (a)
	{
		return a;
	}
	BTNode* b = BinaryTreeFind(root->right, x);
	if (b)
	{
		return b;
	}
	//沒(méi)有x，則返回空
	return NULL;
}

5.二叉樹(shù)銷(xiāo)毀

思路：相當(dāng)于二叉樹(shù)的后序遍歷。

先把左右子樹(shù)遍歷完后，開(kāi)始遍歷根，對(duì)根進(jìn)行free。

// 二叉樹(shù)銷(xiāo)毀
void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	//free掉根
	free(root);
}

6.前序遍歷構(gòu)建二叉樹(shù)

思路：

對(duì)一串字符進(jìn)行先序遍歷，遞歸遍歷二叉樹(shù)，當(dāng)遇見(jiàn)#時(shí)開(kāi)始返回 連接 樹(shù)。

通過(guò)前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹(shù)

#include <stdio.h>
#include <stdlib.h>
typedef struct BTNodeTree
{
    struct BTNodeTree* left;
    struct BTNodeTree* right;
    char val;
}BTNode;
//創(chuàng)建二叉樹(shù)
BTNode* CreateTree(char* a, int* pi)
{
	//如果樹(shù)為#則返回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)建左右子樹(shù)
    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.判斷二叉樹(shù)是否是完全二叉樹(shù)

思路：

1.層序遍歷，空節(jié)點(diǎn)也進(jìn)隊(duì)列

2.出到空節(jié)點(diǎn)以后，出隊(duì)列中所有數(shù)據(jù)，如果全是空，則是完全二叉樹(shù)

8.求二叉樹(shù)的深度

思路：二叉樹(shù)的最大深度等價(jià)于：左右子樹(shù)的最大深度 + 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;
}

//判斷二叉樹(shù)是否是完全二叉樹(shù)
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);
		//空后面出到非空，那說(shuō)明不是完全二叉樹(shù)
		if (front)
			return false;
	}
	//否則是完全二叉樹(shù)
	return true;
}

三、二叉樹(shù)LeetCode題目

以下題目均屬于LeetCode的 簡(jiǎn)單 題目

1.單值二叉樹(shù)

如果二叉樹(shù)每個(gè)節(jié)點(diǎn)都具有相同的值，那么該二叉樹(shù)就是單值二叉樹(shù)。

只有給定的樹(shù)是單值二叉樹(shù)時(shí)，才返回 true；否則返回 false。

思想：

1.看一棵樹(shù)的三個(gè)部分是否相同，相同則繼續(xù)遞歸下一顆樹(shù)，直到樹(shù)為空。

bool isUnivalTree(struct TreeNode* root)
{
    //當(dāng)樹(shù)為空時(shí)。
    if(root == NULL)
    {
        return true;
    }
    //當(dāng)右樹(shù)不為空，并且 根 != 左樹(shù)
    //當(dāng)右樹(shù)不為空，并且 根 != 右樹(shù)時(shí)
    if(root->left != NULL && root->val != root->left->val)
    return false;
    if(root->right != NULL && root->val != root->right->val)
    return false;
    //能走到這一行，說(shuō)明第一層樹(shù)的值相同了。接著遞歸左右子樹(shù)。
    return isUnivalTree(root->left) && 
            isUnivalTree(root->right);
}

2. 檢查兩顆樹(shù)是否相同

給你兩棵二叉樹(shù)的根節(jié)點(diǎn) p 和 q ，編寫(xiě)一個(gè)函數(shù)來(lái)檢驗(yàn)這兩棵樹(shù)是否相同。

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    //當(dāng)兩樹(shù)都為空時(shí)
    if(p == NULL && q== NULL)
        return true;
    //當(dāng)其中一個(gè)樹(shù)為空時(shí)
    if(p == NULL || q == NULL)
        return false;
    //走到這里說(shuō)明兩樹(shù)存在，比較兩樹(shù)的值
    if(p->val != q->val)
        return false;
    //走到這里說(shuō)明兩樹(shù)的根節(jié)點(diǎn)相同，繼續(xù)遞歸，直到判斷完左右子樹(shù)為止。
    return isSameTree(p->left, q->left) 
    && isSameTree(p->right, q->right);
}

3. 對(duì)稱(chēng)二叉樹(shù)

給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn) root ， 檢查它是否軸對(duì)稱(chēng)。

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ù)為空時(shí)
    if(q == NULL ||p ==NULL)
         return false;
    //程序走到一這行，說(shuō)明左右節(jié)點(diǎn)存在。當(dāng)兩個(gè)根節(jié)點(diǎn)不相等時(shí)
    if(q->val != p->val)
    return false;
    //走到這一步說(shuō)明左右節(jié)點(diǎn)相同，開(kāi)始遞歸左右子樹(shù)
    return isSym(q->left, p->right) && isSym(q->right, p->left); 
}
bool isSymmetric(struct TreeNode* root)
{
    //當(dāng)是空樹(shù)時(shí)
    if(root == NULL)
        return true;
    return isSym(root->left, root->right);
}

4.另一顆樹(shù)的子樹(shù)

思路：

用到了上一題判斷兩棵樹(shù)是否相同的思想。

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    //當(dāng)兩樹(shù)都為空時(shí)
    if(p == NULL && q== NULL)
        return true;
    //當(dāng)其中一個(gè)樹(shù)為空時(shí)
    if(p == NULL || q == NULL)
        return false;
    //走到這里說(shuō)明兩樹(shù)存在，比較兩樹(shù)的值
    if(p->val != q->val)
        return false;
    //走到這里說(shuō)明兩樹(shù)的根節(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í)，并不是說(shuō)明沒(méi)有節(jié)點(diǎn)，可能是所有的子樹(shù)都遍歷過(guò)了。然后不相等返回false
    if(root == NULL)
    return false;
//走到這里說(shuō)明子樹(shù)不為空，開(kāi)始比較子樹(shù)和sub相同不。
    bool a = isSameTree(root, subRoot);
    if(a)
    return a;
    //走到這里說(shuō)明不相同，繼續(xù)遞歸左子樹(shù)和右子樹(shù)，其中一個(gè)相同就返回true。
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

5.二叉樹(shù)的前序遍歷

題目思路

1.求節(jié)點(diǎn)個(gè)數(shù)，開(kāi)辟數(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ì)算樹(shù)有幾個(gè)節(jié)點(diǎn),然后開(kāi)辟相應(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)二叉樹(shù)

給你一棵二叉樹(shù)的根節(jié)點(diǎn) root ，翻轉(zhuǎn)這棵二叉樹(shù)，并返回其根節(jié)點(diǎn)。

我犯的BUG：只是對(duì)二叉樹(shù)里面的值進(jìn)行交換，但是無(wú)法避免空指針。一直都是空指針的錯(cuò)誤，因?yàn)閞oot總會(huì)為空，root->data總會(huì)遇見(jiàn)空指針

所以以后盡量要多想著交換地址。

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ǔ)言數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)遞歸的方法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！