目錄

前言

分治算法

模擬二叉樹代碼

結點個數計算

錯誤方法

不便利方法

基于分治思想的方法

葉子結點個數

樹的高度

第k層結點的個數

---

前言

????????在鏈式二叉樹的前序、中序、后續遍歷中我們模擬了一棵二叉樹，并實現了它的前、中、后序遍歷，現在我們來解決設計與二叉樹相關的計算問題。

分治算法

概念：是一種將問題劃分為更小的子問題，并通過解決子問題來解決原始問題的算法設計策略

分治算法的基本思想：

1. 分解：將原始問題劃分成若干個規模較小且相互獨立的子問題。這里關鍵是要找到一個適當的方式將原始問題切割成更小規模的子問題，使得每個子問題都與原始問題具有相同或類似結構。

2. 解決：遞歸地求解各個子問題。對于規模較小而直接可求解的情況，直接給出答案；對于規模較大而無法直接求解時，則繼續應用該算法來進一步劃分為更小的子問題并進行求解。

3. 合并：將各個子結果合并成最終結果。在所有子任務都被獨立地處理和求得結果之后，需要把這些局部結果合并起來以獲得整體上正確且有效率的最終輸出。

可以應用分治算法來解決的問題的特點：

1、原問題可以分解為多個子問題

子問題與原問題相比，只是問題的規模有所降低，其結構和求解方法與原問題相同或相似

2、原問題在分解過程中，遞歸地求解子問題

由于遞歸都必須有一個終止條件，故當分解后的子問題規模足夠小時，應能夠直接求解

3、在求解并得到各個子問題的解后

應能夠采用某種方式、方法合并或構造出原問題的解

結論：不難發現，在分治策略中，由于子問題與原問題在結構和解法上的相似性，用分治方法解決的問題，大都采用了遞歸的形式🥰

模擬二叉樹代碼

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}TreeNode;TreeNode* BuyTreeNode(int x)
{TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));assert(node);node->data = x;node->left = NULL;node->right = NULL;return node;
}TreeNode* CreatTree()
{TreeNode* node1 = BuyTreeNode(1);TreeNode* node2 = BuyTreeNode(2);TreeNode* node3 = BuyTreeNode(3);TreeNode* node4 = BuyTreeNode(4);TreeNode* node5 = BuyTreeNode(5);TreeNode* node6 = BuyTreeNode(6);node1->left = node2;node1->right = node4;node2->left = node3;//node2->right = NULL;//node3->left = NULL;//node3->right = NULL;node4->left = node5;node4->right = node6;//node5->left = NULL;//node5->right = NULL;//node6->left = NULL;//node6->right= NULL;return node1;
}int main()
{TreeNode* root = CreatTree();return 0;
}

結點個數計算

錯誤方法

int TreeSize(TreeNode* root)
{if (root == NULL)return;int size = 0;++size;TreeSize(root->left);TreeSize(root->right);return size;
}

????????這是因為每一次的遞歸都會開辟出一個幀棧，而每一塊的幀棧中都會有一個size且聲明周期僅只在自己的幀棧范圍內，在調用返回時所有的size并不會相加然后一起返回，簡單來說就是生命周期有限

不便利方法

//二叉樹代碼
.....static int size = 0;
int TreeSize(TreeNode* root)
{if (root == NULL)return;++size;TreeSize(root->left);TreeSize(root->right);return size;
}int main()
{TreeNode* root = CreatTree();printf("TreeSize：%d\n", TreeSize(root));printf("TreeSize：%d\n", TreeSize(root));printf("TreeSize：%d\n", TreeSize(root));printf("TreeSize：%d\n", TreeSize(root));return 0;
}

????????基于上次生命周期的問題，我們想到了用static來延長局部變量的生命周期，此時size的生命周期就是整個程序，但是當我們連續三次打印時發現三次的結果都不一樣，每次都比上次的結果增加了6？這也是使用static的副作用，因為被static修飾的變量（靜態變量）在整個程序中只會初始化一次，當第二次使用該靜態變量時，此次的結果與上次的結果疊加，從而出現意料之外的問題

我們需要在首次打印后，后續的每次打印前將該靜態變量人為置空后才能正常使用：

//二叉樹代碼
.....static int size = 0;
int TreeSize(TreeNode* root)
{if (root == NULL)return;++size;TreeSize(root->left);TreeSize(root->right);return size;
}int main()
{TreeNode* root = CreatTree();printf("TreeSize：%d\n", TreeSize(root));size = 0;printf("TreeSize：%d\n", TreeSize(root));size = 0;printf("TreeSize：%d\n", TreeSize(root));size = 0;printf("TreeSize：%d\n", TreeSize(root));return 0;
}

---

使用全局變量也是一樣的效果，只需要對代碼進行簡單的更改即可：

//二叉樹代碼
.....int size = 0;
void TreeSize(TreeNode* root)
{if (root == NULL)return;++size;TreeSize(root->left);TreeSize(root->right);
}int main()
{TreeNode* root = CreatTree();TreeSize(root);printf("TreeSize：%d\n", size);size = 0;TreeSize(root);printf("TreeSize：%d\n", size);size = 0;TreeSize(root);printf("TreeSize：%d\n", size);size = 0;TreeSize(root);printf("TreeSize：%d\n", size);return 0;
}

基于分治思想的方法

//二叉樹總結點個數
int TreeSize(TreeNode* root)
{return root == NULL ? 0 :TreeSize(root->left) +TreeSize(root->right) + 1;
}

解釋：主體邏輯就是判斷此時所處結點的值是否為空，若不為空則進行左遞歸，左遞歸結束后進行右遞歸，每一次左右遞歸完全結束后就會返回一個1，每次返回的結果可以疊加

葉子結點個數

//葉子結點個數
int TreeLeafSize(TreeNode* root)
{//空樹 返回0if (root == NULL)return 0;//非空樹，但是沒有左右子樹（葉子結點/僅有一個結點的樹）返回1if (root->left == NULL && root->right == NULL)return 1;//不是空 也不是葉子結點return TreeLeafSize(root->left) +TreeLeafSize(root->right);
}

解釋：主體邏輯與獲取結點總數時沒有區別，但是這里增加了一個用于判斷葉子結點的判斷條件，因為葉子結點的特殊性（沒有左右子樹），所以我們的返回1的操作操作必須要在確定該結點為葉子結點時才會返回

樹的高度

//樹的高度
int TreeHeight(TreeNode* root)
{if (root == NULL)return 0;int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

設計思想：

1. 如果即當前子樹為空，則返回 0，表示該子樹沒有任何結點，因此高度為 0
2. 如果傳入的?root?指針不為空，則執行以下操作：
   a）調用遞歸函數?TreeHeight(root->left)?來計算左子樹中結點到達最底層所需經過的邊數，并將結果賦值給變量?leftHeight
   b）調用遞歸函數?TreeHeight(root->right)?來計算右子樹中結點到達最底層所需經過邊數，并將結果賦值給變量?rightHeight
   c）返回左右子樹兩者中較大者加上當前節點本身所代表邊數（加1）作為該子問題下一級別解答（理解這里十分重要）

解釋： 1、某個結點的左子樹遞歸的三目運算符的運算結果都會在最后賦值給leftHeight，右子樹遞歸的三目運算符的運算結果都會在最后賦值給rightHeight

2、每次調用?TreeHeight?函數時都會進行三目運算符的比較，如果是葉子結點，由于沒有左右子樹為空所以兩次遞歸返回的值均為0，即leftHeight和rightHeight的值均為0（因為0>0為假，故：rightHeight+1，此時rightHeight+1里的+1是為了加上3結點本身的高度，不可能因為左右子樹均為空就沒有高度了，當前結點也算一個高度）比較后會返回1它被賦值給leftHeight，因為它是2結點的左子樹遞歸得到的，同時它也告訴了2結點你的左子樹高度只有1，然后2結點又會遞歸調用它的右子樹但是由于右子樹為NULL所以會返回0，所以此時leftHeight和rightHeight的值分別為1和0（因為1>0為真所以leftHeight+1，表明2結點的左子樹大于右子樹，左子樹的高度可以代表2結點的高度）比較后會返回2它被賦值給leftHeight，因為它是1結點的左子樹遞歸得到的，同時它也告訴了1結點你的左子樹高度為2

3、然后1結點會遞歸它的右子樹，剩余步驟與上面描述的大致相似，最后右遞歸會告訴1結點你的右子樹高度為2（因為2>2為假所rightHeight+1，此時rightHeight+1里的+1是為了加上1結點本身的高度，不可能左右子樹高度相等就沒有高度了，當前結點也算一個高度，所以當前結點的左右子樹結點高度相等，將當前左右結點子樹的高度+1就是整個樹的高度）

第k層結點的個數

//第k層結點的個數，k==2
int TreeLevelK(TreeNode* root,int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return TreeLevelK(root->left, k - 1) +TreeLevelK(root->right,k-1);
}

?設計思想：

1. 樹為空，返回0
2. 樹不為空且是第一層結點個數，返回1
3. 樹不為空且是第n(n>1)層結點的個數，返回(左子樹的k-1層 + 右子樹的k-1層)

k-1而不是k，k相當于判斷條件count，當count==1的時候就相當于找到了我們要找的那一層，如果為k，那么遞歸的返回條件就不存在

解釋：

1、查找第3層結點個數，即k == 3?

2、樹不為空，并且k != 1，所以遞歸結點1的左子樹，結點2不為空，此時k-1?= 2?!= 1，所以可以繼續遞歸結點2的左子樹，結點3不為空，此時k-1 = 1?== 1，所以返回1，即遞歸結點2左子樹的返回值為1，然后遞歸結點2的右子樹，右子樹為空返回0，最后0+1=1，即遞歸結點1左子樹的返回值為1，這說明結點1左子樹第3層的結點個數為1

3、然后遞歸結點1的右子樹，結點4不為空，此時k-1 = 2 != 1，所以可以繼續遞歸結點4的左子樹，結點5不為空，此時k - 1 =1 == 1，所以返回1，即遞歸結點4的左子樹的返回值為1，然后遞歸結點4的右子樹，結點6不為空，此時k - 1 =1 == 1（這是因為此時處于結點4的TreeLevelK函數中，此時的k為2），所以返回1，即遞歸結點4的右子樹的返回值為1，最后1+1=2，即遞歸結點1右子樹的返回值為2，這說明結點1右子樹第3層的結點個數為2

4、最后結點1的左右子樹均遞歸完璧，1+2=3，即該二叉樹第3層的結點個數為3

?~over~