《二叉树叶子结点个数计算》由会员分享，可在线阅读，更多相关《二叉树叶子结点个数计算（13页珍藏版）》请在金锄头文库上搜索。
1、1程序设计简介已知一棵二叉树，求该二叉树中叶子结点的个数。2基本要求（1）设计二叉树的二叉链表为存储结构（2）设计求叶子结点个数的递归算法（3）输入：一颗二叉树（4）输出：二叉树中叶子结点的个数3实现提示（1 ）存储设计二叉树采用二叉链表为存储结构（2 ）算法设计求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子 树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中 “访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。4源程序#in clude #in cludeusing n amespace std;struct BiNode 二叉树的结点结构char data;BiN
2、ode *lchild, *rchild;；class BiTreepublic:BiTree();构造函数，初始化一棵二叉树，其前序序列由键盘输入BiTree(void);析构函数，释放二叉链表中各结点的存储空间BiNode* Getroot(); 获得指向根结点的指针void PreOrder(BiNode *root); 前序遍历二叉树void BiTree:yezi(BiNode *root,i nt &n);private:BiNode *root;指向根结点的头指针BiNode *Creat();有参构造函数调用void Release(BiNode *root);析构函数调用 ;
3、BiTree:BiTree() root = Creat();BiTree:BiTree(void)Release(root);BiNode* BiTree:Getroot()return root;void BiTree:PreOrder 侣iNode *root)if(root=NULL) return;elsecoutdatalchild);PreOrder(root-rchild);void BiTree:yezi(BiNode *root,i nt &n)if(root)if(root-lchild=NULL&root-rchild=NULL) n+;yezi(root-lchild
4、, n);yezi(root-rchild, n);BiNode* BiTree:Creat()BiNode *root;char ch;cin ch;if (ch=#) root = NULL;elseroot = 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-rc
5、hild);释放右子树delete root;void mai n()cout请输入二叉树的结点数据：;BiTree bt; 创建一棵树BiNode *root = bt.Getroot(); 获取指向根结点的指针int n=0;cout前序遍历e ndl;bt. PreOrder(root);bt.yezi(root, n);coute ndl;cout叶子节点数：n;coute ndl;5运行与测试6调试感想非递归算法求叶子结点的个数#in clude#in cludeusing n amespace std;struct nodeint data;node *lchild;node *r
6、child;；node *root=NULL;void mid( no de*root,i nt key=500)int sum=0;stack s;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 no de;node *b=new no de;node *a1= new n
7、o de;node *a2=new no de;node *b1= new no de;node *b2=new no de;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;
