資源描述:
《二叉樹葉子結(jié)點個數(shù)計算.doc》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、.計算二叉樹葉子結(jié)點1.程序設(shè)計簡介已知一棵二叉樹,求該二叉樹中葉子結(jié)點的個數(shù)。2.基本要求(1)設(shè)計二叉樹的二叉鏈表為存儲結(jié)構(gòu)(2)設(shè)計求葉子結(jié)點個數(shù)的遞歸算法(3)輸入:一顆二叉樹(4)輸出:二叉樹中葉子結(jié)點的個數(shù)3.實現(xiàn)提示(1)存儲設(shè)計二叉樹采用二叉鏈表為存儲結(jié)構(gòu)(2)算法設(shè)計求二叉樹中葉子結(jié)點個數(shù),即求二叉樹的所有結(jié)點中左、右子樹均為空的結(jié)點個數(shù)之和??梢詫⒋藛栴}轉(zhuǎn)化為遍歷問題,在遍歷中“訪問一個結(jié)點”時判斷該結(jié)點是不是葉子,若是則將計數(shù)器累加。4.源程序#include#includeus
2、ingnamespacestd;..structBiNode//二叉樹的結(jié)點結(jié)構(gòu){chardata;BiNode*lchild,*rchild;};classBiTree{public:BiTree();//構(gòu)造函數(shù),初始化一棵二叉樹,其前序序列由鍵盤輸入~BiTree(void);//析構(gòu)函數(shù),釋放二叉鏈表中各結(jié)點的存儲空間BiNode*Getroot();//獲得指向根結(jié)點的指針voidPreOrder(BiNode*root);//前序遍歷二叉樹voidBiTree::yezi(BiNode*root,int&n);private
3、:BiNode*root;//指向根結(jié)點的頭指針BiNode*Creat();//有參構(gòu)造函數(shù)調(diào)用voidRelease(BiNode*root);//析構(gòu)函數(shù)調(diào)用};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;//生成一個結(jié)點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<<"請輸入二叉樹的結(jié)點數(shù)據(jù):";BiTreebt;//創(chuàng)建一棵樹BiNod
6、e*root=bt.Getroot();//獲取指向根結(jié)點的指針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