#include<iostream>
using namespace std;

struct BTNode
{
     int data;     //数据域
	BTNode *lchild;//指向左子树的指针
	BTNode *rchild;//指向右子树的指针

};

class BinaryTree 
{
	BTNode<char> *BT;
public :
	BinaryTree () {BT=NULL;}
	~BinaryTree(){clear (BT);}
	void ClearBinaryTree(){clear(BT); BT=NULL;};
	void CreateBiTree( T end);
	bool IsEmpty ();
	int BiTreeDepth();
	void PreTraBiTree();
	int LeafCount();
	void DisplayBTreeShape(BTNode<T> *bt,int level=1);

};


void BinaryTree <T>::CreateBiTree(T end)
{//创建一颗二叉树：按先序序列的顺序输入数据，end为结束标志
	cout<<"按先序输入二叉树；-1为空指针域标志："<<endl;
	BTNode< > * p;
	  x ;
	cin>>x;
	if (x==end) return;
	p=new BTNode<T>;
	if(!p)
	{
		cout<<"申请内存失败！"<<endl;
		exit(-1);//申请内存失败退出
	}
	p->data=x;
	p->lchild=NULL;
	p->rchild=NULL;
	BT=p;
	create(p,1,end);
	create(p,2,end);
}

static int create(BTNode < >*p,int k,  end)
{
	BTNode< > *q;
	 x;
	cin>>x;
	if(x!=end)
	{
		q=new BTNode< >;
		q->data=x;
		q->lchild=NULL;
		q->rchild=NULL;
		if(k==1) p->lchild=q;
		if(k==2) p->rchild=q;
		create (q,1,end);
		create(q,2,end);
	}
	return 0;

}
bool BinaryTree< >::IsEmpty()
{
	if (BT==NULL) return true;
	return false;
}

int BinaryTree< >::LeafCount()
{
	int count=0;
	return Leaf(BT,count);
}
static int Leaf(BTNode<T> *p,int &count)
{
	static int count=0;
	if(p)
	{
		if (p->lchild==NULL&&p->rchild==NULL) count++;
		Leaf (p->lchild,count);
		Leaf(p->rchild,count);
	}
	return count;
}
void BinaryTree<T>::DisplayBTreeShape(BTNode< > *bt,int int level)
{
	if (bt)
	{DisplayBTreeShape(bt->rchild,leavel+1);
	cout<<endl;
	for (int i=0;i<level-1;i++)
		cout<<"   ";
	cout<<bt->data;
	DisplayBTreeShape(bt->lchild,level+1);
	}
}


#include"BinaryTree.cpp"
#include"windows.h"
int main()
{
	int MainMenu=-1;
	BinaryTree<int>T;
	BinaryTree<int>t;
	while (MainMenu!=4)
	{
		system("cls");
		cout<<"--------------------主菜单------------------------"<<endl;
		cout <<1--创建二叉树（类型为整型）"<<endl;
		cout<<"2--树型显示二叉树"<<endl;
		cout<<"3--叶子结点数"<<endl;
		cout<<"4--退出"<<endl;
		cout<<"---------------------------------------------------"endl;
		cout<<"   请选择操作：[]";
		cout<<\b\b";
		cin>>MainMenu;
		swtch(MainMenu)
		{
			case 1:
				T.CreateBiTree(-1);
				break;
			case 2:
				cout<<"下面显示的是一颗左转了90度的树！"<<endl;
				T.DisplayBTreeShape(T.GetRoot());
				cout<<endl;
				system("pause");
				break;
			case 3:
				cout<<"二叉树的叶子结点的个数为:"<<T.LeafCount()<<endl;
				system("pause");break;
			case 4:
				cout<<"程序运行结束,拜拜！"<<endl;
				break;
			default:
				break;
	}
	}
	return 0;

	}