开发者社区> 问答> 正文

编写递归算法,计算二叉树中叶子结点的数目

编写递归算法,计算二叉树中叶子结点的数目

展开
收起
知与谁同 2018-07-18 16:52:39 2235 0
2 条回答
写回答
取消 提交回答
  • 云栖社区聚能聊、问答管理员~发福利、搞怪,八卦我来,论技术、发话题、写博客你上!
    int leafNum(bnode* root)
    {
    static int num=0;
    if(!root->left&&!root->right)
    num++;
    if(root->left)
    leafNum(root->left);
    if(root->right)
    leafNum(root->right);

    return num;
    }
    2019-07-17 22:55:36
    赞同 展开评论 打赏
  • #include<iostream>
    using namespace std;

    typedef struct TNode//二叉树结构
    {
    char nodeValue;//结点的值
    TNode* left;//左子树
    TNode* right;//右子树
    }*BiTree;
    void CreateBiTree(BiTree &T)//中序遍历方式创建二叉树 ,输入#代表该结点为空
    {
    char nodeValue;
    cin>> nodeValue;
    if(nodeValue!='#')//结点非空
    {
    T=new TNode;
    T->nodeValue=nodeValue;
    CreateBiTree(T->left);
    CreateBiTree(T->right);
    }
    else T=NULL;

    }
    int CountLeaf(BiTree T)
    {
    static int LeafNum=0;//叶子初始数目为0,使用静态变量
    if(T)//树非空
    {
    if(T->left==NULL&&T->right==NULL)//为叶子结点
    LeafNum++;//叶子数目加1
    else//不为叶子结点
    {
    CountLeaf(T->left);//递归统计左子树叶子数目
    CountLeaf(T->right);//递归统计右子树叶子数目
    }
    }
    return LeafNum;
    }
    //用来测试的main函数,
    int main()
    {
    BiTree T;
    int leafNum;
    cout<<"请输入中序遍历的二叉树序列(#号代表该结点为空):如(ABC##DE#G##F###)"<<endl;
    CreateBiTree(T);
    leafNum=CountLeaf(T);
    cout<<"该二叉树中叶子结点数为:"<<leafNum<<endl;
    return 0;
    }
    2019-07-17 22:55:36
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载