#include<math.h>
#include<vector>
#include<iostream>
#include<time.h>
using namespace std;

constexpr auto ARRAY_INIT_SIZE = 100; // 栈存储空间初始分配量
constexpr auto STACK_INIT_SIZE = 100; // 栈存储空间初始分配量
constexpr auto STACKINCREMENT = 10;   // 栈存储空间分配增量
constexpr auto QUENE_INIT_SIZE = 100; // 队列存储空间初始分配量
constexpr auto QUENEINCREMENT = 10;   // 队列存储空间分配增量

typedef struct Node {
    int data;
    Node* Ltree;
    Node* Rtree;
}*NTree;

// 定义栈
typedef struct Stack
{
    Node* base;
    Node* top;
    int stacksize;
};

typedef struct IntStack
{
    int* base;
    int* top;
    int stacksize;
};

//定义队列
typedef struct Quene
{
    NTree arr[QUENE_INIT_SIZE];
    int length;
    int quenesize;
};

typedef struct child {
    NTree tree;
    int serial;
};
// 队列
typedef struct quene
{
    child arr[QUENE_INIT_SIZE];
    int length;
    int quenesize;

};

typedef struct Date {
	int Y, M, D;
};
typedef struct {
	//编号 书名 作者 价格 购买时间
	int id;
	string name, author, price;
	Date buyingtime;
}Book, Datatype;
typedef struct BNode {
	Datatype book;
	BNode* Ltree;
	BNode* Rtree;
}*BTree;

//声明函数
void InitStack(Stack&);
void Push(Stack&, Node*);
void Pop(Stack&, Node&);
Node getTop(Stack);
void PreOrderTraverse(NTree);  //非递归先序遍历
void InOrderTraverse(NTree);   //非递归中序遍历
void PostOrderTraverse(NTree); //非递归后序遍历
NTree Root();
void insert(NTree, int);
void Treeinput(vector<int>&);
void add(Quene);
NTree Pop(Quene);
void add(quene*&, NTree, int, int);
int Pop(quene);
quene* LevelTraversal(NTree);       //层次遍历
void Treeprint(quene*);             //二叉树打印 

class ArrayLMS {
public:
	// 功能记录项
	int lion = 99;
	int current_date;
	ArrayLMS();
	//~ArrayLMS();
	//查询操作
	Book Search();
	//插入操作
	void Insert();
	//更新操作
	int Update();
private:
	Book* A;
	Book* InitBArray();
	void gettime();
	void Bookshow(Book b);
	void Insert(Book*& a, Book n);
	void Table() {
		cout << "------------------------------------\n";
		cout << "-------简单图书管理系统（数组）-----\n";
		cout << "------------1: 图书检索-------------\n";
		cout << "------------2: 图书插入-------------\n";
		cout << "------------3: 图书修改-------------\n";
		cout << "---------------0: 退出--------------\n";
		cout << "------------------------------------\n";
	}

};

class TreeLMS {
public:
	// 功能记录项
	int lion = 99;
	int current_date;
	TreeLMS();
	//~TreeLMS();
	//查询操作
	Book Search();
	//插入操作
	void Insert();
	//更新操作
	int Update();
private:

	BTree T;
	void gettime();
	BTree InitBTree();
	void Treeinput(vector<Book>& v);
	void Bookshow(Book b);
	void Insert(BTree& t, Book n);
	void Table() {
		cout << "------------------------------------\n";
		cout << "-----简单图书管理系统（二叉树）-----\n";
		cout << "------------1: 图书检索-------------\n";
		cout << "------------2: 图书插入-------------\n";
		cout << "------------3: 图书修改-------------\n";
		cout << "---------------0: 退出--------------\n";
		cout << "------------------------------------\n";
	}
#include"标头.h"


void main() {
    //任务一 编辑生成排序二叉树
    NTree T = Root();
    vector<int> v;
    Treeinput(v);
    for (int i = 0; i < v.size(); i++) {
        insert(T, v[i]);
    }
    //任务二
    //非递归前序
    cout << "非递归前序遍历:";
    PreOrderTraverse(T);
    //非递归中序
    cout << "\n非递归中序遍历:";
    InOrderTraverse(T);
    cout << "\n非递归后序遍历:";
    //非递归后序
    PostOrderTraverse(T);

    //任务三
    //层次遍历
    cout << "\n层次遍历:";
    quene* q = LevelTraversal(T);
    //二叉树打印
    Treeprint(q);
    cout << "\n";


    //任务四.1 二叉排序树简单图书管理系统
    TreeLMS t;
    while (t.lion) {
        cout << "----------请输入功能编号----------\n";
        cin >> t.lion;
        switch (t.lion) {
        case 1:t.Search(); break;
        case 2:t.Insert(); break;
        case 3:t.Update(); break;
        case 0:cout << "-----------系统退出-----------\n"; break;
        default:printf("-----------输入错误-----------\n"); break;
        }
    }
    //任务四.2 数组简单图书管理系统
    ArrayLMS a;
    while (a.lion) {
        cout << "----------请输入功能编号----------\n";
        cin >> a.lion;
        switch (a.lion) {
        case 1:a.Search(); break;
        case 2:a.Insert(); break;
        case 3:a.Update(); break;
        case 0:cout << "-----------系统退出-----------\n"; break;
        default:printf("-----------输入错误-----------\n"); break;
        }
    }
}


NTree Root(){
	NTree t = (NTree)malloc(sizeof(Node));
	t->data = NULL;
	t->Ltree = NULL;
	t->Rtree = NULL;
	return t;
}
void insert(NTree t, int n) {

	if (t->data == NULL) {
		t->data = n;
		return;
	}
	
	NTree tmp, p;
	p = t;
	tmp = (NTree)malloc(sizeof(Node));
	tmp->data = n;
	tmp->Ltree = NULL;
	tmp->Rtree = NULL;
	while(p){
		if (p->data == n) {
			return;
		}
		if (p->data < n) {
			if (p->Rtree) { p = p->Rtree; continue; }
			else {
				p->Rtree = tmp;
				return;
			}
		}
		if (p->data > n) {
			if (p->Ltree) { p = p->Ltree; continue; }
			else {
				p->Ltree = tmp;
				return;
			}
		}
	}
}

void Treeinput(vector<int> &v) {
	int tmp = 0;
	cout << "请输入整形个数" << endl;
	int num;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cout << "请输入第" << i + 1 << "个整形元素"<<endl;
		cin >> tmp;
		v.push_back(tmp);
	}
}

//栈初始化
void InitStack(Stack& S) {
    S.base = (Node*)malloc(sizeof(Node) * STACK_INIT_SIZE);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
}
void InitStack(IntStack& S) {
    S.base = (int*)malloc(sizeof(int) * STACK_INIT_SIZE);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
}
// 入栈
void Push(Stack& S, Node* t) {
    if (S.top - S.base >= S.stacksize) {
        S.base = (Node*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(Node));

        if (!S.base) exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = *t;

}
void Push(IntStack& S, int t) {
    if (S.top - S.base >= S.stacksize) {
        S.base = (int*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(int));

        if (!S.base) exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = t;

}
//获取栈顶
Node getTop(Stack S) {
    return *(S.top - 1);
}
// 出栈
void Pop(Stack& S, Node& t) {
    if (S.top != S.base) {
        t = *(--S.top);
    }
}
int Pop(IntStack& S) {
    if (S.top != S.base) {
        return *(--S.top);
    }
}

// 非递归先序遍历
void PreOrderTraverse(Node* T) {
    if (!T) return;
    Stack S;
    InitStack(S);
    Node p;
    p = *T;
    Push(S, &p);
    while (S.top != S.base) {
        Pop(S, p);
        cout << p.data << "->";
        if (p.Rtree) {
            Push(S, p.Rtree);
        }
        if (p.Ltree) {
            Push(S, p.Ltree);
        }
    }
}

// 非递归中序遍历
void InOrderTraverse(NTree T) {
    Stack S;
    InitStack(S);
    Node c = *T;
    Node* p = &c;
    while (S.top != S.base || p) {
        if (p) {
            Push(S, p); p = p->Ltree;
        }
        else {
            Node tmp;
            Pop(S, tmp);
            p = &(tmp);
            if (p->data == '#')return;
            cout << p->data << "->";
            p = p->Rtree;
        }
    }
}
// 非递归后序遍历
void PostOrderTraverse(NTree T) {
    if (T == NULL) return;
    // 结点栈
    Stack S;
    // 状态栈
    IntStack O;
    InitStack(S);
    InitStack(O);
    Node tmp = *T;
    Node* p = &tmp;
    //状态变量
    int tag = 0;
    Push(S, p);
    Push(O, 0);
    p = p->Ltree;

    while (S.top != S.base) {
        if (p) {

            Push(S, p);
            Push(O, 0);
            p = p->Ltree;
        }
        else {
            tag = Pop(O);
            if (!tag) {
                Push(O, 1);
                tmp = getTop(S);
                p = &tmp;
                p = p->Rtree;
            }
            else {
                tmp = getTop(S);
                cout << tmp.data << "->";
                Pop(S, tmp);
            }
        }
    }
}
void add(Quene* &q,NTree t){
    if (q->length >= q->quenesize) {
        q = (Quene*)realloc(q, q->quenesize + QUENEINCREMENT * sizeof(Quene));
        q->quenesize += QUENEINCREMENT;
    }
    q->arr[q->length++] = t;
}

void add(quene*& q, NTree t, int n, int order) {
    /// <param name="q"></队列>
    /// <param name="t"></树>
    /// <param name="n"></类型>
    /// <param name="order"></父节点序号>
    if (q->length >= q->quenesize) {
        q = (quene*)realloc(q, q->quenesize + QUENEINCREMENT * sizeof(quene));
        q->quenesize += QUENEINCREMENT;
    }
    q->arr[q->length].tree = t;
    //add左孩子
    if (n == 0) {
        q->arr[q->length].serial = 2 * order + 1;
    }
    //add右孩子
    if (n == 1) {
        q->arr[q->length].serial = 2 * order + 2;
    }
    q->length++;
}
NTree Pop(Quene* &q) {
    NTree tmp = q->arr[0];
    for (int i = 0; i < q->length;i++) {
        q->arr[i] = q->arr[i + 1];
    }
    q->length--;
    return tmp;
}
NTree Search(quene*& q, int n) {
    NTree tmp = q->arr[n].tree;
    return tmp;
}
int Order(quene*& q, int n) {
    return q->arr[n].serial;
}
quene* LevelTraversal(NTree t) {
    //层次遍历二叉树，返回二叉树的队列形式
    //
    Quene* q = (Quene*)malloc(sizeof(Quene) * QUENE_INIT_SIZE);
    quene* r = (quene*)malloc(sizeof(quene) * QUENE_INIT_SIZE);

    NTree tmp;
    int n = 0;
    int order;

    q->length = 0;
    q->quenesize = QUENE_INIT_SIZE;
    
    r->length = 0;
    r->quenesize = QUENE_INIT_SIZE;


    add(q, t);
    //r->arr[0] = (child*)malloc(quene)
    r->arr[0].tree = t;
    r->arr[0].serial = 0;
    r->length++;

    while (q->length != 0) {
        tmp = Pop(q);
        order = Order(r, n);
        n++;
        if (tmp->Ltree) { add(q, tmp->Ltree); add(r, tmp->Ltree, 0, order); }
        if (tmp->Rtree) { add(q, tmp->Rtree); add(r, tmp->Rtree, 1, order); }

        cout << tmp->data << "->";
    }
    cout << endl;
    return r;
}

void Treeprint(quene* q) 
{
    //第i-1行的最左侧空格数为2 ** (layers - i) - 1 行内元素空格数为 2 * （layers + 1 - i) -1   
    int length = q->length;
    int layers = floor(log(q->arr[length - 1].serial + 1) / log(2));
    //换行标识 打印最左侧空格数标识
    int mark = 1;
    for (int i = 0; i < length; i++)
    {
        // 每一层最左侧结点 2**i -1
        // 换行判断
        if (floor(log(q->arr[i].serial + 1) / log(2)) != floor(log(q->arr[i - 1].serial + 1) / log(2)) && i != 0) {
            cout << endl;
            mark = 1;
        } 
        float row = log(q->arr[i].serial + 1) / log(2);
        if (int(row) == row) {
            for (int j = 0; j < pow(2, (layers - int(row))) - 1; j++) {
                cout << " ";
            }
            cout << Search(q, i)->data;
            mark = 0;
            continue;
        }

        else 
        {
            if (mark)
            {
                for (int j = 0; j < pow(2, (layers - int(row) + 1)) * (q->arr[i].serial - pow(2, (int)row - 1)) + pow(2, (layers - int(row))) - 1; j++)
                {
                    cout << " ";
                }
                    // 每一层最右侧结点 2**i -2 
                    cout << Search(q, i)->data;
                    mark = 0;
                
            }
            else
            {
                for (int j = 0; j < pow(2, (layers - int(row) + 1)) * (q->arr[i].serial - q->arr[i - 1].serial) - 1; j++)
                {
                    cout << " ";
                }
                // 每一层最右侧结点 2**i -2 
                cout << Search(q, i)->data;

            }
        }
    }
}
#include"标头.h"





BTree TreeLMS::InitBTree() {
	//BTree t = (BTree)malloc(sizeof(BNode)); 错误 由于string不定长 使用malloc不能动态分配内存
	BTree t = new BNode;
	t->book.id = NULL;
	t->Ltree = t->Rtree = NULL;
	return t;
}
TreeLMS::TreeLMS() {
	T = InitBTree();
	vector<Book> v;
	Book tmp1, tmp2, tmp3;
	tmp1.id = 50; tmp1.name = "时间简史"; tmp1.author = "霍金"; tmp1.price = 55; tmp1.buyingtime.Y = 2019; tmp1.buyingtime.M = 9; tmp1.buyingtime.D = 1;
	tmp2.id = 29; tmp2.name = "机器学习"; tmp2.author = "周志华"; tmp2.price = 77; tmp2.buyingtime.Y = 2018; tmp2.buyingtime.M =8; tmp2.buyingtime.D = 4;
	tmp3.id = 31; tmp3.name = "数学模型"; tmp3.author = "姜启源"; tmp3.price = 90; tmp3.buyingtime.Y = 2017; tmp3.buyingtime.M = 5; tmp3.buyingtime.D = 17;

	Insert(T, tmp1);
	Insert(T, tmp2);
	Insert(T, tmp3);

	Table();
}
void TreeLMS::Treeinput(vector<Book>& v) {
	Book tmp;
	cout << "请输入录入书籍数" << endl;
	int num;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cout << "请输入第" << i + 1 << "本书的编号 书名 作者 价格 购买时间" << endl;
		cin >> tmp.id>> tmp.name>> tmp.author>> tmp.price >> tmp.buyingtime.Y>> tmp.buyingtime.M>> tmp.buyingtime.D;
		v.push_back(tmp);
	}
}
void TreeLMS::Insert(BTree &t, Book n) {

	if (!t->book.id) {
		t->book = n;
		return;
	}

	BTree tmp, p;
	p = t;
	tmp = new BNode;
	tmp->book = n;
	tmp->Ltree = NULL;
	tmp->Rtree = NULL;
	while (p) {
		if (p->book.id == n.id) {
			return;
		}
		if (p->book.id < n.id) {
			if (p->Rtree) { p = p->Rtree; continue; }
			else {
				p->Rtree = tmp;
				return;
			}
		}
		if (p->book.id > n.id) {
			if (p->Ltree) { p = p->Ltree; continue; }
			else {
				p->Ltree = tmp;
				return;
			}
		}
	}
}

void TreeLMS::Insert() {
	Book n; 
	cout << "----------请输入录入书籍的编号 书名 作者 价格 购买时间----------" << endl;
	cin >> n.id >> n.name >> n.author >> n.price >> n.buyingtime.Y >> n.buyingtime.M >> n.buyingtime.D;

	if (T->book.id) {
		T->book = n;
		return;
	}

	BTree tmp, p;
	p = T;
	tmp = (BTree)malloc(sizeof(BNode));
	tmp->book = n;
	tmp->Ltree = NULL;
	tmp->Rtree = NULL;
	while (p) {
		if (p->book.id == n.id) {
			return;
		}
		if (p->book.id < n.id) {
			if (p->Rtree) { p = p->Rtree; continue; }
			else {
				p->Rtree = tmp;
				return;
			}
		}
		if (p->book.id > n.id) {
			if (p->Ltree) { p = p->Ltree; continue; }
			else {
				p->Ltree = tmp;
				return;
			}
		}
	}
}
Book TreeLMS::Search() {
	cout << "--------请输入检索书籍的ID--------" << endl;
	int id;
	cin >> id;
	BTree t = T;
	if (!t->book.id) {
		cout << "-----------图书库为空-----------" << endl;
		return t->book;
	}
	while (t) {
		if (t->book.id < id) {
			t = t->Rtree;
			continue;
		}
		if (t->book.id > id) {
			t = t->Ltree;
			continue;
		}
		if (t->book.id == id) {
			Bookshow(t->book);
			return t->book;
		}
	}
	cout << "-----------图书库无收录-----------" << endl;
	return t->book;
}
int TreeLMS::Update() {
	cout << "--------请输入更新书籍的ID--------" << endl;
	int id;
	cin >> id;
	BTree t = T;
	if (!t->book.id) {
		cout << "-----------图书库为空-----------" << endl;
		return 0;
	}
	while (t) {
		if (t->book.id < id) {
			t = t->Rtree;
			continue;
		}
		if (t->book.id > id) {
			t = t->Ltree;
			continue;
		}
		if (t->book.id == id) {
			Bookshow(t->book);
			int c = 99;
			while(c){
			cout << "--------请输入更新书籍的信息类别--------" << endl;
			cout << "--------编号:1 书名:2 作者:3 价格:4 购买时间:5--------" << endl;
			cout << "-------------结束请输入:0---------------" << endl;
			cin >> c;
			switch (c)
			{
			case 1: cout << "--------请输入更新书籍的编号--------" << endl; cin >> t->book.id; break;
			case 2: cout << "--------请输入更新书籍的书名--------" << endl; cin >> t->book.name; break;
			case 3: cout << "--------请输入更新书籍的作者--------" << endl; cin >> t->book.author; break;
			case 4: cout << "--------请输入更新书籍的价格--------" << endl; cin >> t->book.price; break;
			case 5: cout << "------请输入更新书籍的购买时间------" << endl; cin >> t->book.buyingtime.Y >> t->book.buyingtime.M >> t->book.buyingtime.D; break;
			default: cout << "----------------结束----------------" << endl; break;
			}
			}
			
			return 1;
		}
	}
	cout << "-----------图书库无此书-----------" << endl;
	return 0;
}
void TreeLMS::Bookshow(Book b) {
	cout << "ID: " << b.id << " ,书名:" << b.name << " ,作者:" << b.author << " ,作者:" << b.author << " ,购买时间:" << b.buyingtime.Y << "-" << b.buyingtime.M << "-" << b.buyingtime.D << endl;
}


ArrayLMS::ArrayLMS()
{
	A = InitBArray();
	Book tmp1, tmp2, tmp3;
	tmp1.id = 50; tmp1.name = "时间简史"; tmp1.author = "霍金"; tmp1.price = 55; tmp1.buyingtime.Y = 2019; tmp1.buyingtime.M = 9; tmp1.buyingtime.D = 1;
	tmp2.id = 29; tmp2.name = "机器学习"; tmp2.author = "周志华"; tmp2.price = 77; tmp2.buyingtime.Y = 2018; tmp2.buyingtime.M = 8; tmp2.buyingtime.D = 4;
	tmp3.id = 31; tmp3.name = "数学模型"; tmp3.author = "姜启源"; tmp3.price = 90; tmp3.buyingtime.Y = 2017; tmp3.buyingtime.M = 5; tmp3.buyingtime.D = 17;
	Insert(A, tmp1);
	Insert(A, tmp2);
	Insert(A, tmp3);

	Table();
}
Book ArrayLMS::Search()
{
	cout << "--------请输入检索书籍的ID--------" << endl;
	int id;
	cin >> id;
	if (!A[0].id) {
		cout << "-----------图书库为空-----------" << endl;
		return A[0];
	}
	for (int i = 0; i < ARRAY_INIT_SIZE; i++) {
		if (A[i].id == id) {
			Bookshow(A[i]);
			return A[i];
		}
	}
	cout << "-----------图书库无收录-----------" << endl;
	return A[99];
}
Book* ArrayLMS::InitBArray()
{
	Book* a = new Book[ARRAY_INIT_SIZE];
	for (int i = 0; i < ARRAY_INIT_SIZE; i++) {
		a[i].id = 0;
	
	}
	return a;
}
void ArrayLMS::Insert(Book*& a, Book n)
{
	for (int i = 0; i < ARRAY_INIT_SIZE; i++) {
		if (!a[i].id) {
			a[i] = n;
			break;
		}
	}
}
void ArrayLMS::Insert() {
	Book n;
	cout << "----------请输入录入书籍的编号 书名 作者 价格 购买时间----------" << endl;
	cin >> n.id >> n.name >> n.author >> n.price >> n.buyingtime.Y >> n.buyingtime.M >> n.buyingtime.D;
	for (int i = 0; i < ARRAY_INIT_SIZE; i++) {
		if (!A[i].id) {
			A[i] = n;
			break;
		}
	}
}
int ArrayLMS::Update()
{
	cout << "--------请输入更新书籍的ID--------" << endl;
	int id;
	cin >> id;
	for (int i = 0; i < ARRAY_INIT_SIZE; i++) {
		if (A[i].id == id) {
			Bookshow(A[i]);
			int c = 99;
			while (c) {
				cout << "--------请输入更新书籍的信息类别--------" << endl;
				cout << "--------编号:1 书名:2 作者:3 价格:4 购买时间:5--------" << endl;
				cout << "-------------结束请输入:0---------------" << endl;
				cin >> c;
				switch (c)
				{
				case 1: cout << "--------请输入更新书籍的编号--------" << endl; cin >> A[i].id; break;
				case 2: cout << "--------请输入更新书籍的书名--------" << endl; cin >> A[i].name; break;
				case 3: cout << "--------请输入更新书籍的作者--------" << endl; cin >> A[i].author; break;
				case 4: cout << "--------请输入更新书籍的价格--------" << endl; cin >> A[i].price; break;
				case 5: cout << "------请输入更新书籍的购买时间------" << endl; cin >> A[i].buyingtime.Y >> A[i].buyingtime.M >> A[i].buyingtime.D; break;
				default: cout << "----------------结束----------------" << endl; break;
				}
			}
		}
	}
	return 1;
}
void ArrayLMS::Bookshow(Book b) {
	cout << "ID: " << b.id << " ,书名:" << b.name << " ,作者:" << b.author << " ,作者:" << b.author << " ,购买时间:" << b.buyingtime.Y << "-" << b.buyingtime.M << "-" << b.buyingtime.D << endl;
}



};