二叉树.cpp

二叉树的操作

#include<iostream>
using namespace std;
template<class T>
class Binnode                   //二叉树结点类
{ 
public:
T  element; 
Binnode *left;  
Binnode *right;  
//成员函数
Binnode(){left=right=NULL;element=NULL;}                //构造函数
Binnode(T e, Binnode *l=NULL,Binnode *r=NULL)
{element=e;left=l;right=r;}                            //构造函数
~Binnode(){}                                           //析构函数
Binnode *leftchild() const{return  left;}             //返回结点的左孩子
Binnode *rightchild() const{return  right;}           //返回结点的右孩子
T value() const{return  element;}                     // 返回结点的值
bool  isLeaf() const{return((left==Null)&&(right==Null));}  //判断是否是叶子结点
};
template <class T>
void creat(Binnode<T> *&rt)                          //先序遍历创建二叉树
{
	T a;
	cout<<"输入结点的值（输入“#”则无叶子结点）：";
	cin>>a;
	if (a=='#') rt=NULL;
	else
	{
		rt=new Binnode<T>;
		rt->element=a;
		creat(rt->left);
		creat(rt->right);
	}
}
template <class T>
void postorder(Binnode<T> *rt)
{
	if (rt==NULL) return;
	postorder(rt->leftchild());
	postorder(rt->rightchild());
	cout<<rt->element<<"  ";
}
template <class T>
void count(Binnode<T> *rt,int &n)                 //计算叶子节点个数,输出叶子结点个数
{
	if (rt==NULL) return ;
    count(rt->left,n);
    count(rt->right,n);
    if((rt->left==NULL)&&(rt->right==NULL))
	{
		n++;
		cout<<rt->element<<"   ";
	}
}

void main()
{
	int n=0;
	Binnode<char> *s;
	s=new Binnode<char>;
	creat(s);
	cout<<"后序遍历的结果："<<"\n";
	postorder(s);
	cout<<"叶子结点为："<<"\n";
	count(s,n);
	cout<<"\n";
	cout<<"叶子结点个数为："<<"\n";
 	cout<<n<<endl;
}