当前位置：首页> 二叉树叶子结点个数计算-

二叉树叶子结点个数计算-

时间：下载该word文档

二叉树叶子结点个数计算

计算二叉树叶子结点

1.程序设计简介
已知一棵二叉树，求该二叉树中叶子结点的个数。

2.基本要求
（1）设计二叉树的二叉链表为存储结构（2）设计求叶子结点个数的递归算法（3）输入：一颗二叉树
（4）输出：二叉树中叶子结点的个数

3.实现提示
（1）存储设计
二叉树采用二叉链表为存储结构 (2算法设计
求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。

4.源程序
#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;

stacks; while(NULL!=root || !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<}
int main( { root=new node; root->data=100; node *a=new node; node *b=new node; node *a1=new node; node *a2=new node; node *b1=new node; node *b2=new node; a->data=200; b->data=300; a1->data=400; a2->data=500; b1->data=600; b2->data=700;

root->lchild=a; root->rchild=b;

a->lchild=a1; a->rchild=a2;

b->lchild=b1; b->rchild=b2;

a1->lchild=NULL; a1->rchild=NULL;

a2->lchild=NULL; a2->rchild=NULL;

b1->lchild=NULL; b1->rchild=NULL;

b2->lchild=NULL; b2->rchild=NULL;

mid(root;

return 0; }

阅读全文