47_一阶段项目

学生管理系统项目要求

功能

1. 完成 学生信息 的增删改查
学生ID 学生名 出生年月 性别

2. 发布的数据量 有100w学生
文件存储(及时的存储)

3. 变长字符串存储CMyString

4. 查询 通过ID, 通过名字,允许同名(查询时间复杂度:对数阶)

5. 不能使用三方的函数 stl…

要求

采用平衡二叉树的可靠管理

流程逻辑

代码

 //studentManager.cpp
#include "CControl.h"

int main()
{
    CControl *pControl = new CControl;
    pControl->start();
    delete pControl;
    return 0;
}
 //CControl.h
#pragma once
#include "CIO.h"
#include 
#include "CBinaryTreeForId.h"
#include "CBinaryThreeForName.h"
#include 

class CControl
{
public:
    CControl();
    ~CControl();
    void createTestData();
    void start();
private:
    void menu();
    void initTree();
    void insert(int id = 0);
    void remove(int id = 0);
    void alert();
    void search();
private:
    CBinaryTreeForId *m_pIdTree;
    CBinaryTreeForName *m_pNameTree;
};
 //CIO.h
#pragma once
#include "CException.h"
#include "CStudent.h"

class CIO
{
public:
    CIO();

    ~CIO();

    void write(void const* buff, unsigned int elementSize);

    void read(void *buff, unsigned int elementSize);

    void seek(long offset, int origin);

    long tell();

    int eof();

private:
    FILE *m_pFile;
};
 //CException.h
#pragma once
#include 

class CException
{
public:
    CException(int id);
    void showError();
private:
    int m_nErrorId;
};
 //CStudent.h
#pragma once
#include "CDate.h"
#include "CException.h"
#include "CMystring.h"

using namespace std;

class CStudent
{
public:
    CStudent() {};
    CStudent(const unsigned int id,
            CMyString& name,
            CDate* date,
            char gender
        )
    {
        m_uId = id;
        m_strName = name;
        m_dateBirthday = date,
        m_chGende = gender;
    }

    CStudent(const CStudent& obj)
    {
        m_uId = obj.m_uId;
        m_strName = obj.m_strName;
        m_dateBirthday = new CDate(obj.m_dateBirthday->m_uYear,
            obj.m_dateBirthday->m_uMonth,
            obj.m_dateBirthday->m_uDay
        );
        m_chGende = obj.m_chGende;
        m_lFileDeviationPosition = obj.m_lFileDeviationPosition;
    }

    ~CStudent()
    {
        if (m_dateBirthday != nullptr)
        {
            delete m_dateBirthday;
        }
    }

    void printfInfo()
    {
        printf("学生信息\r\n\tid:%u\r\n\t姓名:%s\r\n\t出生日期:%u年%u月%u日\r\n"
            "\t性别:%s\r\n", m_uId,
            m_strName.getBuff(),
            m_dateBirthday->m_uYear,
            m_dateBirthday->m_uMonth,
            m_dateBirthday->m_uDay,
            m_chGende == 'x' ? "女" :
            (m_chGende == 'y' ? "男" : "未知")
        );
    }

public:
    unsigned int m_uId;
    CMyString m_strName;
    CDate *m_dateBirthday;
    char m_chGende;
    long m_lFileDeviationPosition;
};
 //#include "CDate.h"
#pragma once
class CDate
{
public:
    CDate() {};
    CDate(unsigned short int year, 
        unsigned short int month,
        unsigned short int day)
    {
        m_uYear = year;
        m_uMonth = month;
        m_uDay = day;
    }

public:
    unsigned short int m_uYear;
    unsigned short int m_uMonth;
    unsigned short int m_uDay;
};
 //CMystring.h
#pragma once
#include 

class CMyString
{
public:
    CMyString();    //无参构造
    CMyString(const char *str); //有参构造
    CMyString(unsigned int size); //有参构造带大小
    CMyString(CMyString& str);   //拷贝构造
    ~CMyString();   //析构
    unsigned getLength() const; //获取实际使用长度
    CMyString& myStrcpy(CMyString& str);    //拷贝字符串
    CMyString& myStrcat(CMyString& str);    //拼接字符串
    CMyString& myStrcat(const char * str);    //拼接字符串
    CMyString& myStrUpper();    //转换为大写
    CMyString& myStrLower();    //转换为小写
    const char *myFindSubStr(CMyString& str);    //查找子串-反向
    void myStrClear();  //清空
    const char *getBuff();  //获取字符串内存
    const char *getSubStrPointer(CMyString& str);   //查找位置 反向查找
    const int myStrcmp(CMyString& str);   //比较字符串
    const bool checkIsPlalindrome();    //检测是否为回文
    bool myStrstr(CMyString& str);            //检查子串
private:
    char*& getStr(); //获取字符串
    unsigned getSize() const; //获取实际占用大小
    void setStr(const char *str);  //设置字符串
    void setLength(const unsigned length); //设置实际占用长度
    void setSize(const unsigned size); //设置实际占用空间大小
    bool getIsNull() const;   //检查是否为空
    void setIsNull(bool b);   //设置是否为空
    void initString(const char *str = nullptr); //初始化字符串
private:
    char *m_pStr; //指向字符串的数组
    unsigned m_uLenth;   //字符串的实际使用长度
    unsigned m_uSize;    //字符串的实际占用的内存大小
    bool m_bIsNull; //是否为空标记
};

 //CMyString.cpp
#include "CMyString.h"

CMyString::CMyString()
{
    initString();
}

CMyString::CMyString(CMyString& str)
{
    if (str.getIsNull() == true)
    {
        initString();
    }
    else
    {
        initString(str.getStr());
    }
}

CMyString::CMyString(const char *str)
{
    initString(str);
}

CMyString::CMyString(unsigned int size)
{
    setIsNull(false);
    unsigned uLen = size;
    setLength(uLen - 1U);
    setSize(uLen);
    getStr() = new char[uLen];
}

CMyString::~CMyString()
{
    if (getIsNull() == true)
    {
        return;
    }
    else
    {
        delete[] getStr();
        setIsNull(true);
        setLength(0U);
        setSize(0U);
    }
}

inline char*& CMyString::getStr()
{
    return m_pStr;
}

inline unsigned CMyString::getLength() const
{
    return m_uLenth;
}

inline unsigned CMyString::getSize() const
{
    return m_uSize;
}

inline void CMyString::setStr(const char *str)
{
    strcpy(getStr(), str);
}

inline void CMyString::setLength(const unsigned length)
{
    m_uLenth = length;
}

inline void CMyString::setSize(const unsigned size)
{
    m_uSize = size;
}

inline bool CMyString::getIsNull() const
{
    return m_bIsNull;
}

inline void CMyString::setIsNull(bool b)
{
    m_bIsNull = b;
}

CMyString& CMyString::myStrcpy(CMyString& str)
{
    if (getIsNull())
    {
        if (!str.getIsNull())
        {
            initString(str.getStr());
        }
    }
    else
    {
        if (str.getIsNull())
        {
            setIsNull(true);
        }
        else
        {
            unsigned uLen = str.getLength() + 1U;
            if (getSize() >= uLen)
            {
                setStr(str.getStr());
                setLength(str.getLength());
            }
            else
            {
                delete[] getStr();
                initString(str.getStr());
            }
        }
    }

    return *this;
}

CMyString& CMyString::myStrcat(CMyString& str)
{
    if (getIsNull())
    {
        if (!str.getIsNull())
        {
            initString(str.getStr());
        }
    }
    else
    {
        if (!str.getIsNull())
        {
            unsigned uLen = getLength() + str.getLength() + 1U;
            char *pszTmp = new char[uLen];
            strcpy(pszTmp, getStr());
            strcat(pszTmp, str.getStr());

            if (getSize() >= uLen)
            {
                setStr(pszTmp);
                setLength(uLen - 1);
            }
            else
            {
                delete[] getStr();
                initString(pszTmp);
            }

            delete[] pszTmp;
        }
    }

    return *this;
}

CMyString& CMyString::myStrcat(const char * str)
{
    if (getIsNull())
    {
        if (strlen(str) != 0)
        {
            initString(str);
        }
    }
    else
    {
        if (strlen(str) != 0)
        {
            unsigned uLen = getLength() + strlen(str) + 1U;
            char *pszTmp = new char[uLen];
            strcpy(pszTmp, getStr());
            strcat(pszTmp, str);

            if (getSize() >= uLen)
            {
                setStr(pszTmp);
                setLength(uLen - 1);
            }
            else
            {
                delete[] getStr();
                initString(pszTmp);
            }

            delete[] pszTmp;
        }
    }

    return *this;
}

inline void CMyString::initString(const char* str)
{
    if (str == nullptr)
    {
        setIsNull(true);
        setLength(0U);
        setSize(0U);
    }
    else
    {
        setIsNull(false);
        unsigned uLen = strlen(str) + 1U;
        setLength(uLen - 1U);
        setSize(uLen);
        getStr() = new char[uLen];
        setStr(str);
    }
}

CMyString& CMyString::myStrUpper()
{
    if (!getIsNull())
    {
        char *pchStr = getStr();
        while (*pchStr != '\0')
        {
            if (*pchStr >= 'a' && *pchStr <= 'z')
            {
                *pchStr -= 32;
            }
        }
    }

    return *this;
}

CMyString& CMyString::myStrLower()
{
    if (!getIsNull())
    {
        char *pchStr = getStr();
        while (*pchStr != '\0')
        {
            if (*pchStr >= 'A' && *pchStr <= 'Z')
            {
                *pchStr += 32;
            }
        }
    }

    return *this;
}

inline void CMyString::myStrClear()
{
    setIsNull(true);
}

inline const char* CMyString::myFindSubStr(CMyString& str)
{
    if (str.getLength() > getLength())
    {
        return nullptr;
    }
    else if (getIsNull() || str.getIsNull())
    {
        if (getIsNull() && str.getIsNull())
        {
            return getStr();
        }
        else
        {
            return nullptr;
        }
    }
    else
    {
        //标记是否搜索成功
        const char *isSubStr = nullptr;
        //字符串
        const char *pNowstr = getStr();
        //需要被搜索的字符串
        const char *pFindStr = str.getStr();
        //调至字符串和被搜索的字符串末尾
        while (*pNowstr != '\0')
        {
            pNowstr++;
        }
        pNowstr--;

        while (*pFindStr != '\0')
        {
            pFindStr++;
        }
        pFindStr--;
        //记录一下被搜索的字符串的尾地址
        const char *pFindStrLastPointer = pFindStr;
        //当字符串为开始地址的时候结束
        do
        {
            //如果被搜索的字符串为开始位置
            if (pFindStr == str.getStr() - 1)
            {
                isSubStr = pNowstr + 1;
                break;
            }
            else if (*pNowstr != *pFindStr)
            {
                pNowstr--;
            }
            else//如果有相同的字符串的时候
            {
                do
                {
                    if (*pNowstr != *pFindStr)
                    {
                        pFindStr = pFindStrLastPointer; //如果还没到结束就不相等了,把字符设为尾巴
                        break;
                    }
                    else
                    {
                        pFindStr--;
                        pNowstr--;
                    }
                } while (pFindStr != str.getStr() - 1);//当被搜索的字符串为开始时表明相等

            }
        } while (pNowstr != getStr() - 1);

        //如果两个都结束表示查找的全匹配
        if (pNowstr == getStr() - 1 && pFindStr == str.getStr() - 1)
        {
            isSubStr = getStr();
        }

        return isSubStr;
    }
}

const char *CMyString::getBuff()
{
    if (getIsNull())
    {
        return nullptr;
    }
    else
    {
        return getStr();
    }
}

const char * CMyString::getSubStrPointer(CMyString & str)
{
    return myFindSubStr(str);
}

const int CMyString::myStrcmp(CMyString& str)
{
 
    if (getIsNull() || str.getIsNull())
    {
        if (getIsNull() && str.getIsNull())
        {
            return 0;
        }
        else
        {
            return -1;
        }
    }
    return strcmp(getStr(), str.getStr());
 
}

const bool CMyString::checkIsPlalindrome()
{
    if (getLength() <= 2U)
    {
        return false;
    }

    const char *pStr = getStr();
    unsigned uI = 0;
    unsigned uJ = getLength() - 1U;
    while ((*(pStr + uI) == *(pStr + uJ)) && (uI <= uJ))
    {
        uI++;
        uJ--;
    }
    if (uI > uJ)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool CMyString::myStrstr(CMyString& str)
{
    if (strstr(getBuff(), str.getBuff()) != nullptr)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 //CException.cpp
#include "CException.h"

CException::CException(int id)
{
    m_nErrorId = id;
}

void CException::showError()
{
    switch (m_nErrorId)
    {
    case 1:
        printf("打开文件失败\r\n");
        break;
    case 2:
        printf("读取文件失败\r\n");
        break;
    case 3:
        printf("写入文件失败\r\n");
        break;
    case 4:
        printf("获取文件偏移失败\r\n");
        break;
    case 5:
        printf("移动文件偏移失败\r\n");
        break;
    case 6:
        printf("搜素方式异常\r\n");
        break;
    default:
        break;
    }
}
 //CIO.cpp
#include "CIO.h"

CIO::CIO()
{
    m_pFile = fopen("data.bin", "rb+");
    if (m_pFile == nullptr)
    {
        throw CException(1);
    }
}

CIO::~CIO()
{
    if (m_pFile != nullptr)
    {
        fclose(m_pFile);
    }
}

void CIO::write(void const* buff, unsigned int elementSize)
{
    int nRet = fwrite(buff, elementSize, 1U, m_pFile);

    if (nRet == 1)
    {
        fflush(m_pFile);
        return;
    }
    else
    {
        throw CException(3);
    }
}

void CIO::read(void *buff, unsigned int elementSize)
{
    int nRet = fread(buff, elementSize, 1U, m_pFile);
    if (nRet == 1)
    {
        fflush(m_pFile);
        return;
    }
    else
    {
        throw CException(2);
    }
}

void CIO::seek(long offset, int origin)
{
    int nRet = fseek(m_pFile, offset, origin);
    if (nRet != 0)
    {
        throw CException(5);
    }
}

long CIO::tell()
{
    long lRet = ftell(m_pFile);
    if (lRet != -1L)
    {
        return lRet;
    }
    else
    {
        throw CException(4);
    }
}

int CIO::eof()
{
    return feof(m_pFile);
}

 //Stack.h
#pragma once

template 
class CStack
{
private:
    class CLinkNode     //单向链表
    {
    public:
        CLinkNode()
        {
            m_pElement = nullptr;
            m_pNextNode = nullptr;
        }

        CLinkNode(const T& element)
        {
            m_pElement = new T(element);
            m_pNextNode = nullptr;
        }

        ~CLinkNode()
        {
            if (m_pElement != nullptr)
            {
                delete m_pElement;
            }
        }

    public:
        T* m_pElement;              //元素
        CLinkNode *m_pNextNode;     //下一个结点
    };

public:
    CStack()
    {
        m_pStackTop = nullptr;
        setSize(0U);
    }

    CStack(const T& element)
    {
        m_pStackTop = new CLinkNode(element);
        setSize(1U);
    }

    ~CStack()
    {
        while (m_pStackTop != nullptr)
        {
            pop();
        }
    }

    void push(const T& element)                 //压栈
    {
        CLinkNode *pNode = new CLinkNode(element);
        pNode->m_pNextNode = m_pStackTop;
        m_pStackTop = pNode;
        setSize(getSize() + 1U);
    }

    void pop()                                //出栈
    {
        if (getSize() > 0)
        {
            CLinkNode *pOldNode = m_pStackTop;
            m_pStackTop = pOldNode->m_pNextNode;
            delete pOldNode;
            setSize(getSize() - 1U);
        }
    }

    T* getTop() const    //获得栈顶元素
    {
        return m_pStackTop->m_pElement;
    }

    const unsigned getSize() const  //获得栈的大小
    {
        return m_uSize;
    }

private:
    void setSize(const unsigned size)   //设置栈大小
    {
        m_uSize = size;
    }

private:
    CLinkNode *m_pStackTop;     //栈顶
    unsigned m_uSize;           //栈的大小
};
 //Queue.h
#pragma once

template 
class CQueue
{
private:
    class CLinkNode     //单向链表
    {
    public:
        CLinkNode()
        {
            m_pElement = nullptr;
            m_pNextNode = nullptr;
        }

        CLinkNode(const T& element)
        {
            m_pElement = new T(element);
            m_pNextNode = nullptr;
        }

        ~CLinkNode()
        {
            if (m_pElement != nullptr)
            {
                delete m_pElement;
            }
        }

    public:
        T* m_pElement;              //元素
        CLinkNode *m_pNextNode;     //下一个结点
    };

public:
    CQueue()
    {
        m_pQueueHead = nullptr;
        m_pQueueTail = nullptr;
        setSize(0U);
    }

    CQueue(const T& element)
    {
        CLinkNode *pNode = new CLinkNode(element);
        m_pQueueHead = m_pQueueTail = pNode;
        setSize(1U);
    }

    ~CQueue()
    {
        while (getSize() > 0U)
        {
            pop();
        }
    }

    void push(const T& element)                 //入队
    {
        if (getSize() == 0U)
        {
            CLinkNode *pNode = new CLinkNode(element);
            m_pQueueHead = m_pQueueTail = pNode;
            setSize(1U);
        }
        else
        {
            CLinkNode *pNode = new CLinkNode(element);
            m_pQueueTail->m_pNextNode = pNode;
            m_pQueueTail = pNode;
            setSize(getSize() + 1U);
        }
    }

    void pop()                                //出队
    {
        if (getSize() == 0U)
        {
            return;
        }
        else
        {
            CLinkNode *pNode = m_pQueueHead;
            m_pQueueHead = pNode->m_pNextNode;
            delete pNode;
            setSize(getSize() - 1U);
        }
    }

    T* getTail() const    //获得队列尾部元素
    {
        if (getSize() > 0)
        {
            return m_pQueueTail->m_pElement;
        }
        else
        {
            throw 0;
        }
    }

    T* getHead() const  //获得队列头部元素
    {
        if (getSize() > 0)
        {
            return m_pQueueHead->m_pElement;
        }
        else
        {
            throw 0;
        }
    }

    const unsigned getSize() const  //获得队列的大小
    {
        return m_uSize;
    }

private:
    void setSize(const unsigned size)   //设置队列大小
    {
        m_uSize = size;
    }

private:
    CLinkNode *m_pQueueHead;    //队列头
    CLinkNode *m_pQueueTail;     //队列尾
    unsigned m_uSize;           //队列的大小
};
 //CBinaryTreeForId.h
#pragma once
#include "Stack.h"
#include "Queue.h"
#include "CStudent.h"
#include 

class CBinaryTreeForId
{
private:
    class TreeNode
    {
    public:

        TreeNode(CStudent &element,
            TreeNode *left = nullptr,
            TreeNode *right = nullptr,
            int ef = 0
        )

        {
            m_pElement = &element;
            m_pLeft = left;
            m_pRight = right;
            m_iEf = ef;
        }

        ~TreeNode()
        {
            if (m_pElement != nullptr)
            {
                delete m_pElement;
            }
        }

    public:
        CStudent *m_pElement;   //元素
        TreeNode *m_pLeft;      //左儿子
        TreeNode *m_pRight;     //右儿子
        int m_iEf;              //平衡因子
    };

public:

    void showMaxStuInfo()
    {
        TreeNode *pNode = m_pTreeRoot;
        while (pNode->m_pRight != nullptr)
        {
            pNode = pNode->m_pRight;
        }
        printf("id最大的");
        pNode->m_pElement->printfInfo();
    }

    CBinaryTreeForId()
    {
        m_pTreeRoot = nullptr;
    }

    CBinaryTreeForId(CStudent& element)
    {
        m_pTreeRoot = new TreeNode(element);
    }

    ~CBinaryTreeForId()
    {
        if (m_pTreeRoot != nullptr)
        {
            //removeTree(m_pTreeRoot);
            removeTree_n(m_pTreeRoot);
        }
    }

    CBinaryTreeForId& insert_n(CStudent& element)     //非递归增加
    {
        if (empty())   //如果根节点为空,表示为第一个节点
        {
            m_pTreeRoot = new TreeNode(element);
            balance(m_pTreeRoot);         //平衡树
            return *this;
        }

        CStack stack;
        TreeNode *pNode = m_pTreeRoot;
        TreeNode *pLastNode = nullptr;

        //压栈之前的结点位置
        while (pNode != nullptr)
        {
            //判断大小来确定放左孩子还是右孩子
            if (element.m_uId > pNode->m_pElement->m_uId)
            {
                stack.push(pNode);
                pNode = pNode->m_pRight;
            }
            else if (element.m_uId < pNode->m_pElement->m_uId)
            {
                stack.push(pNode);
                pNode = pNode->m_pLeft;
            }
        }
        //存放新结点
        pNode = *stack.getTop();

        if (element.m_uId > pNode->m_pElement->m_uId)
        {
            pNode->m_pRight = new TreeNode(element);
            balance(pNode->m_pRight);
        }
        else if (element.m_uId < pNode->m_pElement->m_uId)
        {
            pNode->m_pLeft = new TreeNode(element);
            balance(pNode->m_pLeft);
        }

        //平衡树高度
        while (stack.getSize() != 0U)
        {
            pNode = *stack.getTop();
            pLastNode = pNode;
            balance(pNode); //第5次增加到3的时候
            if (pLastNode != pNode && *stack.getTop() != m_pTreeRoot)
            {
                if (pNode->m_pElement->m_uId > pLastNode->m_pElement->m_uId)
                {
                    pLastNode = pNode;
                    stack.pop();
                    pNode = *stack.getTop();
                    pNode->m_pRight = pLastNode;
                }
                else if (pNode->m_pElement->m_uId < 
                    pLastNode->m_pElement->m_uId)
                {
                    pLastNode = pNode;
                    stack.pop();
                    pNode = *stack.getTop();
                    pNode->m_pLeft = pLastNode;
                }
            }
            else
            {
                stack.pop();
            }
        }
        if (m_pTreeRoot != pNode)
        {
            m_pTreeRoot = pNode;
        }

        return *this;
    }

    void remove_n(const CStudent& element) //非递归删除
    {
        if (!empty())
        {
            CStack stack;
            TreeNode *pNode = m_pTreeRoot;

            while (true)    //寻找结点
            {
                if (pNode != nullptr)
                {
                    if (element.m_uId > pNode->m_pElement->m_uId)
                    {
                        stack.push(pNode);
                        pNode = pNode->m_pRight;
                    }
                    else if (element.m_uId < pNode->m_pElement->m_uId)
                    {
                        stack.push(pNode);
                        pNode = pNode->m_pLeft;
                    }
                    else if (element.m_uId == pNode->m_pElement->m_uId)
                    {
                        break;
                    }
                }
                else
                {
                    stack.~CStack();
                    return;
                }
            }

            //如果找到了结点
            if (!(stack.getSize() == 0U
                && pNode->m_pLeft == nullptr
                && pNode->m_pRight == nullptr)
                )
            {
                if (pNode->m_pLeft == nullptr
                    && pNode->m_pRight == nullptr) //如果为叶子节点
                {
                    TreeNode *pParmarNode = *stack.getTop();
                    if (pParmarNode->m_pRight == pNode)
                    {
                        delete pParmarNode->m_pRight;
                        pParmarNode->m_pRight = nullptr;
                    }
                    else
                    {
                        delete pParmarNode->m_pLeft;
                        pParmarNode->m_pLeft = nullptr;
                    }
                    balance(pParmarNode);
                    stack.pop();

                    while (stack.getSize() != 0U)
                    {
                        pParmarNode = *stack.getTop();
                        stack.pop();
                        balance(pParmarNode);
                    }

                    if (m_pTreeRoot != pParmarNode)
                    {
                        m_pTreeRoot = pParmarNode;
                    }

                    return;
                }
                else if (pNode->m_pLeft == nullptr  //一个孩子
                    ||
                    pNode->m_pRight == nullptr
                    )
                {
                    if (stack.getSize() != 0U)
                    {
                        TreeNode *pOld = pNode; //保留删除点位置
                        TreeNode *pParmarNode = *stack.getTop();  //获取父节点指针

                        pNode = (pNode->m_pLeft != nullptr)
                            ? pNode->m_pLeft
                            : pNode->m_pRight;  //删除节点的非空节点

                        if (pParmarNode->m_pLeft == pOld)   //设父节点的原位置为删除节点的左或者右节点
                        {
                            pParmarNode->m_pLeft = pNode;
                        }
                        else
                        {
                            pParmarNode->m_pRight = pNode;
                        }

                        delete pOld;
                        stack.pop();
                        balance(pNode);
                        balance(pParmarNode);

                        while (stack.getSize() != 0U)
                        {
                            pParmarNode = *stack.getTop();
                            stack.pop();
                            balance(pParmarNode);
                        }

                        if (m_pTreeRoot != pParmarNode)
                        {
                            m_pTreeRoot = pParmarNode;
                        }

                        return;
                    }
                    else                        //删除的是树根的左树或者右树
                    {
                        if (m_pTreeRoot->m_pLeft != nullptr)
                        {
                            m_pTreeRoot = m_pTreeRoot->m_pLeft;
                            delete pNode;
                        }
                        else
                        {
                            m_pTreeRoot = m_pTreeRoot->m_pRight;
                            delete pNode;
                        }

                        return;
                    }
                }
                else                               //二个孩子,删除节点左子树的最右侧节点,它的值代替当前节点
                {
                    if (stack.getSize() != 0U)
                    {
                        TreeNode *pParmarNode = pNode->m_pLeft;
                        TreeNode *pElementNode = pNode->m_pLeft;

                        while (true)
                        {
                            if (pElementNode->m_pRight == nullptr)
                            {
                                break;
                            }

                            pElementNode = pElementNode->m_pRight;
                        }

                        //*pNode->m_pElement = *pElementNode->m_pElement; //修改值
                        pNode->m_pElement->m_uId = 
                            pElementNode->m_pElement->m_uId;
                        pNode->m_pElement->m_strName.myStrcpy(
                            pElementNode->m_pElement->m_strName);
                        delete pNode->m_pElement->m_dateBirthday;
                        pNode->m_pElement->m_dateBirthday = 
                            pElementNode->m_pElement->m_dateBirthday;
                        pElementNode->m_pElement->m_dateBirthday = nullptr;
                        pNode->m_pElement->m_chGende =
                            pElementNode->m_pElement->m_chGende;
                        pNode->m_pElement->m_lFileDeviationPosition =
                            pElementNode->m_pElement->m_lFileDeviationPosition;

                        if (pParmarNode == pElementNode)
                        {
                            pNode->m_pLeft = nullptr;
                        }
                        else
                        {
                            while (true)                                    //删除
                            {
                                if (pParmarNode->m_pRight == pElementNode)
                                {
                                    break;
                                }
                                pParmarNode = pParmarNode->m_pRight;
                            }
                            pParmarNode->m_pRight = nullptr;
                        }

                        delete pElementNode;
                        balance(pNode);

                        while (stack.getSize() != 0U)
                        {
                            pNode = *stack.getTop();
                            stack.pop();
                            balance(pNode);
                        }

                        if (m_pTreeRoot != pNode)
                        {
                            m_pTreeRoot = pNode;
                        }

                        return;
                    }
                    else                //如果为三个节点的二叉树
                    {
                        m_pTreeRoot = pNode->m_pRight;
                        pNode->m_pRight->m_pLeft = pNode->m_pLeft;
                        balance(m_pTreeRoot);
                        delete pNode;
                        return;
                    }
                }
            }
            else              //如果栈大小为0切左右结点为空表示树只有一个结点切为栈顶
            {
                m_pTreeRoot = nullptr;
                delete pNode;
            }

        }
    }

    bool find_n(const int& id) //非递归查找
    {
        if (!empty()) //如果空树返回false
        {
            TreeNode *pNode = m_pTreeRoot;
            while (true)
            {
                if (pNode != nullptr)
                {
                    if ((unsigned int)id > pNode->m_pElement->m_uId)
                    {
                        pNode = pNode->m_pRight;
                    }
                    else if ((unsigned int)id < pNode->m_pElement->m_uId)
                    {
                        pNode = pNode->m_pLeft;
                    }
                    else
                    {
                        return true;
                    }
                }
                else
                {
                    return false;
                }
            }

        }
        else
        {
            return false;
        }
    }

    CStudent* find_stu(const int& id) //非递归查找
    {
        if (!empty()) //如果空树返回false
        {
            TreeNode *pNode = m_pTreeRoot;
            while (true)
            {
                if (pNode != nullptr)
                {
                    if ((unsigned int)id > pNode->m_pElement->m_uId)
                    {
                        pNode = pNode->m_pRight;
                    }
                    else if ((unsigned int)id < pNode->m_pElement->m_uId)
                    {
                        pNode = pNode->m_pLeft;
                    }
                    else
                    {
                        return pNode->m_pElement;
                    }
                }
                else
                {
                    return nullptr;
                }
            }

        }
        else
        {
            return nullptr;
        }
    }

    bool empty()
    {
        if (m_pTreeRoot == nullptr)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    void printTreePre()
    {
        _printTreePre(getRoot());
    }

    void printTreeMid()
    {
        _printTreeMid(getRoot());
    }

    void printTreeAft()
    {
        _printTreeAft(getRoot());
    }

    void printTreeOrd()
    {
        _printTreeOrd(getRoot());
    }

private:

    void removeTree_n(TreeNode* node)
    {
        if (!empty())
        {
            CStackstack;
            TreeNode *curNode = m_pTreeRoot;
            TreeNode *topNode = nullptr;
            TreeNode *lastNode = nullptr;

            while (curNode != nullptr
                ||
                stack.getSize() != 0U
                )
            {
                while (curNode != nullptr)
                {
                    stack.push(curNode);
                    curNode = curNode->m_pLeft;
                }
                //此时curNode指向空节点
                topNode = *stack.getTop();//
                if (topNode->m_pRight == nullptr
                    ||
                    topNode->m_pRight == lastNode)
                {
                    stack.pop();
                    lastNode = topNode;
                    delete topNode;
                }
                else
                {
                    curNode = topNode->m_pRight;
                }
            }
        }
    }


    TreeNode* findMin(TreeNode* node)
    {
        if (node == nullptr)
            return nullptr;

        while (true)
        {
            if (node->m_pLeft == nullptr)
            {
                return node;
            }
            node = node->m_pLeft;
        }
    }


    int getEf(TreeNode *node)    //获取左右子树平衡因子最大值
    {
        if (node == nullptr)
        {
            return 0;
        }
        else
        {
            return node->m_iEf;
        }
    }

    TreeNode* getRoot()
    {
        return m_pTreeRoot;
    }

    int getMax(int value1, int value2)
    {
        return value1 > value2 ? value1 : value2;
    }

    void rotateRight(TreeNode*& node)   //右旋转
    {
        /*
        k1
        k2
        k3
        */
        /*
        10
        5     12
        3  7
        4

        5
        3  10
        4  7  12
        */

        TreeNode *K1 = node;
        TreeNode *K2 = K1->m_pLeft;
        TreeNode *A = K2->m_pLeft;
        TreeNode *B = K2->m_pRight;
        TreeNode *C = K1->m_pRight;

        K1->m_pLeft = B;
        K2->m_pRight = K1;

        K1->m_iEf = getMax(getEf(B), getEf(C)) + 1;
        K2->m_iEf = getMax(getEf(K1), getEf(A)) + 1;

        node = K2;

    }

    void rotateLeft(TreeNode*& node) //左单旋转
    {
        /*
        5
        4    10
        9  11
        12
        10
        5  11
        4  9   12
        */
        TreeNode *K1 = node;
        TreeNode *K2 = K1->m_pRight;
        TreeNode *A = K1->m_pLeft;
        TreeNode *B = K2->m_pLeft;
        TreeNode *C = K2->m_pRight;

        K1->m_pRight = B;
        K2->m_pLeft = K1;

        K1->m_iEf = getMax(getEf(A), getEf(B)) + 1;
        K2->m_iEf = getMax(getEf(K1), getEf(C)) + 1;

        node = K2;
    }

    void rotateLeftRight(TreeNode*& node)   //先左后右
    {
        rotateLeft(node->m_pLeft);
        rotateRight(node);
    }

    void rotateRightLeft(TreeNode*& node)   //先右后左
    {
        rotateRight(node->m_pRight);
        rotateLeft(node);
    }

    void balance(TreeNode*& node) //平衡二叉树
    {
        //设置高度
        if (getEf(node->m_pLeft) > getEf(node->m_pRight))
        {
            node->m_iEf = getEf(node->m_pLeft) + 1;
        }
        else
        {
            node->m_iEf = getEf(node->m_pRight) + 1;
        }
        //判断平衡
        if (getEf(node->m_pLeft) - getEf(node->m_pRight) > 1)
        {
            //左边不平衡
            if (getEf(node->m_pLeft->m_pLeft) - 
                getEf(node->m_pLeft->m_pRight) > 0)
            {
                rotateRight(node);
            }
            else
            {
                //左双旋转
                rotateLeftRight(node);
            }
        }
        else if (getEf(node->m_pLeft) - getEf(node->m_pRight) < -1)
        {
            //右边不平衡
            if (getEf(node->m_pRight->m_pLeft) - 
                getEf(node->m_pRight->m_pRight) < 0)
            {
                //左单旋转
                rotateLeft(node);
            }
            else
            {
                //右双旋转
                rotateRightLeft(node);
            }
        }

    }

    void _printTreePre(TreeNode *node)             //前序遍历
    {
        if (!empty())
        {
            /*
            if (node != nullptr)
            {
            cout << *(node->m_pElement) << " ";
            printTreePre(node->m_pLeft);
            printTreePre(node->m_pRight);
            }
            */
            //压栈当前根,打印当前根元素,根等于当前更的左孩子,当当前更的左孩子为空时出栈,并进去当前根的右孩子,压栈右孩子。循环
            CStack stack;
            while (true)
            {
                if (node != nullptr)
                {
                    stack.push(node);
                    printf("%d ",(node->m_pElement->m_uId));
                    node = node->m_pLeft;
                }
                else if (node == nullptr && stack.getSize() == 0U)
                {
                    break;
                }
                else if (node == nullptr)
                {
                    node = *stack.getTop();
                    stack.pop();
                    node = node->m_pRight;
                }
            }
            printf("\r\n");

        }
    }

    void _printTreeMid(TreeNode *node)             //中序遍历
    {
        if (!empty())
        {
            /*
            if (node != nullptr)
            {
            printTreeMid(node->m_pLeft);
            cout << *(node->m_pElement) << " ";
            printTreeMid(node->m_pRight);
            }
            */
            //压栈当前根,根等于当前更的左孩子,当当前更的左孩子为空时出栈,打印当前根元素,并进去当前根的右孩子,压栈右孩子。循环
            CStack stack;
            while (true)
            {
                if (node != nullptr)
                {
                    stack.push(node);
                    node = node->m_pLeft;
                }
                else if (node == nullptr && stack.getSize() == 0U)
                {
                    break;
                }
                else if (node == nullptr)
                {
                    node = *stack.getTop();
                    stack.pop();
                    printf("%d ", (node->m_pElement->m_uId));
                    node = node->m_pRight;
                }
            }
            printf("\r\n");
        }
    }

    void _printTreeAft(TreeNode *node)             //后序遍历
    {
        if (!empty())
        {
            /*
            if (node != nullptr)
            {
            printTreeAft(node->m_pLeft);
            printTreeAft(node->m_pRight);
            cout << *(node->m_pElement) << " ";
            }
            */

            //当左孩子不为空一直压栈当前结点,为空当前结点就为栈顶元素,出栈,当前结点为节点右孩子,如果结点不为空压栈右孩子,打印。
            //后序:2 5 7 6 4 17 21 20 10

            CStackstack;
            TreeNode *curNode = m_pTreeRoot;
            TreeNode *topNode = nullptr;
            TreeNode *lastNode = nullptr;
            while (curNode != nullptr
                ||
                stack.getSize() != 0U
                )
            {
                while (curNode != nullptr)
                {
                    stack.push(curNode);
                    curNode = curNode->m_pLeft;
                }
                //此时curNode指向空节点
                topNode = *stack.getTop();//
                if (topNode->m_pRight == nullptr
                    ||
                    topNode->m_pRight == lastNode)
                {
                    stack.pop();
                    printf("%d ", (topNode->m_pElement->m_uId));
                    lastNode = topNode;
                }
                else
                {
                    curNode = topNode->m_pRight;
                }
            }
            printf("\r\n");

        }

    }

    void _printTreeOrd(TreeNode *node)             //层序遍历
    {
        //10 4 20 2 6 17 21 5 7
        if (!empty())
        {
            CQueue queue;
            TreeNode *pLeft = nullptr;
            TreeNode *pRight = nullptr;
            queue.push(node);

            while (queue.getSize() != 0U)
            {
                node = *queue.getHead();
                printf("%d ", (node->m_pElement->m_uId));
                pLeft = node->m_pLeft;
                pRight = node->m_pRight;
                if (pLeft != nullptr)
                {
                    queue.push(pLeft);
                }
                if (pRight != nullptr)
                {
                    queue.push(pRight);
                }
                queue.pop();
            }
            printf("\r\n");

        }
    }

private:
    TreeNode *m_pTreeRoot;  //树根
};
 //CBinaryThreeForName.h
#pragma once
#include "CStudent.h"
#include "Stack.h"

class CBinaryTreeForName
{
private:
    class CTreeNode
    {
    public:
        CTreeNode(
            CStudent *element = nullptr,
            CTreeNode *parents = nullptr,
            CTreeNode *left = nullptr,
            CTreeNode *right = nullptr,
            int height = 0,
            CTreeNode *next = nullptr
        )
            :m_pElement(element), m_pParents(parents), m_pLeft(left), 
            m_pRight(right),m_iHeight(height), m_pNext(next) {};
        ~CTreeNode()
        {
            if (m_pElement != nullptr)
            {
                delete m_pElement;
            }
        }
    public:
        CStudent *m_pElement;   //元素
        CTreeNode *m_pParents;  //双亲结点
        CTreeNode *m_pLeft;     //左孩子
        CTreeNode *m_pRight;    //右孩子
        int m_iHeight;          //树的高度
        CTreeNode *m_pNext;      //重复名的下一个结点
    };

public:
    CBinaryTreeForName()
    {
        m_pRoot = nullptr;
    }

    ~CBinaryTreeForName()
    {
        if (!empty())
        {
            CStackstack;
            CTreeNode *curNode = m_pRoot;
            CTreeNode *topNode = nullptr;
            CTreeNode *lastNode = nullptr;

            while (curNode != nullptr
                ||
                stack.getSize() != 0U
                )
            {
                while (curNode != nullptr)
                {
                    stack.push(curNode);
                    curNode = curNode->m_pLeft;
                }
                //此时curNode指向空节点
                topNode = *stack.getTop();//
                if (topNode->m_pRight == nullptr
                    ||
                    topNode->m_pRight == lastNode)
                {
                    stack.pop();
                    lastNode = topNode;
                    delete topNode;
                }
                else
                {
                    curNode = topNode->m_pRight;
                }
            }
        }
    }

    CBinaryTreeForName& insert(CStudent* stu)   //增加
    {
        if (!empty())
        {
            CTreeNode *pNewNode = new CTreeNode(stu);
            CTreeNode *pNode = m_pRoot;
            CTreeNode *pParents = m_pRoot;

            while (true)
            {
                if (pNode->m_pElement->m_strName.myStrcmp( //如果当前树名字大于增加的名字
                    pNewNode->m_pElement->m_strName) > 0
                    )
                {
                    pNode = pNode->m_pLeft;
                    if (pNode == nullptr)
                    {
                        pParents->m_pLeft = pNewNode;
                        pParents->m_pLeft->m_pParents = pParents;
                        balance(pParents->m_pLeft);
                        while (pParents != nullptr)
                        {
                            balance(pParents);
                            pParents = pParents->m_pParents;
                        }
                        return *this;
                    }
                    pParents = pNode;
                }
                else if (pNode->m_pElement->m_strName.myStrcmp( //如果当前树名字小于增加的名字
                    pNewNode->m_pElement->m_strName) < 0
                    )
                {
                    pNode = pNode->m_pRight;
                    if (pNode == nullptr)
                    {
                        pParents->m_pRight = pNewNode;
                        pParents->m_pRight->m_pParents = pParents;
                        balance(pParents->m_pRight);
                        while (pParents != nullptr)
                        {
                            balance(pParents);
                            pParents = pParents->m_pParents;
                        }
                        return *this;
                    }
                    pParents = pNode;
                }
                else                                        //如果相等
                {
                    if (pNode->m_pNext != nullptr)   //如果下一个相同名字不为空
                    {
                        //[1][2]-->[3] -->[1][3][2]
                        pNewNode->m_pNext = pNode->m_pNext;
                        //pNewNode->m_pParents = pNode->m_pParents;
                        pNode->m_pNext = pNewNode;
                    }
                    else
                    {
                        pNode->m_pNext = pNewNode;
                    }

                    return *this;
                }
            }  //结束非空节点增加
            
        }
        else
        {
            m_pRoot = new CTreeNode(stu); //空节点增加
            balance(m_pRoot);
            return *this;
        }
    }

    CBinaryTreeForName& remove(CStudent* stu)   //删除
    {
        if (!empty())
        {
            CTreeNode *pNode = m_pRoot;

            while (pNode != nullptr)
            {
                //如果当前树名字大于删除的名字
                if (pNode->m_pElement->m_strName.myStrcmp(stu->m_strName) > 0)
                {
                    pNode = pNode->m_pLeft;
                }
                else if (pNode->m_pElement->m_strName.myStrcmp(
                    stu->m_strName) < 0
                    )
                {
                    pNode = pNode->m_pRight;
                }
                else//找到了,删除之后要向上平衡高度
                {
                    //如果为叶子节点
                    if (pNode->m_pLeft == nullptr && pNode->m_pRight == nullptr)
                    {
                        if (pNode->m_pNext == nullptr) //如果没有同名
                        {
                            //获取父节点
                            CTreeNode *pParents = pNode->m_pParents;
                            //修改父节点的当前结点为空
                            if (pParents != nullptr)
                            {
                                if (pParents->m_pLeft == pNode)
                                {
                                    pParents->m_pLeft = nullptr;
                                }
                                else
                                {
                                    pParents->m_pRight = nullptr;
                                }
                            }
                            else         //如果没有父节点为根节点
                            {
                                delete pNode;
                                m_pRoot = nullptr;
                                return *this;
                            }
                            delete pNode;
                            while (pParents != nullptr)
                            {
                                balance(pParents);
                                pParents = pParents->m_pParents;
                            }
                            return *this;
                        }//结束叶子节点非同名情况
                        else
                        {
                            removeSameName(pNode, stu);
                            return *this;
                        }
                    }//结束孩子为叶子节点
                    else if (pNode->m_pLeft == nullptr //如果有一个孩子不为空
                            || pNode->m_pRight == nullptr
                        )
                    {
                        if (pNode->m_pNext == nullptr) //如果没有同名
                        {
                            //获取父节点
                            CTreeNode *pParents = pNode->m_pParents;
                            //获取当前结点的孩子结点
                            CTreeNode *pSon =
                                (pNode->m_pLeft != nullptr ?
                                    pNode->m_pLeft : pNode->m_pRight
                                    );
                            
                            if (pParents != nullptr)
                            {
                                //修改当前结点的孩子的父亲为当前结点的父亲
                                pSon->m_pParents = pParents;
                                //当前结点的父亲的孩子为当前结点的孩子
                                if (pParents->m_pLeft == pNode)
                                {
                                    pParents->m_pLeft = pSon;
                                }
                                else
                                {
                                    pParents->m_pRight = pSon;
                                }
                                //删除当前结点
                                delete pNode;
                                while (pParents != nullptr)
                                {
                                    balance(pParents);
                                    pParents = pParents->m_pParents;
                                }
                                return *this;
                            }
                            else         //如果没有父节点为根节点
                            {
                                if (m_pRoot->m_pLeft != nullptr)
                                {
                                    m_pRoot = m_pRoot->m_pLeft;
                                }
                                else
                                {
                                    m_pRoot = m_pRoot->m_pRight;
                                }
                                m_pRoot->m_pParents = nullptr;
                                delete pNode;
                                return *this;
                            }
                        }//结束只有一个孩子的非同名情况
                        else
                        {
                            removeSameName(pNode, stu);
                            return *this;
                        }
                    }//结束有一个孩子不为空
                    else if (pNode->m_pLeft != nullptr //如果有两个孩子
                        && pNode->m_pRight != nullptr
                        )
                    {
                        if (pNode->m_pNext == nullptr) //如果没有同名的情况下
                        {
                            if (pNode != m_pRoot)
                            {
                                //左子树的最右侧替换当前元素
                                CTreeNode *pOld = pNode;
                                pNode = pNode->m_pLeft;
                                while (pNode->m_pRight != nullptr)
                                {
                                    pNode = pNode->m_pRight;
                                }
                                CTreeNode *pParents = pNode->m_pParents;
                                //交换数据
                                pOld->m_pElement->m_chGende =
                                    pNode->m_pElement->m_chGende;
                                delete pOld->m_pElement->m_dateBirthday;
                                pOld->m_pElement->m_dateBirthday =
                                    pNode->m_pElement->m_dateBirthday;
                                pNode->m_pElement->m_dateBirthday = nullptr;
                                pOld->m_pElement->m_lFileDeviationPosition =
                                    pNode->m_pElement->m_lFileDeviationPosition;
                                pOld->m_pElement->m_uId =
                                    pNode->m_pElement->m_uId;
                                pOld->m_pElement->m_strName.myStrcpy(
                                    pNode->m_pElement->m_strName
                                );
                                //设置一下被替换的父节点孩子为空
                                if (pParents->m_pRight == pNode)
                                {
                                    pParents->m_pRight = nullptr;
                                }
                                else
                                {
                                    pParents->m_pLeft = nullptr;
                                }
                                //删除替换的元素
                                delete pNode;
                                while (pParents != nullptr)
                                {
                                    balance(pParents);
                                    pParents = pParents->m_pParents;
                                }
                                return *this;
                            }
                            else
                            {
                                //如果删除的为根节点
                                //左子树的最右侧替换当前元素
                                CTreeNode *pOld = pNode; //根节点
                                pNode = pNode->m_pLeft;  //根节点左边
                                while (pNode->m_pRight != nullptr)
                                {
                                    pNode = pNode->m_pRight; //根节点左边最大右边
                                }
                                CTreeNode *pParents = pNode->m_pParents; //根节点或根节点左边最大右边上一个父亲
                                //交换数据
                                pOld->m_pElement->m_chGende =
                                    pNode->m_pElement->m_chGende;
                                delete pOld->m_pElement->m_dateBirthday;
                                pOld->m_pElement->m_dateBirthday =
                                    pNode->m_pElement->m_dateBirthday;
                                pNode->m_pElement->m_dateBirthday = nullptr;
                                pOld->m_pElement->m_lFileDeviationPosition =
                                    pNode->m_pElement->m_lFileDeviationPosition;
                                pOld->m_pElement->m_uId =
                                    pNode->m_pElement->m_uId;
                                pOld->m_pElement->m_strName.myStrcpy(
                                    pNode->m_pElement->m_strName
                                );
                                if (m_pRoot != pParents)
                                {
                                    //设置一下被替换的父节点孩子
                                    if (pNode->m_pLeft == nullptr)
                                    {
                                        pParents->m_pRight = nullptr;
                                    }
                                    else
                                    {
                                        pParents->m_pRight = pNode->m_pLeft;
                                        pNode->m_pLeft->m_pParents = pParents;
                                    }
                                }
                                else
                                {
                                    m_pRoot->m_pLeft = pNode->m_pLeft;
                                    m_pRoot->m_pLeft->m_pParents = m_pRoot;
                                }
                                //删除替换的元素
                                delete pNode;
                                while (pParents != nullptr)
                                {
                                    balance(pParents);
                                    pParents = pParents->m_pParents;
                                }
                                return *this;
                            }
                            
                        } //结束两个孩子没同名情况
                        else
                        {
                            removeSameName(pNode, stu);
                            return *this;
                        }
                    } //结束有两个孩子的删除
                    else
                    {
                        printf("删除意外情况\r\n");
                        system("pause");
                        return *this;
                    }
                }//结束找到之后的删除操作

            }//结束非空查找

            return *this;
        }
        else
        {
            return *this;
        }
    }

    void search(CMyString& str)   //查询
    {
        if (!empty())
        {
            CTreeNode *pNode = m_pRoot;
            while (pNode != nullptr)
            {
                int nRet = pNode->m_pElement->m_strName.myStrcmp(str);
                if (nRet > 0) //如果当前树名字大于增加的名字
                {
                    pNode = pNode->m_pLeft;
                }
                else if(nRet < 0)
                {
                    pNode = pNode->m_pRight;
                }
                else
                {
                    while (pNode != nullptr)
                    {
                        pNode->m_pElement->printfInfo();
                        pNode = pNode->m_pNext;
                    }
                    return;
                }
            }
            printf("没有找到匹配的名字\r\n");
        }
    }

    void printMax()
    {
        if (!empty())
        {
            CTreeNode *pNode = m_pRoot;
            while (pNode->m_pRight != nullptr)
            {
                pNode = pNode->m_pRight;
            }
            printf("%u", pNode->m_pElement->m_uId);
        }
    }

    void printTest()
    {
        printMid(m_pRoot);
    }

    void printMid(CTreeNode *pNode)
    {
        if (pNode != nullptr)
        {
            printMid(pNode->m_pLeft);
            printf("%s ", pNode->m_pElement->m_strName.getBuff());
            printMid(pNode->m_pRight);
        }
    }

    void printTreeMid()             //中序遍历
    {
        CTreeNode *node = m_pRoot;
        if (!empty())
        {
            CStack stack;
            while (true)
            {
                if (node != nullptr)
                {
                    stack.push(node);
                    node = node->m_pLeft;
                }
                else if (node == nullptr && stack.getSize() == 0U)
                {
                    break;
                }
                else if (node == nullptr)
                {
                    node = *stack.getTop();
                    stack.pop();
                    printf("%d ", (node->m_pElement->m_uId));
                    node = node->m_pRight;
                }
            }
            printf("\r\n");
        }
    }
private:
    bool empty()                        //是否为空树
    {
        if (m_pRoot != nullptr)
        {
            return false;
        }
        else
        {
            return true;
        }
    }

    void rightSingleRotation(CTreeNode* pNode)  //右边单旋转
    {
        /*
                10
              5    20
                 13  28
                        29

               20
            10    28
           5  13    29
        */
        CTreeNode *p10 = pNode;
        CTreeNode *p20 = pNode->m_pRight;
        CTreeNode *p13 = p20->m_pLeft;
        if (p10->m_pParents == nullptr)
        {
            m_pRoot = p20;
        }
        else
        {
            if (p10->m_pParents->m_pLeft == p10)
            {
                p10->m_pParents->m_pLeft = p20;
            }
            else
            {
                p10->m_pParents->m_pRight = p20;
            }
        }

        p20->m_pParents = p10->m_pParents;
        if (p13 != nullptr)
        {
            p13->m_pParents = p10;
        }
        p10->m_pParents = p20;
        p10->m_pRight = p13;
        p20->m_pLeft = p10;
        setHeight(p10);
        setHeight(p20);
        pNode = p20;
    }

    void leftSingleRotation(CTreeNode* pNode)  //左边单旋转
    {
        /*
                    20
                15     40
              12  18
            10

                    15
                  12  20
                10   18 40
        */
        CTreeNode *p20 = pNode;
        CTreeNode *p15 = p20->m_pLeft;
        CTreeNode *p18 = p15->m_pRight;
        if (p20->m_pParents == nullptr)
        {
            m_pRoot = p15;
        }
        else
        {
            if (p20->m_pParents->m_pLeft == p20)
            {
                p20->m_pParents->m_pLeft = p15;
            }
            else
            {
                p20->m_pParents->m_pRight = p15;
            }
        }

        p15->m_pParents = p20->m_pParents;
        p20->m_pParents = p15;
        if (p18 != nullptr)
        {
            p18->m_pParents = p20;
        }

        p15->m_pRight = p20;
        p20->m_pLeft = p18;
        setHeight(p20);
        setHeight(p15);
        pNode = p15;
    }

    void leftDoubleRotation(CTreeNode* pNode)  //左边双旋转
    {
        /*
                    20
                15     40
              12  18
                    19
         ------------------------- pNode->left rightSingle
        */
        rightSingleRotation(pNode->m_pLeft);
        /*
                    20
                18      40
              15  19
            12
        -------------------------- pNode leftSingle
                     18
                  15     20
                12    19    40

        */
        leftSingleRotation(pNode);
    }

    void rightDoubleRotation(CTreeNode* pNode)  //右边双旋转
    {
        /*
                10
             5      20
                  13  28
                12      
        -------------------- pNode->right leftSingle
        */
        leftSingleRotation(pNode->m_pRight);
        /*
                
                10
            5       13
                  12  20
                        28

                 13
              10   20
            5   12   29
        */
        rightSingleRotation(pNode);
    }
    
    void balance(CTreeNode* pNode) //平衡二叉树
    {
        setHeight(pNode);

        if (getLength(pNode->m_pLeft) - getLength(pNode->m_pRight) > 1) ////左边需要旋转
        {
            if (getLength(pNode->m_pLeft) -
                getLength(pNode->m_pLeft->m_pLeft) == 2 //双旋转
                )
            {
                leftDoubleRotation(pNode);
            }
            else if (getLength(pNode->m_pLeft) -
                getLength(pNode->m_pLeft->m_pLeft) == 1 //单旋转
                )
            {
                leftSingleRotation(pNode);
            }
            else
            {
                printf("未知旋转\r\n");
                system("pause");
            }

            return;
        }
        else if (getLength(pNode->m_pRight) - getLength(pNode->m_pLeft) > 1) //右边需要旋转
        {
            if (getLength(pNode->m_pRight) -
                getLength(pNode->m_pRight->m_pRight) == 2 //双旋转
                )
            {
                rightDoubleRotation(pNode);
            }
            else if (getLength(pNode->m_pRight) -
                getLength(pNode->m_pRight->m_pRight) == 1 //单旋转
                )
            {
                rightSingleRotation(pNode);
            }
            else
            {
                printf("未知旋转\r\n");
                system("pause");
            }

            return;
        }

    }

    void setHeight(CTreeNode* node) //设置高度
    {
        node->m_iHeight = getLength(node);
    }

    int getLength(CTreeNode* pNode) //获取高度
    {
        if (pNode == nullptr)
        {
            return 0;
        }

        if (pNode->m_pLeft == nullptr && pNode->m_pRight == nullptr)
        {
            return 1;
        }
        else if (pNode->m_pLeft == nullptr)
        {
            return pNode->m_pRight->m_iHeight + 1;
        }
        else if (pNode->m_pRight == nullptr)
        {
            return pNode->m_pLeft->m_iHeight + 1;
        }
        else
        {
            int iHeightNode1 = pNode->m_pLeft->m_iHeight;
            int iHeightNode2 = pNode->m_pRight->m_iHeight;
            return iHeightNode1 > iHeightNode2 ? iHeightNode1 + 1 : 
                iHeightNode2 + 1;
        }
    }
    
    void removeSameName(CTreeNode* pNode, CStudent *stu)
    {
        //获取父节点
        CTreeNode *pParents = pNode->m_pParents;
        //保存一下删除节点
        CTreeNode *pOld = pNode;
        //删除节点的前一个
        CTreeNode *pOldLast = nullptr;
        //寻找id和stu一样的节点
        while (pNode->m_pElement->m_uId != stu->m_uId)
        {
            pOldLast = pNode;
            pNode = pNode->m_pNext;
            if (pNode == nullptr)
            {
                printf("没有找到要删除的同名id\r\n");
                system("pause");
                return;
            }
        }
        /*
        [1][2][3], delete [1]-->[2][3]
        [1][2][3], delete [2]-->[1][3]
        [1][2][3], delete [3]-->[1][2]
        [1][2], delete [1]-->[2]
        [1][2], delete [2]-->[1]
        */
        //如果删除的同名id不为空表示为第一个
        if (pNode->m_pParents != nullptr
            ||
            m_pRoot == pNode
            )
        {
            pNode->m_pNext->m_pLeft = pNode->m_pLeft;
            pNode->m_pNext->m_pRight = pNode->m_pRight;
            pNode->m_pNext->m_pParents = pParents;
            pNode->m_pNext->m_iHeight = pNode->m_iHeight;

            if (m_pRoot != pNode)
            {
                if (pParents->m_pLeft == pNode)
                {
                    pParents->m_pLeft = pNode->m_pNext;
                }
                else
                {
                    pParents->m_pRight = pNode->m_pNext;
                }
            }
            else
            {
                m_pRoot = pNode->m_pNext;
            }

            delete pNode;
        }
        else
        {
            pOldLast->m_pNext = pNode->m_pNext;
            delete pNode;
        }
    }
private:
    CTreeNode *m_pRoot;         //树根
};
 //CControl.cpp
#include "CControl.h"
#define MAX_NAME_LENGTH 33
#define CHARZERO '\0'

CControl::CControl()
{
    m_pIdTree = nullptr;
    m_pNameTree = nullptr;
    initTree();
}

CControl::~CControl()
{
    if (m_pIdTree != nullptr)
    {
        delete m_pIdTree;
    }

    if (m_pNameTree != nullptr)
    {
        delete m_pNameTree;
    }

}

void CControl::start()
{
    while (true)
    {
        int nUserInputFunctionId = 0;
        menu();
        int nRet = scanf("%d", &nUserInputFunctionId);
        fflush(stdin);
        while (getchar() != '\n') { ; }
        if (nRet != 1)
        {
            printf("输入的功能id有问题,请重新输入\r\n");
            system("pause");
            continue;
        }

        switch (nUserInputFunctionId)
        {
        case 1:
            insert();
            break;
        case 2:
            remove();
            break;
        case 3:
            alert();
            break;
        case 4:
            search();
            break;
        case 0:
            printf("欢迎使用,再见\r\n");
            system("pause");
            return;
        default:
            printf("输入的功能id有问题,请重新输入\r\n");
            system("pause");
            break;
        }
    }
}

void CControl::menu()
{
    system("cls");
    printf("**********学生管理系统**********\r\n");
    printf("\t0.退出\r\n");
    printf("\t1.增加\r\n");
    printf("\t2.删除\r\n");
    printf("\t3.修改\r\n");
    printf("\t4.查询\r\n");
    printf("********************************\r\n");
    printf("输入对应的功能id执行操作:");
}

void CControl::createTestData()
{
    //初始化年月日,在1970年及其之后
    short unsigned int nTmpYear = 0;
    short unsigned int nhTmpMonth = 0;
    short unsigned int nhTmpDay = 0;
    int nLenForName = 0;
    char szName[MAX_NAME_LENGTH] = { CHARZERO };
    int nBigOrSmall = 0;
    char pCh = CHARZERO;
    char chGender = CHARZERO;
    unsigned int uId = 1;

    //如果文件不存在,则创建
    FILE *pOpenTest = fopen("data.bin", "rb+");
    if (pOpenTest == nullptr)
    {
        pOpenTest = fopen("data.bin", "wb+");
        fclose(pOpenTest);
        pOpenTest = nullptr;
    }
    else
    {
        fclose(pOpenTest);
        pOpenTest = nullptr;
    }
    FILE *pFile = fopen("data.bin", "rb+");

    if (pFile != nullptr)
    {
        srand((unsigned)time(NULL));
        for (int i = 0; i < 1000000; i++)
        {
            //日期
            nTmpYear = rand() % 50 + 1970;
            nhTmpMonth = rand() % 11 + 1;
            if (nhTmpMonth != 2)
            {
                nhTmpDay = rand() % 30 + 1;
            }
            else
            {
                nhTmpDay = rand() % 27 + 1;
            }

            //名字长度
            nLenForName = rand() % 31 + 1;
            //名字
            for (int i = 0; i < nLenForName; i++)
            {
                nBigOrSmall = rand() % 1;
                if (nBigOrSmall = 0)
                {
                    pCh = 'A' + rand() % 25;
                }
                else
                {
                    pCh = 'a' + rand() % 25;
                }
                szName[i] = pCh;
            }
            //性别
            chGender = rand() % 2 + 'x';

            fwrite(&szName, strlen(szName) + 1, 1, pFile);
            fflush(pFile);
            fwrite(&uId, sizeof(uId), 1, pFile);
            fflush(pFile);
            fwrite(&nTmpYear, sizeof(nTmpYear), 1, pFile);
            fflush(pFile);
            fwrite(&nhTmpMonth, sizeof(nhTmpMonth), 1, pFile);
            fflush(pFile);
            fwrite(&nhTmpDay, sizeof(nhTmpDay), 1, pFile);
            fflush(pFile);
            fwrite(&chGender, sizeof(chGender), 1, pFile);
            fflush(pFile);

            memset(szName, CHARZERO, sizeof(szName));
            uId++;
        }

        fclose(pFile);
        printf("创建测试数据成功\r\n");
        system("pause");
    }
}

void CControl::initTree()
{
    try
    {
        //初始化树,用时1分10秒左右
        printf("初始化树中,请稍后\r\n");
        CIO file;
        char ch = CHARZERO;
        CStudent *pStu = nullptr;
        CStudent *pStu2 = nullptr;
        m_pIdTree = new CBinaryTreeForId;
        m_pNameTree = new CBinaryTreeForName;
        CMyString *pStrName = nullptr;
        CMyString *pStrName2 = nullptr;
        CDate *pDate = nullptr;
        CDate *pDate2 = nullptr;
        char szBuf[2] = { CHARZERO };
        unsigned int uNum = 0U;
        file.seek(0L, SEEK_END);
        long lFileEnd = file.tell();
        file.seek(0L, SEEK_SET);
        float fPercentage = 0.1f;

        while (file.tell() != lFileEnd)
        {
            file.read(&ch, sizeof(char));

            if (ch != CHARZERO)
            {
                file.seek(-1L, SEEK_CUR);
                uNum++;
                pStu = new CStudent;
                pDate = new CDate;
                pStrName = new CMyString;
                pStu->m_lFileDeviationPosition = file.tell();
                do
                {
                    file.read(&szBuf, sizeof(char));
                    pStrName->myStrcat(szBuf);
                } while (strlen(szBuf) != 0);
                file.read(&pStu->m_uId, sizeof(pStu->m_uId));
                pStu->m_strName = *pStrName;
                file.read(&pDate->m_uYear, sizeof(pDate->m_uYear));
                file.read(&pDate->m_uMonth, sizeof(pDate->m_uMonth));
                file.read(&pDate->m_uDay, sizeof(pDate->m_uDay));
                pStu->m_dateBirthday = pDate;
                file.read(&pStu->m_chGende, sizeof(pStu->m_chGende));
                m_pIdTree->insert_n(*pStu);

                pDate2 = new CDate;
                pDate2->m_uYear = pDate->m_uYear;
                pDate2->m_uMonth = pDate->m_uMonth;
                pDate2->m_uDay = pDate->m_uDay;
                pStrName2 = new CMyString;
                pStrName2->myStrcpy(*pStrName);
                pStu2 = new CStudent(pStu->m_uId, *pStrName2, 
                    pDate2, pStu->m_chGende);
                m_pNameTree->insert(pStu2);
                
                //m_pIdTree->showMaxStuInfo();
                //m_pNameTree->printTreeMid();
                if (uNum >= (1000000.0f * fPercentage))
                {
                    printf("初始化%%%.2f\r\n", fPercentage * 100);
                    fPercentage = fPercentage + 0.1f;
                }

            }
        }

        //m_pIdTree->showMaxStuInfo();
        printf("初始化完成\r\n");
        system("pause");
    }
    catch (CException& e)
    {
        e.showError();
        system("pause");
    }

}


void CControl::insert(int id)
{
    int nId = 0U;
    char szName[MAX_NAME_LENGTH] = { CHARZERO };
    CDate *pDate = new CDate;
    char chGender = CHARZERO;
    bool bIdIsExist = false;
    int nDay = 0;
    int nMonth[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    fflush(stdin);
    int nRet = 0;

    try
    {
        if (id == 0U)
        {
            do
            {
                printf("请输入要增加的学生ID,不能重复必须是正数:");
                nRet = scanf("%d", &nId);
                fflush(stdin);
                while (getchar() != '\n') { ; }
                bIdIsExist = m_pIdTree->find_n(nId);
            } while (bIdIsExist || nRet != 1 || nId < 1);
        }
        else
        {
            nId = id;
        }
        do
        {
            if (id == 0U)
            {
                printf("请输入要增加的学生名字,最多%d个字节:", MAX_NAME_LENGTH - 1);
            }
            else
            {
                printf("请输入要修改的学生名字,最多%d个字节:", MAX_NAME_LENGTH - 1);
            }
            nRet = scanf("%32s", szName);
            fflush(stdin);
            while (getchar() != '\n') { ; }
        } while (nRet != 1);
        CMyString *pStrName = new CMyString;
        pStrName->myStrcat(szName);

        while (true)
        {
            if (id == 0U)
            {
                printf("请输入要增加的学生生日,八位数,如20190808:");
            }
            else
            {
                printf("请输入要修改的学生生日,八位数,如20190808:");
            }
            nRet = scanf("%d", &nDay);
            fflush(stdin);
            while (getchar() != '\n') { ; }
            if (nRet != 1)
            {
                continue;
            }
            pDate->m_uYear = nDay / 10000;
            if (pDate->m_uYear > 2019
                ||
                pDate->m_uYear < 1900
                )
            {
                continue;
            }
            pDate->m_uMonth = (nDay % 10000) / 100;
            if (pDate->m_uMonth > 12
                ||
                pDate->m_uMonth < 1
                )
            {
                continue;
            }
            pDate->m_uDay = nDay % 100;
            if (pDate->m_uYear % 400 == 0
                ||
                (
                    pDate->m_uYear % 4 == 0
                    &&
                    pDate->m_uYear % 100 != 0
                    )
                )
            {
                if (pDate->m_uMonth == 2)
                {
                    nMonth[1] = 29;
                }
            }
            else
            {
                nMonth[1] = 28;
            }

            if (pDate->m_uDay > nMonth[pDate->m_uMonth - 1]
                ||
                pDate->m_uDay < 1
                )
            {
                continue;
            }

            break;
        }

        do
        {
            if (id == 0U)
            {
                printf("请输入要增加的学生性别,x(女),y(男),z(未知):");
            }
            else
            {
                printf("请输入要修改的学生性别,x(女),y(男),z(未知):");
            }
            nRet = scanf("%c", &chGender);
            fflush(stdin);
            while (getchar() != '\n') { ; }
            if (nRet != 1)
            {
                continue;
            }
        } while (chGender != 'x' && chGender != 'y' && chGender != 'z');

        //保存学生信息
        CStudent *pStu = new CStudent;
        pStu->m_uId = nId;
        pStu->m_chGende = chGender;
        pStu->m_dateBirthday = pDate;
        pStu->m_strName = *pStrName;
        

        CIO file;
        file.seek(0L, SEEK_END);
        pStu->m_lFileDeviationPosition = file.tell();
        file.write(pStu->m_strName.getBuff(), pStu->m_strName.getLength() + 1);
        file.write(&pStu->m_uId, sizeof(pStu->m_uId));
        file.write(&pStu->m_dateBirthday->m_uYear, sizeof(unsigned short int));
        file.write(&pStu->m_dateBirthday->m_uMonth, sizeof(unsigned short int));
        file.write(&pStu->m_dateBirthday->m_uDay, sizeof(unsigned short int));
        file.write(&pStu->m_chGende, sizeof(char));
        m_pIdTree->insert_n(*pStu);

        CDate *pDate2 = new CDate;
        pDate2->m_uYear = pDate->m_uYear;
        pDate2->m_uMonth = pDate->m_uMonth;
        pDate2->m_uDay = pDate->m_uDay;
        CMyString *pStrName2 = new CMyString;
        pStrName2->myStrcpy(*pStrName);
        CStudent *pStu2 = new CStudent(pStu->m_uId, 
            *pStrName2, pDate2, pStu->m_chGende);
        m_pNameTree->insert(pStu2);
        if (id == 0U)
        {
            printf("增加成功\r\n");
            system("pause");
        }
    }
    catch (CException& e)
    {
        e.showError();
    }
    
}

void CControl::remove(int id)
{
    try
    {
        int nId = 0U;
        int nRet = 0;
        bool bIdIsExist = false;
        
        if (id == 0)
        {
            do
            {
                printf("请输入要删除的学生id:");
                nRet = scanf("%d", &nId);
                fflush(stdin);
                while (getchar() != '\n') { ; }
                if (nRet != 1 || nId < 1)
                {
                    printf("输入的学生id有问题\r\n");
                    continue;
                }
                bIdIsExist = m_pIdTree->find_n(nId);
            } while (!bIdIsExist);
        }
        else
        {
            nId = id;
        }
        CStudent *pStu = m_pIdTree->find_stu(nId);

        CIO file;
        file.seek(pStu->m_lFileDeviationPosition, SEEK_CUR);
        char ch = CHARZERO;
        for (unsigned i = 0; i < (pStu->m_strName.getLength() + 1); i++)
        {
            file.write(&ch, sizeof(ch));
        }
        unsigned int uWriteId = 0U;
        file.write(&uWriteId, sizeof(uWriteId));
        CDate date(0U,0U,0U);
        file.write(&date, sizeof(date));
        file.write(&ch, sizeof(ch));
        m_pNameTree->remove(pStu);
        m_pIdTree->remove_n(*pStu);

        if (id == 0)
        {
            printf("删除成功\r\n");
            system("pause");
        }
    }
    catch (CException& e)
    {
        e.showError();
    }
}

void CControl::alert()
{
    try
    {
        int nId = 0U;
        int nRet = 0;
        bool bIdIsExist = false;

        do
        {
            printf("请输入要更新的学生id:");
            nRet = scanf("%d", &nId);
            fflush(stdin);
            while (getchar() != '\n') { ; }
            if (nRet != 1 || nId < 1)
            {
                printf("输入的学生id有问题\r\n");
                continue;
            }
            bIdIsExist = m_pIdTree->find_n(nId);
        } while (!bIdIsExist);

        remove(nId);
        insert(nId);
        printf("修改成功\r\n");
        system("pause");
    }
    catch(CException& e)
    {
        e.showError();
    }
}

void CControl::search()
{
    unsigned int uUserSearchChose = 0U;
    int nRet = 0;

    try
    {
        printf("搜素方式,1.按id搜素,2.按姓名搜素\r\n");
        do
        {
            printf("请输入要搜素的方式:");
            nRet = scanf("%d", &uUserSearchChose);
            fflush(stdin);
            while (getchar() != '\n') { ; }
            if (nRet != 1 || 
                (
                    uUserSearchChose != 1U && uUserSearchChose != 2U)
                )
            {
                printf("搜素方式有问题\r\n");
                continue;
            }
            else
            {
                break;
            }
        } while (true);

        if (uUserSearchChose == 1U)
        {
            int nId = 0U;
            bool bIdIsExist = false;

            do
            {
                printf("请输入要搜素的学生id:");
                nRet = scanf("%d", &nId);
                fflush(stdin);
                while (getchar() != '\n') { ; }
                if (nRet != 1 || nId < 1)
                {
                    printf("输入的学生id有问题\r\n");
                    continue;
                }
                bIdIsExist = m_pIdTree->find_n(nId);
                break;
            } while (true);

            if (bIdIsExist == true)
            {
                CStudent* pStu = m_pIdTree->find_stu(nId);
                pStu->printfInfo();
            }
            else
            {
                printf("搜素的学生ID没找到\r\n");
            }
        }
        else if(uUserSearchChose == 2)
        {
            
            char szName[MAX_NAME_LENGTH] = { CHARZERO };
            int nRet = 0;

            do
            {
                printf("请输入要查找的用户名,最多%d字节\r\n", MAX_NAME_LENGTH - 1);
                nRet = scanf("%32s", szName);
                fflush(stdin);
                while (getchar() != '\n') { ; }
            } while (nRet != 1);

            CMyString str = szName;
            m_pNameTree->search(str);
        }
        else
        {
            throw CException(6);
        }
    }
    catch (CException& e)
    {
        e.showError();
    }

    system("pause");
}
0 条评论
发表一条评论