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

《二叉树叶子结点个数计算.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.计算二叉树叶子结点1.程序设计简介已知一棵二叉树，求该二叉树中叶子结点的个数。2.基本要求（1）设计二叉树的二叉链表为存储结构（2）设计求叶子结点个数的递归算法（3）输入：一颗二叉树（4）输出：二叉树中叶子结点的个数3.实现提示（1）存储设计二叉树采用二叉链表为存储结构(2)算法设计求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。4.源程序#include#includeus

2、ingnamespacestd;..structBiNode//二叉树的结点结构{chardata;BiNode*lchild,*rchild;};classBiTree{public:BiTree();//构造函数，初始化一棵二叉树，其前序序列由键盘输入~BiTree(void);//析构函数，释放二叉链表中各结点的存储空间BiNode*Getroot();//获得指向根结点的指针voidPreOrder(BiNode*root);//前序遍历二叉树voidBiTree::yezi(BiNode*root,int&n);private

3、: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<data<<"";P

4、reOrder(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=newBiN

5、ode;//生成一个结点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;//创建一棵树BiNod

6、e*root=bt.Getroot();//获取指向根结点的指针intn=0;cout<<"------前序遍历------"<#includeusingnamespacestd;structnode{intdata;node*lchild;node*rchild;};no

7、de*root=NULL;voidmid(node*root,intkey=500){intsum=0;..stacks;while(NULL!=root

8、

9、!s.empty()){if(NULL!=root){s.push(root);root=root->lchild;}else{root=s.top();//cout<data<<"";if(NULL==root->lchild&&NULL==root->rchild)++sum;s.pop();root=root->rchild;}}cout<

10、<data=100;node*a=newnode;node*b=newnode;node*a1=newnode;node*a2=new