項目1

class BitTree
{
public:
    typedef struct BiTNode
    {
        BiTNode()
        {

        }
        BiTNode(int data_in)
            :data(data_in)
        {

        }
        int data;//數(shù)據(jù)
        struct BiTNode *lchild, *rchild;//左右孩子指針
    }BiTNode, *BiTNodePt;

public:
    BitTree();
    ~BitTree();

public:
    // 遞歸的方法遍歷二叉樹 [12/12/2020 wangy]
    // 前序遍歷：根左右
    void PreOrderTraverse(BiTNode* T);

    // 中序遍歷:左根右
    void InOrderTraverse(BiTNode* T);

    // 后續(xù)遍歷
    void PostOrderTraverse(BiTNode* T);

    // 判斷一顆二叉樹是否為完全二叉樹


    // 二叉樹的鏡像轉(zhuǎn)換
    BiTNode* MirrorTree(BiTNode* T);

    // 遞歸實現(xiàn)：左子樹葉子結(jié)點個數(shù)+右子樹葉子結(jié)點個數(shù)
    size_t GetLeefCount(BiTNode* T);

    // 獲取第K層節(jié)點個數(shù)
    size_t GetKLevelCount(BiTNode* T,size_t k);

    // 獲取二叉樹的深度
    size_t GetHeight(BiTNode* T);

    // 查找指定數(shù)據(jù)
    BiTNode*  FindData(BiTNode*  pRoot, const int& data);

    // 二叉樹的復(fù)制
    BiTNode* CopyBinTree(BiTNode* T);
};

BitTree::BitTree()
{
}


BitTree::~BitTree()
{
}

void BitTree::PreOrderTraverse(BiTNode* T)
{
    if (T==NULL)
    {
        return;
    }
    // 輸出結(jié)點
    std::cout << T->data;

    // 遍歷左子樹
    PreOrderTraverse(T->lchild);

    // 遍歷右子樹
    PreOrderTraverse(T->rchild);
    //////////////////////////////////////////////////////////////////////////
    //非遞歸實現(xiàn)
    std::stack<BiTNode*>s;

    s.push(T);

    while (!s.empty())
    {
        BiTNode* cur = s.top();
        s.pop();
        while (cur != nullptr)
        {
            std::cout << cur->data;// 訪問當(dāng)前節(jié)點

            if (cur->rchild)
            {
                s.push(cur->rchild);// 保存右節(jié)點
            }

            cur = cur->lchild;  // 繼續(xù)訪問左節(jié)點
        }
    }
}

void BitTree::InOrderTraverse(BiTNode* T)
{
    if (T==NULL)
    {
        return;
    }
    // 遍歷左子樹
    InOrderTraverse(T->lchild);

    // 輸出結(jié)點
    std::cout << T->data;

    // 遍歷右子樹
    InOrderTraverse(T->rchild);
    //////////////////////////////////////////////////////////////////////////
    // 非遞歸實現(xiàn)
    //非遞歸實現(xiàn)
    std::stack<BiTNode*>s;

    BiTNode* cur = T;
    while (!s.empty() &&cur)
    {
        // 保存所有根左子節(jié)點
        while (cur)
        {
            s.push(cur);
            cur = cur->lchild;
        }
        cur = s.top();
        s.pop();
        std::cout << cur->data;

        cur = cur->rchild;// 保存所有右子樹
    }
}

void BitTree::PostOrderTraverse(BiTNode* T)
{
    if (T == NULL)
    {
        return;
    }
    // 遍歷左子樹
    InOrderTraverse(T->lchild);

    // 遍歷右子樹
    InOrderTraverse(T->rchild);

    // 輸出結(jié)點
    std::cout << T->data;

    //////////////////////////////////////////////////////////////////////////
    // 非遞歸實現(xiàn)

    stack<BiTNode*>s;//存放所有節(jié)點
    BiTNode* pCur = T;
    BiTNode* prev = NULL;
    while (pCur || !s.empty())
    {
        while (pCur&&pCur != prev)  //存放左側(cè)路徑所有節(jié)點
        {
            s.push(pCur);            //當(dāng)左子樹未被標(biāo)記時入棧
            pCur = pCur->lchild;
        }
        BiTNode* pTop = s.top();
        if (NULL == pTop->rchild || prev == pTop->rchild)//如果棧頂元素的右子樹為空，并且已經(jīng)被訪問過
        {
            cout << pTop->data << " ";          //則輸出該棧頂元素并出棧
            prev = pTop;
            s.pop();
            if (!s.empty())
                pCur = s.top();
            else
                return; //當(dāng)棧為空時，退出
        }
        pCur = pCur->rchild;
    }
}

BitTree::BiTNode* BitTree::MirrorTree(BiTNode* T)
{
    if (T==nullptr)
    {
        return nullptr;
    }
    else if(T->rchild==nullptr && T->lchild==nullptr)
    {
        return T;
    }
    else
    {
        swap(T->rchild,T->lchild);
        MirrorTree(T->lchild);//遞歸鏡像左子樹
        MirrorTree(T->rchild);//遞歸鏡像右子樹
    }

    //////////////////////////////////////////////////////////////////////////
    // 非遞歸實現(xiàn)
    stack<BiTNode*>s;//存放所有節(jié)點
    s.push(T);

    while (!s.empty())
    {
        BiTNode* curr = s.top();
        s.pop();

        swap(curr->lchild, curr->rchild);

        if (curr->lchild)
        {
            s.push(curr->lchild);//遍歷左子樹
        }
        else
        {
            s.push(curr->rchild);//遍歷右子樹
        }
    }
}

size_t BitTree::GetLeefCount(BiTNode* T)
{
    if (T==nullptr)
    {
        return 0;
    }
    if (T->lchild==nullptr && T->rchild==nullptr)
    {
        return 1;
    }

    return GetLeefCount(T->lchild) + GetLeefCount(T->rchild);
}

size_t BitTree::GetKLevelCount(BiTNode* T, size_t k)
{
    if (T==nullptr || k<0)
    {
        return 0;
    }
    if (k==0)
    {
        return 1;
    }
    return GetKLevelCount(T->lchild, k - 1) + GetKLevelCount(T->rchild, k - 1);
}

size_t BitTree::GetHeight(BiTNode* T)
{
    if (T == nullptr)
    {
        return 0;
    }

    return GetHeight(T->lchild) > GetHeight(T->rchild) ? GetHeight(T->lchild) : GetHeight(T->rchild) + 1;
}

BitTree::BiTNode* BitTree::FindData(BiTNode* pRoot, const int& data)
{
    if (pRoot==nullptr)
    {
        return pRoot;
    }

    if (pRoot->data==data)
    {
        return pRoot;
    }

    BiTNode* ret= FindData(pRoot->lchild, data);
    if (ret!=nullptr)
    {
        return ret;
    }
    else
    {
        BiTNode* cur = FindData(pRoot->rchild, data);
        if (cur != nullptr)
        {
            return cur;
        }
    }
    return nullptr;
}

BitTree::BiTNode* BitTree::CopyBinTree(BiTNode* pRoot)
{
    if (NULL == pRoot)
        return NULL;
    //拷貝根節(jié)點
    BiTNode* pNewNode = new BiTNode(pRoot->data);
    //拷貝左子樹
    if (pRoot->lchild)
        pNewNode->lchild = CopyBinTree(pRoot->lchild);
    //拷貝右子樹
    if (pRoot->rchild)
        pNewNode->rchild = CopyBinTree(pRoot->rchild);

    return pNewNode;
}