BST 삽입, 삭제, 높은 차원 추구 실현

BST 삽입, 삭제, 높은 차원 추구 실현

제목.

코드

/************************************************************************* > File Name: BinarySearchTree.cpp > Author: > Mail: > Created Time: Tue 27 Sep 2016 09:12:54 PM CST ************************************************************************/

#include<iostream>
#include<queue>
#include<string>
#include<sstream>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {};
};

class Tree
{
public:
    void Insert(int v);
    void Delete(int v);
    int  GetHeight();
    void TraverseByLevelOrder();
    Tree() { root = new (TreeNode*); *root = nullptr; };
    ~Tree() { while(*root) { Delete((*root)->val); } delete root; root = nullptr; };

private:
    void Transplant(TreeNode* pNode, TreeNode* pParent, TreeNode* pReplace);
    TreeNode* FindMin(TreeNode* pNode, TreeNode** ppParent);
    void Delete(TreeNode* pNode, TreeNode* pParent);
    int GetHeight(TreeNode* pNode);
    void TraverseByLevelOrder(TreeNode* pNode);
    TreeNode** root;
};

void Tree::Insert(int v)
{
    TreeNode* pNode = new TreeNode(v);

    if(*root == nullptr)
    {
        *root = pNode;
    }
    else
    {
        TreeNode* pParent = nullptr;
        TreeNode* pCur = *root;
        while(pCur)
        {
            pParent = pCur;
            if(pNode->val <= pCur->val)
            {
                pCur = pCur->left;
            }
            else
            {
                pCur = pCur->right;
            }
        }
        if(pNode->val <= pParent->val)
        {
            pParent->left = pNode;
        }
        else
        {
            pParent->right = pNode;
        }
    }
}

TreeNode* Tree::FindMin(TreeNode* pNode, TreeNode** ppParent)
{
    while(pNode->left)
    {
        ppParent = &pNode;
        pNode = pNode->left;
    }
    return pNode;
}

void Tree::Transplant(TreeNode* pNode, TreeNode* pParent, TreeNode* pReplace)
{
    if(pParent)
    {
        if(pNode == pParent->left)
        {
            pParent->left = pReplace;
        }
        else
        {
            pParent->right = pReplace;
        }
    }
    else
    {
        *root = pReplace;
    }
}

void Tree::Delete(TreeNode* pNode, TreeNode* pParent)
{
    if(pNode->left == nullptr)
    {
        Transplant(pNode, pParent, pNode->right);
    }
    else if (pNode->right == nullptr)
    {
        Transplant(pNode, pParent, pNode->left);
    }
    else
    {
        TreeNode** ppParent = nullptr;
        TreeNode* RightMin = FindMin(pNode->right, ppParent);
        if(RightMin != pNode->right)           /*                         */
        {
            Transplant(RightMin, *ppParent, RightMin->right);
            RightMin->right = pNode->right;
        }
        Transplant(pNode, pParent, RightMin);
        RightMin->left = pNode->left;
    }

    delete pNode;
    pNode = nullptr;
}

void Tree::Delete(int v)
{
    if(*root)
    {
        TreeNode* pParent = nullptr;
        TreeNode* pNode = *root;
        while(pNode)
        {
            if(pNode->val == v)
                Delete(pNode, pParent);
            else
            {
                pParent = pNode;
                if(pNode->val < v)
                {
                    pNode = pNode->right;
                }
                else
                {
                    pNode = pNode->left;
                }
            }
        }
    }
}


int Tree::GetHeight(TreeNode* pNode)
{
    if(pNode == nullptr)
        return 0;

    return max(GetHeight(pNode->left), GetHeight(pNode->right)) + 1;
}


int Tree::GetHeight()
{
    int h = 0;
    if(*root)
    {
        TreeNode* pCur = *root;
        h =  GetHeight(pCur);
    }
    return h;
}


void Tree::TraverseByLevelOrder(TreeNode* pNode)
{
    queue<TreeNode*> myQueue;
    myQueue.push(pNode);
    while(!myQueue.empty())
    {
        TreeNode* pCur = myQueue.front();
        myQueue.pop();
        cout<<pCur->val<<'\t';
        if(pCur->left)
            myQueue.push(pCur->left);
        if(pCur->right)
            myQueue.push(pCur->right);

    }
    cout<<endl;
}

void Tree::TraverseByLevelOrder()
{
    if(*root)
    {
        TreeNode* pCur = *root;
        TraverseByLevelOrder(pCur);
    }
}

int main()
{
    string command;
    stringstream ss;
    Tree BST;
    while(getline(cin, command))
    {
        char action;
        int parameter;
        ss.str(command);
        ss.clear();
        ss>>action;
        switch(action)
        {
            case 'I':
            {
                ss>>parameter;
                BST.Insert(parameter);
                break;
            }
            case 'D':
            {
                ss>>parameter;
                BST.Delete(parameter);
                break;
            }
            case 'H':
            {
                cout<<BST.GetHeight()<<endl;
                break;
            }
            case 'B':
            {
                BST.TraverseByLevelOrder();
                break;
            }
            default:
                break;
        }
    }
    return 0;
}