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

计算二叉树叶子结点1. 程序设计简介已知一棵二叉树，求该二叉树中叶子结点的个数。2. 基本要求（1） 设计二叉树的二叉链表为存储结构（2） 设计求叶子结点个数的递归算法（3） 输入：一颗二叉树（4） 输出：二叉树中叶子结点的个数3. 实现提示（1） 存储设计 二叉树采用二叉链表为存储结构 (2)算法设计 求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。4.源程序#include#includeusing namespace std;struct BiNode /二叉树的结点结构 char data; BiNode *lchild, *rchild;class BiTreepublic: 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;elsecoutdatalchild);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;cinch; 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-前序遍历- endl;bt.PreOrder(root);bt.yezi(root,n);coutendl;cout叶子节点数：n;coutendl;5.运行与测试6.调试感想非递归算法求叶子结点的个数#include#includeusing namespace std;struct nodeint data;node *lchild;node *rchild;node *root=NULL;void mid(node*root,int key=500)int sum=0;stacks;while(NULL!=root | !s.empty()if(NULL!=root)s.push(root);root=root-lchild;elseroot=s.top();/coutdatalchild & NULL=root-rchild)+sum;s.pop();root=root-rchild;coutsumdata=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;