二叉树叶子结点个数计算.doc

文档介绍：计算二叉树叶子结点程序设计简介已知一棵二叉树,求该二叉树中叶子结点的个数。基本要求设计二叉树的二叉链表为存储结构设计求叶子结点个数的递归算法输入:一颗二叉树输出:二叉树中叶子结点的个数实现提示存储设计二叉树采用二叉链表为存储结构(2)算法设计求二叉树中叶子结点个数,即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题,在遍历中“访问一个结点”时判断该结点是不是叶子,若是则将计数器累加。#include<iostream>#include<string>usingnamespacestd;structBiNode//二叉树的结点结构{chardata;BiNode*lchild,*rchild;};classBiTree{public:BiTree();//构造函数,初始化一棵二叉树,其前序序列由键盘输入~BiTree(void);//析构函数,释放二叉链表中各结点的存储空间 BiNode*Getroot();//获得指向根结点的指针voidPreOrder(BiNode*root);//前序遍历二叉树 voidBiTree::yezi(BiNode*root,int&n);private:BiNode*root;//指向根结点的头指针BiNode*Creat();//有参构造函数调用voidRelease(BiNode*root);//析构函数调用};BiTree::BiTree(){ root=Creat();}BiTree::~BiTree(void){ Release(root);}BiNode*BiTree::Getroot(){ returnroot;}voidBiTree::PreOrder(BiNode*root){ if(root==NULL)return; else{ cout<<root->data<<"";PreOrder(root->lchild); PreOrder(root->rchild); }}voidBiTree::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; charch; cin>>ch;if(ch=='#')root=NULL;else{ root=newBiNode;//生成一个结点root->data=ch;root->lchild=Creat();//递归建立左子树root->rchild=Creat();//递归建立右子树}returnroot;}voidBiTree::Release(BiNode*root){if(root!=NULL){ Release(root->lchild);//释放左子树Release(root->rchild);//释放右子树deleteroot;}}voidmain(){cout<<"请输入二叉树的结点数据:"; BiTreebt;//创建一棵树 BiNode*root=();//获取指向根结点的指针intn=0; cout<<"---