ep7_10.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:3k
- /*7.10 为二叉树类编写统计其度为2的结点数n2的成员函数,统计叶结点数n0的成员函数。并验证 n0= n2+1。*/
- //此题将两函数定为私有,在公有部分加接口函数
- #include<iostream>
- #include<cstdlib>
- using namespace std;
- template<typename T>class BinaryTree;
- template<typename T>class Node{
- Node<T> *lchild,*rchild;
- T info;
- public:
- Node(){lchild=NULL;rchild=NULL;}
- Node(T data,Node<T> *left=NULL,Node<T> *right=NULL){
- info=data;
- lchild=left;
- rchild=right;
- }
- friend class BinaryTree<T>;
- };
- template<typename T>class BinaryTree{
- Node<T> *root; //二叉树的根指针
- void Insert(const T &data,Node<T> * &b); //插入结点,参数为引用!
- void Destory(Node<T> * Current); //删除树
- int Countleaf(Node<T> *btree); //叶结点计数
- int CountNode2(Node<T> *btree);//度为2的结点计数
- public:
- BinaryTree(){root=NULL;} //空树构造函数
- ~BinaryTree(){Destory(root);} //析构函数
- void Creat(T* data,int n); //建立(排序)二叉树
- int Countleaf(){return Countleaf(root);} //叶结点计数接口
- int CountNode2(){return CountNode2(root);}//度为2的结点计数接口
- };
- template<typename T> void BinaryTree<T>::Destory(Node<T> *Current){
- if(Current!=NULL){
- Destory(Current->lchild);
- Destory(Current->rchild);
- delete Current; //后序释放根结点
- }
- }
- template<typename T>void BinaryTree<T>::Insert(const T &data,Node<T> * &b){
- if(b==NULL){ //已到空树,插入
- b=new Node<T>(data);
- if(b==NULL){
- cout<<"空间不足"<<endl;
- exit(1);
- }
- }
- else if(data<b->info) Insert(data,b->lchild); //小于,向左子树去查
- else Insert(data,b->rchild); //大于等于,向右子树去查
- }
- template<typename T>void BinaryTree<T>::Creat(T* data,int n){//建立一棵二叉排序树
- for(int i=0;i<n;i++) Insert(data[i],root);
- }
- template<typename T>int BinaryTree<T>::Countleaf(Node<T> *btree){//叶结点计数
- int num1,num2;
- if(btree==NULL)return 0;
- else if(btree->lchild==NULL&&btree->rchild==NULL)return 1;
- else{
- num1=Countleaf(btree->lchild);
- num2=Countleaf(btree->rchild);
- return(num1+num2);
- }
- }
- template<typename T>int BinaryTree<T>::CountNode2(Node<T> *btree){//度为2的结点计数
- int num=0;
- if(btree!=NULL){
- if(btree->lchild!=NULL&&btree->rchild!=NULL) num+=1;;
- num+=CountNode2(btree->lchild);
- num+=CountNode2(btree->rchild);
- }
- return num;
- }
- int main(){
- const int n=15;
- int i,a[n]={10,5,15,8,3,18,13,12,14,16,20,1,4,6,9};
- BinaryTree<int> btree;
- btree.Creat(a,n);
- cout<<"输入数据:"<<endl;
- for(i=0;i<n;i++) cout<<a[i]<<'t';
- cout<<endl<<"叶结点计数:"<<endl;
- cout<<btree.Countleaf()<<endl; //叶结点计数:8
- cout<<endl<<"度为2结点计数:"<<endl;
- cout<<btree.CountNode2()<<endl; //度为2的结点计数:7
- return 0;
- }