编写递归算法,计算二叉树中叶子结点的数目
收起
知与谁同
2018-07-18 16:52:39
2233
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