二叉樹葉子結點個數(shù)計算

《二叉樹葉子結點個數(shù)計算》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、數(shù)據(jù)結構實驗報告二叉樹葉子結點個數(shù)計算姓名：許嚴班級：計122學號：12130230501.問題描述已知一棵二叉樹，求該二叉樹中葉子結點的個數(shù)。2.基本要求（1）設計二叉樹的二叉鏈表存儲結構。（2）設計求葉子結點個數(shù)的遞歸算法。（3）輸入：一棵二叉樹。（4）輸出：二叉樹中葉子結點的個數(shù)。3.實驗提示（1）存儲設計二叉樹采用二叉鏈表為存儲結構。typedefstructBiTNode{TElemTypedata;StructBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTre

2、e;（2）算法設計求二叉樹中葉子結點個數(shù)，即求二叉樹的所有結點中左右字數(shù)均為空的結點個數(shù)之和。可以將此問題轉化為遍歷問題，在遍歷中“訪問一個結點”時判斷該結點是不是葉子，若是則將計數(shù)器累加。算法如下：VoidCountLeaf(BiNode*root,int&count)//前序遍歷根指針為root的二叉樹以計算葉子樹count,假定count的初值為0{if(root!=NULL){If(root->lchild==NULL&&root->rchild==NULL)Count++;CountLeaf(ro

3、ot->lchild,count);//累計在左子樹上的葉子數(shù)CountLeaf(root->rchild,count);//累計右子樹上的葉子數(shù)}}(3)程序如下#include#includeusingnamespacestd;structBiNode//二叉樹的結點結構{chardata;BiNode*lchild,*rchild;};classBiTree{public:BiTree();//構造函數(shù)，初始化一棵二叉樹，其前序序列由鍵盤輸入4數(shù)據(jù)結構實驗報告~BiTre

4、e(void);//析構函數(shù)，釋放二叉鏈表中各結點的存儲空間BiNode*Getroot();//獲得指向根結點的指針voidPreOrder(BiNode*root);//前序遍歷二叉樹voidBiTree::yezi(BiNode*root,int&n);private:BiNode*root;//指向根結點的頭指針BiNode*Creat();//有參構造函數(shù)調(diào)用voidRelease(BiNode*root);//析構函數(shù)調(diào)用};BiTree::BiTree(){root=Creat();}BiTree:

5、:~BiTree(void){Release(root);}BiNode*BiTree::Getroot(){returnroot;}voidBiTree::PreOrder(BiNode*root){if(root==NULL)return;else{cout<data<<"";PreOrder(root->lchild);PreOrder(root->rchild);}}voidBiTree::yezi(BiNode*root,int&n){if(root){if(root->lchild==N

6、ULL&&root->rchild==NULL)n++;yezi(root->lchild,n);yezi(root->rchild,n);}}BiNode*BiTree::Creat(){BiNode*root;4數(shù)據(jù)結構實驗報告charch;cin>>ch;if(ch=='#')root=NULL;else{root=newBiNode;//生成一個結root->data=ch;root->lchild=Creat();//遞歸建立左子樹root->rchild=Creat();//遞歸建立右子樹}retur

7、nroot;}voidBiTree::Release(BiNode*root){if(root!=NULL){Release(root->lchild);//釋放左子樹Release(root->rchild);//釋放右子樹deleteroot;}}voidmain(){cout<<"請輸入二叉樹的結點數(shù)據(jù)：";BiTreebt;//創(chuàng)建一棵樹BiNode*root=bt.Getroot();//獲取指向根結點的指針intn=0;cout<<"------前序遍歷------"<

8、r(root);bt.yezi(root,n);cout<