二叉树

项目1

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

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

        }
        int data;//数据
        struct BiTNode *lchild, *rchild;//左右孩子指针
    }BiTNode, *BiTNodePt;

public:
    BitTree();
    ~BitTree();

public:
    // 递归的方法遍历二叉树 [12/12/2020 wangy]
    // 前序遍历：根左右
    void PreOrderTraverse(BiTNode* T);

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

    // 后续遍历
    void PostOrderTraverse(BiTNode* T);

    // 判断一颗二叉树是否为完全二叉树


    // 二叉树的镜像转换
    BiTNode* MirrorTree(BiTNode* T);

    // 递归实现：左子树叶子结点个数+右子树叶子结点个数
    size_t GetLeefCount(BiTNode* T);

    // 获取第K层节点个数
    size_t GetKLevelCount(BiTNode* T,size_t k);

    // 获取二叉树的深度
    size_t GetHeight(BiTNode* T);

    // 查找指定数据
    BiTNode*  FindData(BiTNode*  pRoot, const int& data);

    // 二叉树的复制
    BiTNode* CopyBinTree(BiTNode* T);
};

BitTree::BitTree()
{
}


BitTree::~BitTree()
{
}

void BitTree::PreOrderTraverse(BiTNode* T)
{
    if (T==NULL)
    {
        return;
    }
    // 输出结点
    std::cout << T->data;

    // 遍历左子树
    PreOrderTraverse(T->lchild);

    // 遍历右子树
    PreOrderTraverse(T->rchild);
    //////////////////////////////////////////////////////////////////////////
    //非递归实现
    std::stack<BiTNode*>s;

    s.push(T);

    while (!s.empty())
    {
        BiTNode* cur = s.top();
        s.pop();
        while (cur != nullptr)
        {
            std::cout << cur->data;// 访问当前节点

            if (cur->rchild)
            {
                s.push(cur->rchild);// 保存右节点
            }

            cur = cur->lchild;  // 继续访问左节点
        }
    }
}

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

    // 输出结点
    std::cout << T->data;

    // 遍历右子树
    InOrderTraverse(T->rchild);
    //////////////////////////////////////////////////////////////////////////
    // 非递归实现
    //非递归实现
    std::stack<BiTNode*>s;

    BiTNode* cur = T;
    while (!s.empty() &&cur)
    {
        // 保存所有根左子节点
        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);

    // 输出结点
    std::cout << T->data;

    //////////////////////////////////////////////////////////////////////////
    // 非递归实现

    stack<BiTNode*>s;//存放所有节点
    BiTNode* pCur = T;
    BiTNode* prev = NULL;
    while (pCur || !s.empty())
    {
        while (pCur&&pCur != prev)  //存放左侧路径所有节点
        {
            s.push(pCur);            //当左子树未被标记时入栈
            pCur = pCur->lchild;
        }
        BiTNode* pTop = s.top();
        if (NULL == pTop->rchild || prev == pTop->rchild)//如果栈顶元素的右子树为空，并且已经被访问过
        {
            cout << pTop->data << " ";          //则输出该栈顶元素并出栈
            prev = pTop;
            s.pop();
            if (!s.empty())
                pCur = s.top();
            else
                return; //当栈为空时，退出
        }
        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);//递归镜像右子树
    }

    //////////////////////////////////////////////////////////////////////////
    // 非递归实现
    stack<BiTNode*>s;//存放所有节点
    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;
    //拷贝根节点
    BiTNode* pNewNode = new BiTNode(pRoot->data);
    //拷贝左子树
    if (pRoot->lchild)
        pNewNode->lchild = CopyBinTree(pRoot->lchild);
    //拷贝右子树
    if (pRoot->rchild)
        pNewNode->rchild = CopyBinTree(pRoot->rchild);

    return pNewNode;
}