#include "myTree.h"
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>

using namespace std;

//树节点类的初始化
TreeNode::TreeNode(char value,TreeNode* left,TreeNode* right,NodeTag leftTag,NodeTag rightTag)
    :data(value),leftChild(left),rightChild(right),lTag(leftTag),rTag(rightTag) {}

//树节点类的销毁
TreeNode::~TreeNode() {}

//树初始化  MyTree默认构造函数
MyTree::MyTree():root(nullptr),isThread(false) {}

//设置左孩子
void TreeNode::return_LChild(TreeNode* left)
{
    leftChild=left;
}

//设置右孩子
void TreeNode::return_RChild(TreeNode* right)
{
    rightChild=right;
}

//获取左孩子
TreeNode* TreeNode::getLeftChild() const
{
    return leftChild;
}

//获取右孩子
TreeNode* TreeNode::getRightChild() const
{
    return rightChild;
}

//设置左标记
void TreeNode::setLTag(NodeTag tag)
{
    lTag=tag;
}

//设置右标记
void TreeNode::setRTag(NodeTag tag)
{
    rTag=tag;
}

//获取左标记
NodeTag TreeNode::getLTag() const
{
    return lTag;
}

//获取右标记
NodeTag TreeNode::getRTag() const
{
    return rTag;
}

//递归构建二叉树
TreeNode* buildTree(const char data[],int& index)
{
    char value=data[index++];   //获取当前字符并递增索引

    if(value=='\0')
    {
        return nullptr;         //到达字符串末尾
    }
    if(value=='@')
    {
        return nullptr;         //将空节点忽略
    }

    //创建新结点
    TreeNode* newNode=new TreeNode(value,nullptr,nullptr,Link,Link);

    //递归创建左右子树
    newNode->return_LChild(buildTree(data,index));
    newNode->return_RChild(buildTree(data,index));
    return newNode;

}

//树初始化  MyTree构造函数 根据二叉树的先序序列，生成二叉树的二叉链表存储
MyTree::MyTree(const char data[])
{
    int index=0;
    root=buildTree(data,index);
    isThread=false;
}

//递归复制树的节点
TreeNode* MyTree::copyTree(TreeNode* node)
{
    if(node==nullptr)
    {
        return nullptr;     //若节点为空，返回nullptr
    }

    //创建新节点，复制数据和线索标记
    TreeNode* newNode=new TreeNode(node->data,nullptr,nullptr,node->getLTag(),node->getLTag());

    //递归复制左右子树
    newNode->return_LChild(copyTree(node->getLeftChild()));
    newNode->return_RChild(copyTree(node->getRightChild()));

    return newNode;
}

//树的复制构造函数 复制参数中的树
MyTree::MyTree(const MyTree& other)
{
    root=copyTree(other.root);
    isThread=other.isThread;
}

//树销毁 支持普通二叉树和线索二叉树
MyTree::~MyTree()
{
    //递归释放树的节点
    if(root)
    {
        stack<TreeNode*> nodeStack;
        nodeStack.push(root);
        while(!nodeStack.empty())
        {
            TreeNode* node=nodeStack.top();
            nodeStack.pop();
            if(node->rightChild)
            {
                nodeStack.push(node->rightChild);
            }
            if(node->leftChild)
            {
                nodeStack.push(node->leftChild);
            }
            delete node;    //释放节点
        }
    }
}

//先序遍历二叉树并打印
void MyTree::preOrderTraverse()
{
    if(!root)   return;
    stack<TreeNode*> nodeStack;
    TreeNode* node=root;

    while(node||!nodeStack.empty())
    {
        if(node)
        {
            node->printNode();
            nodeStack.push(node);
            node=node->leftChild;
        }
        else
        {
            node=nodeStack.top();
            nodeStack.pop();
            node=node->rightChild;
        }
    }
}

//中序遍历二叉树并打印
void MyTree::inOrderTraverse()
{
    if(!root)   return;
    stack<TreeNode*> nodeStack;
    TreeNode* current=root;

    while(current||!nodeStack.empty())
    {
        if(current)
        {
            nodeStack.push(current);
            current=current->getLTag()==Link? current->leftChild:nullptr;
        }
        else
        {
            current=nodeStack.top();
            nodeStack.pop();
            current->printNode();
            current=current->getRTag()==Link? current->rightChild:nullptr;
        }
    }
}

//后序遍历二叉树并打印
void MyTree::postOrderTraverse()
{
    if(!root)   return;
    stack<TreeNode*> nodeStack;
    TreeNode* current =root;
    TreeNode* lastVisited=nullptr;

    //while循环走到左子树最左端
    while(current||!nodeStack.empty())
    {
        if(current)
        {
            nodeStack.push(current);
            current=current->leftChild;     //一直走到左孩子最左端
        }
        else
        {
            current=nodeStack.top();        //读取栈顶指针
            //若右子树存在且还未访问
            if(current->rightChild&&current->rightChild!=lastVisited)
            {
                current=current->rightChild;//转向右
            }
            else
            {
                //若不存在右子树或右子树已被访问,弹出节点并进行访问
                current=nodeStack.top();
                nodeStack.pop();
                current->printNode();
                lastVisited=current;        //记录最近访问过的结点
                current=nullptr;            //节点访问后重置p指针
            }   
        }
    }
}

//定位二叉树中的结点
TreeNode& MyTree::locateNode(const char& v)
{
    //在树中找到值为v的结点则返回该节点，否则返回NULL
    //支持普通二叉树与线索二叉树
    if(!root) throw std::runtime_error("Tree is empty");
    stack<TreeNode*> nodeStack;
    nodeStack.push(root);

    while(!nodeStack.empty())
    {
        TreeNode* node=nodeStack.top();
        nodeStack.pop();

        if(node->data==v)
        {
            return *node;
        }
        if(node->rightChild&&node->rTag==Link)
        {
            nodeStack.push(node->rightChild);
        }
        if(node->leftChild&&node->lTag==Link)
        {
            nodeStack.push(node->leftChild);
        }
    }
    throw std::runtime_error("Node not found");
}

//计算二叉树的叶子结点数
int MyTree::countLeaf()
{
    if(!root)   return 0;
    int count=0;
    stack<TreeNode*> nodeStack;
    nodeStack.push(root);

    while(!nodeStack.empty())
    {
        TreeNode* node=nodeStack.top();
        nodeStack.pop();
        //判断是否为叶子结点
        if(!node->leftChild&&!node->rightChild)
        {
            count++;
        }
        if(node->rightChild)
        {
            nodeStack.push(node->rightChild);
        }
        if(node->leftChild)
        {
            nodeStack.push(node->leftChild);
        }
    }
    return count;
}

//计算二叉树的深度
int MyTree::countHeight()
{
    if(!root)   return 0;
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);
    int height=0;

    while(!nodeQueue.empty())
    {
        int levelSize=nodeQueue.size();
        for(int i=0;i<levelSize;i++)
        {
            TreeNode* node=nodeQueue.front();
            nodeQueue.pop();
            if(node->leftChild)
            {
                nodeQueue.push(node->leftChild);
            }
            if(node->rightChild)
            {
                nodeQueue.push(node->rightChild);
            }
        }
        height++;
    }
    return height;
}

//当前树是否为线索二叉树，是则返回true，否则false
bool MyTree::isThreadedTree()
{
    return isThread;
}

//中序线索化的递归函数
void inOrderThread(TreeNode* node,TreeNode*& pre)
{
    if(node==nullptr)   return;     //到达空节点，返回

    //递归遍历左子树
    inOrderThread(node->getLeftChild(),pre);

    //处理当前节点
    if(node->getLeftChild()==nullptr)
    {
        node->setLTag(Thread);      //若无左孩子，则为线索
        node->return_LChild(pre);   //左指针指向前驱
    }
    if(pre!=nullptr&&pre->getRightChild()==nullptr)
    {
        pre->setRTag(Thread);       //若无右孩子，则为线索
        pre->return_RChild(node);   //右指针指向当前节点
    }

    //更新节点
    pre=node;

    if(pre->getRightChild()==nullptr&&pre->getRTag()==Link)
    {
        pre->setRTag(Thread);
    }

    //递归遍历右子树
    inOrderThread(node->getRightChild(),pre);
}

//为二叉树生成中序线索二叉树
bool MyTree::inOrderThreading()
{
    TreeNode* pre=nullptr;      //初始化前驱结点
    inOrderThread(root,pre);    //调用递归函数

    // if(pre!=nullptr)
    // {
    //     pre->setRTag(Thread);
    //     pre->return_RChild(nullptr);
    // }
    isThread=true;  //标记为线索二叉树
    return true;
}

//寻找中序线索二叉树中某结点的前驱结点
TreeNode& MyTree::preNode(const TreeNode& node)
{
    if(!isThread)   throw std::runtime_error("Tree is not a threaded tree");
    //若有左孩子，前驱为左子树的最右端节点
    if(node.lTag==Link&&node.leftChild)
    {
        TreeNode* current=node.leftChild;
        while(current->rTag==Link&&current->rightChild)
        {
            current=current->rightChild;
        }
        return *current;
    }
    //若没有左孩子，前驱为前驱线索指向的结点
    return *node.leftChild;
}

//寻找中序线索二叉树中某结点的后继结点
TreeNode& MyTree::nextNode(const TreeNode& node)
{
    if(!isThread) throw std::runtime_error("Tree is not a threaded tree");
    //若有右孩子，后继为右子树最左节点
    if(node.rightChild&&node.rTag==Link)
    {
        TreeNode* current=node.rightChild;
        while(current->leftChild&&current->lTag==Link)
        {
            current=current->leftChild;
        }
        return *current;
    }
    //若没有右孩子，后继为线索线索指向的结点
    return *node.rightChild;
}

void TreeNode::printNode()
{
    cout << this->data;
}


//构造函数
HuffmanNode::HuffmanNode(int w,int d=0):weight(w),data(d),left(nullptr),right(nullptr) {}

//比较函数
struct Compare
{
    bool operator()(HuffmanNode* l,HuffmanNode* r)
    {
        return l->weight>r->weight;     //权重越小优先级越高
    }
};

//树初始化
HuffmanTree::HuffmanTree(const int& n,const int weights[])
{
    //第一个参数为节点个数
    //第二个参数为节点数组
    
    //使用优先队列构造霍夫曼树
    priority_queue<HuffmanNode*,vector<HuffmanNode*>,Compare> minHeap;

    //将所有权重插入优先队列
    for(int i=0;i<n;i++)
    {
        minHeap.push(new HuffmanNode(weights[i],weights[i]));   //节点值同权重相同
    }

    //构建霍夫曼树
    while(minHeap.size()>1)
    {
        HuffmanNode* left=minHeap.top();    //权重最小的左子树
        minHeap.pop();
        HuffmanNode* right=minHeap.top();   //权重次小的右子树
        minHeap.pop();

        //创建新结点，权重为左右子树权重之和
        HuffmanNode* parent=new HuffmanNode(left->weight+right->weight);
        parent->left=left;                  //将左子树链接到新结点
        parent->right=right;                //将右子树链接到新结点

        minHeap.push(parent);               //新结点插入优先队列
    }
    //设置霍夫曼树根节点
    root=minHeap.top();
}

//树销毁
HuffmanTree::~HuffmanTree()
{
    //递归删除树节点
    function<void(HuffmanNode*)> deleteTree=[&](HuffmanNode* node)
    {
        if(node)
        {
            deleteTree(node->left);
            deleteTree(node->right);
            delete node;
        }
    };
    deleteTree(root);
}

//输出霍夫曼编码
void HuffmanTree::printHuffmanCodes()
{
    map<char,string> huffmanCodes;  //保存编码
    string code;                    //构建编码字符串

    //生成编码的辅助函数
    function<void(HuffmanNode*)> generateCodes=[&](HuffmanNode* node)
    {
        if(!node)   return;
        if(!node->left&&!node->right)       //为叶子结点
        {
            huffmanCodes[node->data]=code;  //编码与节点值关联
        }
        code+='0';          //左子树编码为
        generateCodes(node->left);      //递归生成左子树编码
        code.pop_back();    //撤销最后一位编码
        code+='1';          //右子树编码为
        generateCodes(node->right);     //递归生成右子树编码
        code.pop_back();    //撤销最后一位编码
    };

    //从根节点开始生成编码
    generateCodes(root);

    // 将 map 转换为 vector 以便排序
    vector<pair<int, string>> sortedCodes(huffmanCodes.begin(), huffmanCodes.end());
    
    // 按节点值排序
    sort(sortedCodes.begin(), sortedCodes.end(), [](const pair<int, string>& a, const pair<int, string>& b) {
        return a.first > b.first; // 按值递减排序
    });

    // 输出编码
    for (const auto& pair : sortedCodes) {
        cout << pair.first << ":" << pair.second << endl;
    }
}