求二叉树的叶子节点个数

Question

假设二叉树采用二叉链存储结构存储，设计一个算法计算一棵给定二叉树的所有叶子节点个数。

Answer 1

#include<iostream>
using namespace std;

//二叉树节点
struct BinaryNode
{
    char ch;
    BinaryNode* lchild;
    BinaryNode* rchild;
};
void CaculateLeafNum(BinaryNode* root);
int Leaf_Count = 0;  //不能定义在CaculateLeafNum()函数内。
void CaculateLeafNum(BinaryNode* root) {
    if (!root) return;
    if (root->lchild == NULL && root->rchild == NULL) Leaf_Count++;

    CaculateLeafNum(root->lchild);
    CaculateLeafNum(root->rchild);
}

//初始化二叉树
void CreateBinaryTree() {
    BinaryNode node1 = { 'A',NULL,NULL };
    BinaryNode node2 = { 'B',NULL,NULL };
    BinaryNode node3 = { 'C',NULL,NULL };
    BinaryNode node4 = { 'D',NULL,NULL };
    BinaryNode node5 = { 'E',NULL,NULL };
    BinaryNode node6 = { 'F',NULL,NULL };
    BinaryNode node7 = { 'G',NULL,NULL };
    BinaryNode node8 = { 'H',NULL,NULL };
    //建立节点关系
    node1.lchild = &node2;
    node1.rchild = &node6;
    node2.rchild = &node3;
    node3.lchild = &node4;
    node3.rchild = &node5;
    node6.rchild = &node7;
    node7.lchild = &node8;
    CaculateLeafNum(&node1);  //调用函数
    cout << "Num of Leaf:" << Leaf_Count << endl;
}
//二叉树遍历

int main() {
    CreateBinaryTree();
}