[应用]二叉树叶子结点个数计算

[应用]二叉树叶子结点个数计算 二叉树叶子结点个数计算 姓名,许严 班级,计122 学号,1213023050 1. 问题描述 已知一棵二叉树,求该二叉树中叶子结点的个数。 2. 基本要求 ,1， 二叉树的二叉链表存储结构。 ,2， 设计求叶子结点个数的递归算法。 ,3， 输入,一棵二叉树。 ,4， 输出,二叉树中叶子结点的个数。 3. 实验提示 ,1， 存储设计 二叉树采用二叉链表为存储结构。 typedef struct BiTNode{ TElemType data; Struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree; ,2， 算法设计 求二叉树中叶子结点个数,即求二叉树的所有结点中左右字数均为空的结点个数之和。可以将此问题转化为遍历问题,在遍历中“访问一个结点”时判断该结点是不是叶子,若是则将计数器累加。算法如下, Void CountLeaf(BiNode*root,int &count) //前序遍历根指针为root的二叉树以计算叶子树count,假定count 的初值为0 { if(root!=NULL){ If(root->lchild==NULL&&root->rchild==NULL) Count++; CountLeaf(root->lchild,count); //累计在左子树上的叶子数 CountLeaf(root->rchild,count); //累计右子树上的叶子数 } } (3)程序如下 #include #include using namespace std; struct BiNode //二叉树的结点结构 { char data; BiNode *lchild, *rchild; }; class BiTree { public: BiTree( ); //构造函数,初始化一棵二叉树,其前序序列由键盘输入 ~BiTree(void); //析构函数,释放二叉链表中各结点的存储空间 BiNode* Getroot(); //获得指向根结点的指针 void PreOrder(BiNode *root); //前序遍历二叉树 void BiTree::yezi(BiNode *root,int &n); private: BiNode *root; //指向根结点的头指针 BiNode *Creat( ); //有参构造函数调用 void Release(BiNode *root); //析构函数调用 }; BiTree::BiTree( ) { root = Creat( ); } BiTree::~BiTree(void) { Release(root); } BiNode* BiTree::Getroot( ) { return root; } void BiTree::PreOrder(BiNode *root) { if(root==NULL) return; else{ cout<data<<" "; PreOrder(root->lchild); PreOrder(root->rchild); } } void BiTree::yezi(BiNode *root,int &n) { if(root) { if(root->lchild==NULL&&root->rchild==NULL) n++; yezi(root->lchild,n); yezi(root->rchild,n); } } BiNode* BiTree::Creat( ) { BiNode *root; char ch; cin>>ch; if (ch=='#') root = NULL; else{ root = new BiNode; //生成一个结 root->data=ch; root->lchild = Creat( ); //递归建立左子树 root->rchild = Creat( ); //递归建立右子树 } return root; } void BiTree::Release(BiNode *root) { if (root!= NULL){ Release(root->lchild); //释放左子树 Release(root->rchild); //释放右子树 delete root; } } void main() { cout<<"请输入二叉树的结点数据,"; BiTree bt; //创建一棵树 BiNode *root = bt.Getroot( ); //获取指向根结点的指针 int n=0; cout<<"------前序遍历------ "<