//
// Created by ubuntu on 22-12-6.
//
#include <iostream>
#include <cctype>
#include "bs_tree.h"


using namespace std;

//--------------Stack--------------//
typedef struct LinkNode {
    BiTNode *data;
    struct LinkNode *next;
} *LiStack, LinkNode;

bool InitStack(LiStack &S);

bool StackEmpty(LiStack S);

bool Push(LiStack &S, BiTNode *x);

bool Pop(LiStack &S, BiTNode *&x);

bool GetTop(LiStack S, BiTNode *&x);

bool DestoryStack(LiStack &S);

bool InitStack(LiStack &S) {
    S = (LiStack) malloc(sizeof(LinkNode));
    if (S == nullptr) return false;
    S->next = nullptr;
    return true;
}

bool StackEmpty(LiStack S) {
    if (S->next == nullptr) return true;
    return false;
}

bool Push(LiStack &S, BiTNode *x) {
    LinkNode *p;
    p = (LinkNode *) malloc(sizeof(LinkNode));
    if (p == nullptr) return false;
    p->data = x;
    p->next = S->next;
    S->next = p;
    return true;
}

bool Pop(LiStack &S, BiTNode *&x) {
    if (StackEmpty(S)) return false;
    LinkNode *p = S->next;
    S->next = p->next;
    x = p->data;
    free(p);
    return true;
}

bool GetTop(LiStack S, BiTNode *&x) {
    if (StackEmpty(S)) return false;
    x = S->next->data;
    return true;
}

//--------------Queue--------------//
typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

void InitQueue(LinkQueue &Q);

bool QueueEmpty(LinkQueue Q);

bool EnQueue(LinkQueue &Q, BiTNode *x);

bool DeQueue(LinkQueue &Q, BiTNode *&x);

void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));
    Q.front->next = nullptr;
}

bool QueueEmpty(LinkQueue Q) {
    if (Q.front == Q.rear) return true;
    return false;
}

bool EnQueue(LinkQueue &Q, BiTNode *x) {
    auto *s = (LinkNode *) malloc(sizeof(LinkNode));
    s->data = x;
    s->next = Q.rear->next;
    Q.rear->next = s;
    Q.rear = s;
    return true;
}

bool DeQueue(LinkQueue &Q, BiTNode *&x) {
    if (QueueEmpty(Q)) return false;
    LinkNode *q = Q.front->next;
    x = q->data;
    Q.front->next = q->next;
    if (Q.rear == q) {
        Q.rear = Q.front;
    }
    free(q);
    return true;
}

//--------------Binary Tree--------------//

bool InitBiTree(BiTree &T) {
    ElemType data;
    cout<<"请输入数据(int)，任意非数字字符结束"<<endl;
    while(cin>>data){
        Insert(T,data);
        cin.clear(); //flush the flag
        cin.ignore(); //clear the buffer
    }
    return true;
}

void visit(BiTNode *p) {
    cout << p->data << " ";
}

//先序遍历（递归）
void PreOrder_Rec(BiTree T) {
    if (T == nullptr) return;
    visit(T);
    PreOrder_Rec(T->lchild);
    PreOrder_Rec(T->rchild);
}

//中序遍历（递归）
void InOrder_Rec(BiTree T) {
    if (T == nullptr) return;
    InOrder_Rec(T->lchild);
    visit(T);
    InOrder_Rec(T->rchild);
}

//后序遍历（递归）
void PostOrder_Rec(BiTree T) {
    if (T == nullptr) return;
    PostOrder_Rec(T->lchild);
    PostOrder_Rec(T->rchild);
    visit(T);
}

//先序遍历
void PostOrder(BiTree T) {
    LiStack S;
    InitStack(S);
    BiTree p = T;
    BiTNode *r = nullptr;   //辅助指针，指向最近访问的节点
    while (p || !StackEmpty(S)) {
        if (p) {                              //走到最左边
            Push(S, p);
            p = p->lchild;
        } else {                              //走到最右边
            GetTop(S, p);                    //读栈顶元素（非出栈）
            if (p->rchild && p->rchild != r) {    //若右子树存在且未被访问过
                p = p->rchild;              //转向右
                Push(S, p);                  //压入栈
                p = p->lchild;              //再走到最左
            } else {                          //否则弹出栈顶元素并访问
                Pop(S, p);
                visit(p);
                r = p;                      //记录最近访问过的节点
                p = nullptr;                   //节点访问完后重置p指针
            }
        }
    }
}

//中序遍历
void InOrder(BiTree T) {
    LiStack S;
    InitStack(S);
    BiTree p = T;               //遍历指针
    while (p || !StackEmpty(S)) {   //
        if (p) {                  //一路向左
            Push(S, p);          //当前节点入栈
            p = p->lchild;      //左孩子不为空一直向左走
        } else {                  //出栈，并转向该节点的右孩子
            Pop(S, p);           //栈顶结点出栈，访问
            visit(p);
            p = p->rchild;      //向右子树走，
        }
    }
}

//后序遍历
void PreOrder(BiTree T) {
    LiStack S;
    InitStack(S);
    BiTree p = T;               //遍历指针
    while (p || !StackEmpty(S)) {   //
        if (p) {                  //一路向左
            visit(p);
            Push(S, p);          //当前节点入栈
            p = p->lchild;      //左孩子不为空一直向左走
        } else {                  //出栈，并转向该节点的右孩子
            Pop(S, p);           //栈顶结点出栈
            p = p->rchild;      //向右子树走，
        }
    }
}

//层序遍历
void LevelOrder(BiTree T) {
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);
    while (!QueueEmpty(Q)) {
        DeQueue(Q, p);
        visit(p);
        if (p->lchild != nullptr) {
            EnQueue(Q, p->lchild);
        }
        if (p->rchild != nullptr) {
            EnQueue(Q, p->rchild);
        }
    }
}

//--------------Binary Search Tree--------------//
//BST Search
BiTNode *Search(BiTNode *root, const ElemType &data) {
    while (root) {
        if (root->data == data)break;
        else if (root->data > data)root = root->lchild;
        else root = root->rchild;
    }
    return root;
}

//BST Insert
bool Insert(BiTNode *&root, const ElemType &data) {
    if (root == nullptr) {
        root = new BiTNode(data);
        return true;
    }

    auto p = root;
    while (p) {
        if (p->data > data) {
            if (p->lchild)p = p->lchild;
            else {
                p->lchild = new BiTNode(data);
                break;
            }
        } else if (p->data < data) {
            if (p->rchild)p = p->rchild;
            else {
                p->rchild = new BiTNode(data);
                break;
            }
        } else return false;
    }
    return true;
}

//BST Remove

bool Remove(BiTNode *&root, const ElemType &data) {
    //Find node
    BiTNode **p = &root;
    while ((*p) && (*p)->data != data) {
        if ((*p)->data > data)p = &(*p)->lchild;
        else p = &(*p)->rchild;
    }
    if (!(*p))return false;

    //Delete node
    BiTNode **_p = &(*p)->rchild;//(*p)->data should be the min of right... or the max of left.
    if (!(*_p)) {//no right
        (*p) = (*p)->lchild;
    } else if ((*_p)->lchild) {// right->left->...->left is min of right and is greater than left...
        while ((*_p)->lchild)_p = &(*_p)->lchild;
        (*p)->data = (*_p)->data;//swap data
        (*_p) = (*_p)->rchild;//delete the min node
    } else {// (*p)->right->data is the min of right
        (*_p)->lchild = (*p)->lchild;
        (*p) = (*p)->rchild;
    }
    return true;
}


void test() {
    BiTree T= nullptr;
    InitBiTree(T);

    const char h[]="[d(D) x]:删除x；\n[i(I) x]:插入x；\n[s(S) x]:查找x；\n[o(O) x]:0-中序遍历(default)，1-先序遍历，2-后序遍历，3-层序遍历；";
    cout << h << endl;
    char cmd;
    int val=1;
    cin.clear(); //flush the flag
    cin.ignore(); //clear the buffer
    while(cin>>cmd>>val) {
        cin.clear();
        cmd= (char)tolower(cmd);
        switch (cmd) {
            case 'd':{
                Remove(T, val);
                InOrder(T);
                cout << endl;
            }break;
            case 'i':{
                Insert(T, val);
                InOrder(T);
                cout << endl;
            }break;
            case 's':{
                if (Search(T, val))cout << "ture" << endl;
                else cout << "false" << endl;
            }break;
            case 'o':{
                switch (val) {
                    case 1:{
                        cout << "先序遍历: ";
                        PreOrder(T);
                        cout << endl;
                    }break;
                    case 2:{
                        cout << "后序遍历: ";
                        PostOrder(T);
                        cout << endl;
                    }break;
                    case 3:{
                        cout << "层序遍历: ";
                        LevelOrder(T);
                        cout << endl;
                    }break;
                    default:{
                        cout << "中序遍历: ";
                        InOrder(T);
                        cout << endl;
                    }break;
                }
            }break;
            default:
                return;
        }
        cin.clear(); //flush the flag
        cin.ignore(); //clear the buffer
    }
    cout << endl;
}

int main() {

    test();
    return 0;
}