ep7_10.cpp

这里有大量的c语言习题呢！真的是题海哦

/*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;
}