[数据结构与算法]统计二叉树的叶子节点个数

#include <iostream>
#include <queue>

using namespace std;

typedef struct node {
    char data;
    struct node *lchild;
    struct node *rchild;
} TNode;

TNode *CreateTree(TNode *&t);

int Count(TNode *t); //统计t的叶子节点个数,非递归
int R_Count(TNode *t); //统计t的叶子节点个数,递归

int main() {
    auto t = new TNode ;
    CreateTree(t);
    //或者采用 t = CreateTree(t),
    // 此时的CreateTree(TNode *t)，不需要使用引用符号
    int num = R_Count(t);
    cout<<num<<endl;
    return 0;
}

TNode *CreateTree(TNode *&t) {
    char c;
    cin >> c;
    if (c == '#')
        t = nullptr;
    else {
        //所以如果中序创建只需要把这个放在中间
        t = new TNode ;
        t->data = c;//相当于vision()函数
        t->lchild = CreateTree(t->lchild);
        t->rchild = CreateTree(t->rchild);
    }
    return t;
}

int Count(TNode *t){
    queue <TNode *> q;
    int flag = 0; //计算的是度为2节点的个数
    if (t->lchild!= nullptr&&t->rchild!= nullptr){
        q.push(t);
    }
    TNode * p;
    while (!q.empty()){
        p = q.front();
        q.pop();
        if (p->lchild!= nullptr&&p->rchild!= nullptr){
            flag+=1;
            q.push(p->lchild);
            q.push(p->rchild);
        }
    }
    return flag+=1;
}

int R_Count(TNode *t){
    if (t== nullptr)
        return 0;
    if (t->lchild== nullptr&&t->rchild== nullptr)
        return 1;
    return R_Count(t->lchild)+ R_Count(t->rchild);
}