#include<iostream>//cout,cin
#include<string>
using namespace std;
#include"bitree.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 << 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 << "13-删除以值为x的结点的子树\n";
	cout << "0 -退出\n";
}

int main()
{
	int level;
	BTNode<char>* bt;

	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 << "请按先序序列的顺序输入二叉树,#为空指针域标志：" << endl;
			CreateBiTree(bt);
			break;
		case 2:												// 先序递归遍历二叉树
			cout << "先序遍历序列为：" << endl;
			PreOrDerBiTree(bt);
			break;
		case 3:													// 中序递归遍历二叉树
			cout << "中序遍历序列为：" << endl;
			InOrDerBiTree(bt);
			cout << endl;
			break;
		case 4:												// 后序递归遍历二叉树
			cout << "后序遍历序列为：" << endl;
			PostOrDerBiTree(bt);
			cout << endl;
			break;
		case 5:												// 层序遍历二叉树
			cout << "层序遍历序列为：" << endl;
			cout << endl;
			LevelBiTree(bt);
			break;
		case 6:												// 先序非递归遍历二叉树
			cout << "先序非递归遍历序列为：" << endl;
			PreOrderBiTree_N(bt);
			cout << endl;
			break;
		case 7:												// 中序非递归遍历二叉树
			cout << "中序非递归遍历序列为：" << endl;
			InOrderBiTree_N(bt);
			cout << endl;
			break;
		case 8:												// 后序非递归遍历二叉树
			cout << "后序非递归遍历序列为：" << endl;
			cout << endl;
			PostOrderBiTree_N(bt);
			break;
		case 9:												// 结点查询
			char e;
			BTNode<char>* p;
			cout << "输入要查询的结点值：" << endl;
			cin >> e;
			p = Search(bt, e);
			if (p)
			{
				cout << "找到！";
				cout << p->data << endl;
			}
			else
				cout << "未找到！" << endl;
			cout << endl;
			break;
		case 10:												// 求二叉树高度
			cout << "二叉树高度为：" << Depth(bt) << endl;
			cout << endl;
			break;
		case 11:												//求二叉树结点个数
			cout << "二叉树结点数为：" << NodeCount(bt) << endl;
			cout << endl;
			break;
		case 12:												// 显示二叉树
			cout << "2-显示二叉树" << endl;
			level = 1;
			DispBiTree(bt, level);
			cout << endl;
			break;
		case 13:
			cout << "输入结点的值：";
			char x;
			cin >> x;
			DelChildWithRootX(bt, x);
			break;
		case 0:												// 退出
			DestroyBiTree(bt);
			cout << "结束运行Bye-Bye!" << endl;
			break;
		default:												// 无效选择
			cout << "Invalid choice\n";
			break;
		}
	} while (choice != 0);

	return 0;
}