計(jì)算二叉樹(shù)葉子結(jié)點(diǎn)1. 程序設(shè)計(jì)簡(jiǎn)介已知一棵二叉樹(shù)，求該二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)。2. 基本要求（1） 設(shè)計(jì)二叉樹(shù)的二叉鏈表為存儲(chǔ)結(jié)構(gòu)（2） 設(shè)計(jì)求葉子結(jié)點(diǎn)個(gè)數(shù)的遞歸算法（3） 輸入：一顆二叉樹(shù)（4） 輸出：二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)3. 實(shí)現(xiàn)提示（1） 存儲(chǔ)設(shè)計(jì) 二叉樹(shù)采用二叉鏈表為存儲(chǔ)結(jié)構(gòu) (2)算法設(shè)計(jì) 求二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)，即求二叉樹(shù)的所有結(jié)點(diǎn)中左、右子樹(shù)均為空的結(jié)點(diǎn)個(gè)數(shù)之和。可以將此問(wèn)題轉(zhuǎn)化為遍歷問(wèn)題，在遍歷中“訪問(wèn)一個(gè)結(jié)點(diǎn)”時(shí)判斷該結(jié)點(diǎn)是不是葉子，若是則將計(jì)數(shù)器累加。4.源程序#include#includeusing namespace std;struct BiNode /二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu) char data; BiNode *lchild, *rchild;class BiTreepublic: BiTree( ); /構(gòu)造函數(shù)，初始化一棵二叉樹(shù)，其前序序列由鍵盤(pán)輸入 BiTree(void); /析構(gòu)函數(shù)，釋放二叉鏈表中各結(jié)點(diǎn)的存儲(chǔ)空間BiNode* Getroot(); /獲得指向根結(jié)點(diǎn)的指針 void PreOrder(BiNode *root); /前序遍歷二叉樹(shù)void BiTree:yezi(BiNode *root,int &n);private: BiNode *root; /指向根結(jié)點(diǎn)的頭指針 BiNode *Creat( ); /有參構(gòu)造函數(shù)調(diào)用 void Release(BiNode *root); /析構(gòu)函數(shù)調(diào)用;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; /生成一個(gè)結(jié)點(diǎn) root-data=ch; root-lchild = Creat( ); /遞歸建立左子樹(shù) root-rchild = Creat( ); /遞歸建立右子樹(shù) return root;void BiTree:Release(BiNode *root) if (root!= NULL) Release(root-lchild); /釋放左子樹(shù) Release(root-rchild); /釋放右子樹(shù) delete root; void main() cout請(qǐng)輸入二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)：;BiTree bt; /創(chuàng)建一棵樹(shù)BiNode *root = bt.Getroot( ); /獲取指向根結(jié)點(diǎn)的指針 int n=0;cout-前序遍歷- endl;bt.PreOrder(root);bt.yezi(root,n);coutendl;cout葉子節(jié)點(diǎn)數(shù)：n;coutendl;5.運(yùn)行與測(cè)試6.調(diào)試感想非遞歸算法求葉子結(jié)點(diǎn)的個(gè)數(shù)#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;