二叉樹第k層的葉子節點數

不論是“求二叉樹第k層的節點數”還是“求二叉樹第k層的葉子節點數”，算法思想都是二叉樹的層序周遊，在前面幾篇博文中已經多次講述，此處就不再贅述了。

求二叉樹第k層的葉子節點數，同樣有遞歸方法和非遞歸方法，本文僅講述遞歸方法，非遞歸方法可以參考前面幾篇博文來實作。

說明：根節點位于0層，每層中的第一個節點的下标為0。

具體實作如下：

#include <iostream>
using namespace std;

typedef struct node
{
    char data;
    struct node *lchild;
    struct node *rchild;
}BiNode, *BiTree;


// 先序建立二叉樹 （輸入時，按先序次序輸入二叉樹中結點的值,以 # 字元表示空樹）
BiTree createBiTree()
{
    BiTree T;

    char c;
    scanf("%c", &c);

    if (c == '#')
        T = NULL;
    else
    {
        T = new BiNode;  // 或 T = (BiTree)malloc(sizeof(BiNode));
        T->data = c;

        T->lchild = createBiTree();
        T->rchild = createBiTree();
    }

    return T;

}


// 遞歸
// 參數level代表幾層（不是第幾層）（如2層，對應的是第3層）
int num = ; // level層的總節點數；
int leafNum = ; // level層的葉子節點數；
void PrintNodeAtLevel(BiTree T , int level)
{
    if(T == NULL || level < ) return;

    if(level == )
    {

        if (T->lchild == NULL && T->rchild == NULL)
        {
            leafNum++;
        }

        num++;

    }
    PrintNodeAtLevel(T->lchild , level - );
    PrintNodeAtLevel(T->rchild , level - );
}


int main(int argc, const char * argv[]) {

    BiTree T = createBiTree(); // 建立

    PrintNodeAtLevel(T, ); // 2層葉子節點數（2層，是指第3層)

    printf("該層的節點數為: %d,  該層葉子節點數為: %d\n", num, leafNum);

    return ;
}