#include<iostream>//cout,cin
#include<string>
using namespace std;
#include"bitree.h"
#include"SqQueue_bt.h"
#include"SqStack_bt.h"
																//测试参考数据
string  fbt="a b d # # e # # c f # # g # #";					// 满二叉树最后一层每个叶结点后有两个#
string  cbt="a b d # # e # # c # #";							// 完全二叉树每个叶结点后有两个#
string  gbt="a b # d # # c e # # #";							// 一般二叉树
string  obt="a b c d # # # # #";								// 左斜树1


void dispmenu()
{																//显示主菜单
	cout<<"\n功能选择（1~12，0退出！）"<<endl;
	cout<<"1-创建二叉树\n";
	cout<<"2-先序递归遍历二叉树\n";
	cout<<"3-中序递归遍历二叉树\n";
	cout<<"4-后序递归遍历二叉树\n";
	cout<<"5-层序遍历二叉树\n";
	cout<<"6-先序非递归遍历二叉树\n";
	cout<<"7-中序非递归遍历二叉树\n";
	cout<<"8-后序非递归遍历二叉树\n";
    cout<<"9-结点查询\n";
	cout<<"10-求二叉树高度\n";
	cout<<"11-求二叉树结点个数\n";
	cout<<"12-显示二叉树\n";
	cout<<"0 -退出\n";
}

void main()
{	
	int level;
	BTNode<char> *bt;
	int y=100,x=350;
	
   system("cls");													// 清屏
    
	int choice;
    do
	{
		dispmenu();													// 显示主菜单
		cout<<"Enter choice(1~12，0 退出):";
		cin>>choice;
		switch(choice)
		{
			case 1:													// 创建二叉树 
				cout<<"测试参考数据："<<endl;
				cout<<"满二叉树："<<fbt<<endl;
	            cout<<"完全二叉树："<<cbt<<endl;
	            cout<<"一般二叉树："<<gbt<<endl;
	            cout<<"左斜二叉树："<<obt<<endl;
				cout<<"\n请按先序序列的顺序输入二叉树,#为空指针域标志："<<endl;
				CreateBiTree(bt);
				cout<<"创建的二叉树为："<<endl;
				level=1;
			    DispBiTree(bt,level);
				break;
		     case 2:												// 先序递归遍历二叉树
				 cout<<"\n先序遍历序列为："<<endl;
                 PreOrDerBiTree(bt);
			 	 break;
			case 3:													// 中序递归遍历二叉树
				 cout<<"\n中序遍历序列为："<<endl;
                 InOrDerBiTree(bt);
				 cout<<endl;
				 break;	
			 case 4:												// 后序递归遍历二叉树
                 cout<<"\n后序遍历序列为："<<endl;
                 PostOrDerBiTree(bt);
				 cout<<endl;
				 break;
			 case 5:												// 层序遍历二叉树
				 cout<<"\n层序遍历序列为："<<endl;
				 cout<<endl;
				 LevelBiTree(bt);
				 break;
			 case 6:												// 先序非递归遍历二叉树
				 cout<<"\n先序非递归遍历序列为："<<endl;
				 PreOrderBiTree_N(bt);
				 cout<<endl;
				 break;
			 case 7:												// 中序非递归遍历二叉树
				 cout<<"\n中序非递归遍历序列为："<<endl;
				 InOrderBiTree_N(bt);
				 cout<<endl;
				 break;
			 case 8:												// 后序非递归遍历二叉树
				  cout<<"\n后序非递归遍历序列为："<<endl;
				  cout<<endl;
				  PostOrderBiTree_N(bt);
				  break;
             case 9:												// 结点查询
				 char e;
				 BTNode<char> *p;
				 cout<<"\n输入要查询的结点值："<<endl;
				 cin>>e; 
				 p=Search(bt,e);
				 if(p)
				 {
					 cout<<"\n找到！";
					 cout<<p->data<<endl;					 
				 }
				 else
					 cout<<"\n未找到！"<<endl;
				 cout<<endl;
				 break;
			 case 10:												// 求二叉树高度
				 cout<<"\n二叉树高度为："<<Depth(bt)<<endl;
				 cout<<endl;
				 break;
			case 11:												//求二叉树结点个数
				cout<<"\n二叉树结点数为："<<NodeCount(bt)<<endl;
				cout<<endl;
				break;
			case 12:												// 显示二叉树
			   cout<<"\n二叉树:"<<endl;
			   level=1;
			   DispBiTree(bt,level);
			   cout<<endl;
			   break;
			case 0:												// 退出
                DestroyBiTree(bt);
				cout<<"\n结束运行Bye-Bye!"<<endl;
                break;
			default:												// 无效选择
				cout<<"无效选择，请重新选择（1~12，0退出）\n";
				break;
			}
	}while(choice!=0);
   
	return;
}