文章目錄
- 結點的個數
- 代碼實作
- 圖解遞回
- 葉子結點的個數
- 代碼實作
- 圖解遞回
- 第k層結點的個數
- 代碼實作
- 圖解遞回
- 值為x的結點
- 代碼實作
- 圖解遞回
結點的個數
求解樹的結點總數時，可以將問題拆解成子問題：
1.若為空，則結點個數為0，
2.若不為空，則結點個數 = 左子樹結點個數 + 右子樹結點個數 + 1（自己），
代碼實作
int BinaryTreeSize(BT* root)
{
//結點個數 = 左子樹的結點個數 + 右子樹的結點個數 + 自己
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
圖解遞回
當你自己畫完其遞回程序后，你會發現其實它就相當于后序遍歷，BinaryTreeSize（root->left）相當于左子樹，BinaryTreeSize（root->right）相當于右子樹，而最后加的那個1，其實就是根結點，
葉子結點的個數
子問題拆解：
1.若為空，則葉子結點個數為0，
2.若結點的左指標和右指標均為空，則葉子結點個數為1，
3.除上述兩種情況外，說明該樹存在子樹，其葉子結點個數 = 左子樹的葉子結點個數 + 右子樹的葉子結點個數，
代碼實作
int BinaryTreeLeafSize(BT* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL&&root->right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
圖解遞回
這里要注意，root==NULL這個必須寫在最前面，不能寫在后面，因為萬一是空樹的情況，那樣你root->left訪問就會出問題，
第k層結點的個數
思路：
相對于根結點的第k層結點的個數 = 相對于以其左孩子為根的第k-1層結點的個數 + 相對于以其右孩子為根的第k-1層結點的個數
代碼實作
int BinaryKlevelSize(BT* root,int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryKlevelSize(root->left, k - 1) + BinaryTreeKLevelSize(root->right, k - 1);
}
圖解遞回
值為x的結點
子問題：
1.先判斷根結點是否是目標結點，
2.再去左子樹中尋找，
3.最后去右子樹中尋找，
代碼實作
BT* BinaryTreeFind(BT* root,BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->x == x)
{
return root;
}
struct BinaryNode* ansleft = BinaryTreeFind(root->left, x);
if (ansleft)
{
return ansleft;
}
struct BinaryNode* ansright = BinaryTreeFind(root->right, x);
if (ansright)
{
return ansright;
}
return NULL;
}
這塊代碼其實是很容易寫出一個編譯器的Bug的，讀者不防試試把前面兩個if的{}去掉試試看，此時你就會發現一個編譯器的Bug，
關于這個問題讀者們有興趣的話可以去看看我寫的這篇文章：💥不經意之間的Bug（1）：有些編譯器可能在某些情況下無法識別typedef定義的識別符號
圖解遞回
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298661.html
標籤：其他
上一篇：MEMZ病毒詳細分析