#ifndef BITREE_H
#define BITREE_H
#include <iostream>
#include <queue>
using namespace std;
#include "LinkedStack.h"
#include "SeqQueue.h"
#include "SeqStack.h"
#include <assert.h>
#include <stdlib.h>
template <class T>
struct BinTreeNode
{
    T data;
    BinTreeNode<T> *leftChild, *rightChild;
    BinTreeNode() : leftChild(NULL), rightChild(NULL) {}
    BinTreeNode(T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) : data(x), leftChild(l), rightChild(r) {}
};

template <class T>
class BinaryTree
{
public:
    BinaryTree() : root(NULL) {}
    BinaryTree(T value) : RefValue(value), root(new BinTreeNode<T>(value)) {}
    BinaryTree(BinaryTree<T> &s);
    ~BinaryTree()
    {
        destroy();
    }
    bool IsEmpty() { return (root == NULL) ? true : false; }
    BinTreeNode<T> *Parent(BinTreeNode<T> *current)
    {
        return (root == NULL || root == current) ? NULL : Parent(root, current);
    }
    BinTreeNode<T> *LeftChild(BinTreeNode<T> *current)
    {
        return (current != NULL) ? current->leftChild : NULL;
    }
    BinTreeNode<T> *RightChild(BinTreeNode<T> *current)
    {
        return (current != NULL) ? current->rightChild : NULL;
    }
    void destroy()
    {
        destroy(root);
    }
    int Height() { return Height(root); }
    int Size() { return Size(root); }
    BinTreeNode<T> *getRoot() const { return root; }
    void setRoot(BinTreeNode<T> *p) { root = p; }
    void preOrder(void (*visit)(BinTreeNode<T> *p))
    {
        preOrder(root, visit);
    }
    void inOrder(void (*visit)(BinTreeNode<T> *p))
    {
        inOrder(root, visit);
    }
    void postOrder(void (*visit)(BinTreeNode<T> *p))
    {
        postOrder(root, visit);
    }
    void NonR_preOrder(void (*visit)(BinTreeNode<T> *p));  //非递归前序遍历
    void NonR_preOrder1(void (*visit)(BinTreeNode<T> *p)); //非递归前序遍历
    void NonR_inOrder(void (*visit)(BinTreeNode<T> *p));   //非递归中序遍历
    void NonR_postOrder(void (*visit)(BinTreeNode<T> *p)); //非递归后续遍历
    void levelOrder(void (*visit)(BinTreeNode<T> *p));
    BinTreeNode<T> *Insert(BinTreeNode<T> *curr, const T &x, int d); //作业：实现在curr结点左/右插入子女结点x
    BinTreeNode<T> *Find(T item) const                               //作业：递归算法实现查找item
    {
        return Find(root, item);
    }
    int NonR_Height(); //作业：使用非递归方法求树高度
    bool IsBalanced()  //作业：递归算法判断二叉树是否为平衡二叉树
    {
        int height;
        return IsBalanced(root, height);
    }

protected:
    BinTreeNode<T> *root;
    T RefValue;
    void CreateBinTree(istream &in, BinTreeNode<T> *&subTree);
    void destroy(BinTreeNode<T> *&subTree);
    BinTreeNode<T> *Copy(BinTreeNode<T> *orignode);
    int Height(BinTreeNode<T> *subTree) const;
    int Size(BinTreeNode<T> *subTree) const;
    BinTreeNode<T> *Parent(BinTreeNode<T> *subTree, BinTreeNode<T> *current);
    BinTreeNode<T> *Find(BinTreeNode<T> *subTree, const T &x) const; //作业：使用递归方法实现查找

    void Traverse(BinTreeNode<T> *subTree, ostream &out);
    void preOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *p));
    void inOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *p));
    void postOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *p));

    bool IsBalanced(BinTreeNode<T> *subTree, int &height);
    friend istream &operator>>(istream &in, BinaryTree<T> &Tree)
    {
        Tree.CreateBinTree(in, Tree.root);
        return in;
    };
    friend ostream &operator<<(ostream &out, BinaryTree<T> &Tree)
    {
        //输出二叉树
        Tree.Traverse(Tree.root, out);
        out << endl;
        return out;
    };
    friend int operator==(const BinaryTree<T> &s, const BinaryTree<T> &t)
    {
        return equal(s.root, t.root) ? true : false;
    };
    //public:
    //void MakeTree(const T item,BinaryTree<T> &left,BinaryTree<T>& right);
    //void PrintBTree(BinTreeNode<T> *BT,int level);
};

template <class T>
BinTreeNode<T> *BinaryTree<T>::Insert(BinTreeNode<T> *curr, const T &x, int d)
{ /*在二叉树的curr结点左/右插入新子女结点x，原来的子女节点作为新结点的子女结点。d=0，左插入；d不等于0，右插入。插入成功返回新子女结点的地址。*/
    //在这里添加你的程序替换下面的语句，完成任务1，实现在curr结点左/右插入子女结点x。
    auto node = new BinTreeNode<T>(x);
    node->leftChild = curr->leftChild;
    node->rightChild = curr->rightChild;
    if (d == 0)
        curr->leftChild = node, curr->rightChild = nullptr;
    else
        curr->leftChild = nullptr, curr->rightChild = node;
    return node;
}

template <class T>
BinTreeNode<T> *BinaryTree<T>::Find(BinTreeNode<T> *subtree, const T &x) const
{ //私有函数：在以subtree为根的二叉树中查找x，查找成功，返回结点地址，否则返回0。
    //在这里添加你的程序替换下面的语句，完成任务2，实现在以subtree为根的二叉树中递归搜索结点x。
    if (subtree == nullptr) return nullptr;
    if (x == subtree->data) return subtree;
    if (x < subtree->data) return Find(subtree->leftChild, x);
    if (x > subtree->data) return Find(subtree->rightChild, x);
    return NULL;
}

template <class T>
void BinaryTree<T>::destroy(BinTreeNode<T> *&subTree)
{ //		私有函数，若指针subTree不为空，则删除根为subTree的子树
    if (subTree != NULL)
    {
        destroy(subTree->leftChild);
        destroy(subTree->rightChild);
        delete subTree;
        subTree = NULL;
    }
}

template <class T>
BinTreeNode<T> *BinaryTree<T>::Parent(BinTreeNode<T> *subTree, BinTreeNode<T> *current)
{ //		私有函数，从结点subTree开始，搜索结点current的父节点，若找到结点current的父节点，则函数返回父结点地址，否则返回NULL
    if (subTree == NULL) return NULL;
    if (subTree->leftChild == current || subTree->rightChild == current)
        return subTree;
    BinTreeNode<T> *p = Parent(subTree->leftChild, current);
    if (p != NULL)
        return p;
    else
        return Parent(subTree->rightChild, current);
}
template <class T>
void BinaryTree<T>::Traverse(BinTreeNode<T> *subTree, ostream &out)
{
    if (subTree != NULL)
    {
        out << subTree->data << " ";
        Traverse(subTree->leftChild, out);
        Traverse(subTree->rightChild, out);
    }
}

template <class T>
void BinaryTree<T>::inOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *p))
{
    if (subTree != NULL)
    {
        inOrder(subTree->leftChild, visit);
        visit(subTree);
        inOrder(subTree->rightChild, visit);
    }
}
template <class T>
void BinaryTree<T>::preOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *p))
{
    if (subTree != NULL)
    {
        visit(subTree);
        preOrder(subTree->leftChild, visit);
        preOrder(subTree->rightChild, visit);
    }
}
template <class T>
void BinaryTree<T>::postOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *p))
{
    if (subTree != NULL)
    {
        postOrder(subTree->leftChild, visit);
        postOrder(subTree->rightChild, visit);
        visit(subTree);
    }
}
template <class T>
int BinaryTree<T>::Size(BinTreeNode<T> *subTree) const
{
    if (subTree == NULL)
        return 0;
    else
        return 1 + Size(subTree->leftChild) + Size(subTree->rightChild);
}
template <class T>
int BinaryTree<T>::Height(BinTreeNode<T> *subTree) const
{
    if (subTree == NULL)
        return 0;
    else
    {
        int i = Height(subTree->leftChild);
        int j = Height(subTree->rightChild);
        return (i < j) ? j + 1 : i + 1;
    }
}
template <class T>
BinaryTree<T>::BinaryTree(BinaryTree<T> &s)
{
    root = Copy(s.getRoot());
    RefValue = s.RefValue;
}
template <class T>
BinTreeNode<T> *BinaryTree<T>::Copy(BinTreeNode<T> *orignode)
{
    if (orignode == NULL) return NULL;
    BinTreeNode<T> *temp = new BinTreeNode<T>;
    temp->data = orignode->data;
    temp->leftChild = Copy(orignode->leftChild);
    temp->rightChild = Copy(orignode->rightChild);
    return temp;
}
template <class T>
void BinaryTree<T>::CreateBinTree(istream &in, BinTreeNode<T> *&subTree)
{
    T item;
    if (!in.eof())
    {
        in >> item;
        if (item != RefValue)
        {
            subTree = new BinTreeNode<T>(item);
            if (subTree == NULL)
            {
                cerr << "存储分配出错！" << endl;
                exit(1);
            }
            CreateBinTree(in, subTree->leftChild);
            CreateBinTree(in, subTree->rightChild);
        }
        else
            subTree = NULL;
    }
}

template <class T>
int BinaryTree<T>::NonR_Height()
{
    //在这里添加你的程序替换下列语句，完成任务4，使用非递归方法求二叉树的高度。空树高度为0.
    queue<pair<BinTreeNode<T> *, int>> Q;
    int ans = 0;
    for (Q.push(make_pair(this->root, this->root != nullptr)); !Q.empty(); Q.pop())
    {
        auto cur = Q.front();
        ans = max(ans, cur.second);
        if (cur.first->leftChild) Q.push(make_pair(cur.first->leftChild, cur.second + 1));
        if (cur.first->rightChild) Q.push(make_pair(cur.first->rightChild, cur.second + 1));
    }
    return ans;
}
template <class T>
bool BinaryTree<T>::IsBalanced(BinTreeNode<T> *subTree, int &height)
{ //如果每个结点的左子树和右子树的高度差的绝对值都小于2，则二叉树是平衡的。subTree二叉树如果是平衡的则返回true，否则返回false。
    //subTree二叉树的高度通过形参height返回。
    //在这里添加你的程序替换下面的语句，完成任务3，编写递归算法实现判断二叉树是否为平衡二叉树。
    if (subTree == nullptr) return height = 0, true;
    int hl = 0, hr = 0;
    bool flag = true;
    if (flag) flag = flag && IsBalanced(subTree->leftChild, hl);
    if (flag) flag = flag && IsBalanced(subTree->rightChild, hr);
    if (flag) flag = flag && abs(hr - hl) < 2;
    return flag;
}

template <class T>
void BinaryTree<T>::NonR_preOrder(void (*visit)(BinTreeNode<T> *p)) //非递归前序遍历
{
    SeqStack<BinTreeNode<T> *> S;
    BinTreeNode<T> *p;
    S.Push(root);
    while (!S.IsEmpty())
    {
        S.Pop(p);
        visit(p);
        if (p->rightChild != NULL)
            S.Push(p->rightChild);
        if (p->leftChild != NULL)
            S.Push(p->leftChild);
    }
}

template <class T>
void BinaryTree<T>::NonR_preOrder1(void (*visit)(BinTreeNode<T> *p)) //非递归前序遍历
{
    SeqStack<BinTreeNode<T> *> S;
    BinTreeNode<T> *p = root;
    S.Push(NULL);
    while (p != NULL)
    {
        visit(p);
        if (p->rightChild != NULL)
            S.Push(p->rightChild);
        if (p->leftChild != NULL)
            p = p->leftChild;
        else
            S.Pop(p);
    }
}

template <class T>
void BinaryTree<T>::NonR_inOrder(void (*visit)(BinTreeNode<T> *p)) //非递归中序遍历
{
    SeqStack<BinTreeNode<T> *> S;
    BinTreeNode<T> *p = root;
    do
    {
        while (p != NULL)
        {
            S.Push(p);
            p = p->leftChild;
        }
        if (!S.IsEmpty())
        {
            S.Pop(p);
            visit(p);
            p = p->rightChild;
        }
    } while (p != NULL || !S.IsEmpty());
}

template <typename T>
struct stkNode
{
    BinTreeNode<T> *ptr; //树结点指针
    enum
    {
        L,
        R
    } tag; //退栈标记，必须说明为枚举变量，tag移到最右边。这里最好用bool量
    stkNode(BinTreeNode<T> *N = NULL)
    {
        ptr = N;
        tag = L;
    } //构造函数
};

template <class T>
void BinaryTree<T>::NonR_postOrder(void (*visit)(BinTreeNode<T> *p)) //非递归后序遍历
{
    LinkedStack<stkNode<T>> S;
    stkNode<T> w;
    BinTreeNode<T> *p = root; //p是遍历指针
    do
    {
        while (p != NULL)
        {
            w.ptr = p;
            w.tag = stkNode<T>::L; //枚举类型定义在struct stkNode中，如定义为全局性就简单了
            S.Push(w);
            p = p->leftChild;
        }
        int continue1 = 1; //继续循环标记, 用于R
        while (continue1 && !S.IsEmpty())
        {
            S.Pop(w);
            p = w.ptr;
            switch (w.tag)
            { //判断栈顶的tag标记
            case stkNode<T>::L:
                w.tag = stkNode<T>::R;
                S.Push(w);
                continue1 = 0;
                p = p->rightChild;
                break;
            case stkNode<T>::R: visit(p); break;
            }
        }
    } while (!S.IsEmpty()); //继续遍历其他结点
    cout << endl;
}

template <class T>
void BinaryTree<T>::levelOrder(void (*visit)(BinTreeNode<T> *p)) //非递归层序遍历
{
    SeqQueue<BinTreeNode<T> *> Q;
    BinTreeNode<T> *p = root;
    Q.EnQueue(p);
    while (!Q.IsEmpty())
    {
        Q.DeQueue(p);
        visit(p);
        if (p->leftChild != NULL)
            Q.EnQueue(p->leftChild);
        if (p->rightChild != NULL)
            Q.EnQueue(p->rightChild);
    }
}

template <class T>
bool equal(BinTreeNode<T> *a, BinTreeNode<T> *b)
{
    if (a == NULL && b == NULL)
        return true;
    if (a != NULL && b != NULL && a->data == b->data && equal(a->leftChild, b->leftChild) && equal(a->rightChild, b->rightChild))
    {
        //cout << a->data << endl;cout << b->data << endl;
        return true;
    }
    else
    {
        return false;
    }
}

template <class T>
void PrintBTree(BinTreeNode<T> *BT)
{ //以广义表形式输出二叉树
    if (BT != NULL)
    {
        cout << BT->data;
        if (BT->leftChild != NULL || BT->rightChild != NULL)
        {
            cout << '(';
            PrintBTree(BT->leftChild);
            cout << ',';
            if (BT->rightChild != NULL)
                PrintBTree(BT->rightChild);
            cout << ')';
        }
        else if (BT->leftChild == NULL && BT->rightChild == NULL)
        {
            cout << '(';
            cout << ',';
            cout << ')';
        }
    }
}

template <class T>
void PrintBTree(BinTreeNode<T> *BT, int level)
{                   //以凹入表形式输出二叉树
    if (BT != NULL) //如果二叉树不空
    {
        //二叉树root->Right()第level+1层结点数据域值的横向显示
        PrintBTree(BT->rightChild, level + 1);

        if (level != 0)
        {
            //走过6*(level-1)个空格
            for (int i = 0; i < 6 * (level - 1); i++) cout << " ";
            cout << "----"; //显示横线----
        }
        cout << BT->data << endl; //显示结点的数据域值

        //二叉树root->Left()第level+1层结点数据域值的横向显示
        PrintBTree(BT->leftChild, level + 1);
    }
}
#endif