BSTree/Windows_BSTree/BSTree.cpp

#include "BSTree.hpp"
#include <string>

using namespace Lenyiin;

void test_BSTree_1()
{
    BSTree<int, int> t;
    int a[] = { 5,3,4,1,7,8,2,6,0,9 };
    for (const auto& e : a)
    {
        t.Insert(e, e);
    }

    // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    t.InOrder();
    // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ǰ<EFBFBD><C7B0><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    t.PreOrder();
    // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĺ<EFBFBD><C4BA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    t.PostOrder();
    // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>IJ<EFBFBD><C4B2><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    t.LevelOrder();

    auto node = t.Find(5);
    if (node != nullptr)
    {
        std::cout << node->_value << std::endl;
    }
    else
    {
        std::cout << "û<EFBFBD>ҵ<EFBFBD>" << std::endl;
    }

    auto pre = t.FindPredecessor(node);
    if (pre != nullptr)
    {
        std::cout << node->_key << " <20><>ǰ<EFBFBD><C7B0><EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD>: " << pre->_key << std::endl;
    }
    else
    {
        std::cout << "ǰ<EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>Ϊ<EFBFBD><EFBFBD>" << std::endl;
    }

    auto suc = t.FindSuccessor(node);
    if (suc != nullptr)
    {
        std::cout << node->_key << " <20>ĺ<EFBFBD><C4BA>̽ڵ<CCBD><DAB5><EFBFBD>: " << suc->_key << std::endl;
    }
    else
    {
        std::cout << "<EFBFBD><EFBFBD><EFBFBD>̽ڵ<EFBFBD>Ϊ<EFBFBD><EFBFBD>" << std::endl;
    }

    // 1. Ҷ<><D2B6>
    t.Erase(5);
    t.InOrder();

    // <20><>Ϊ<EFBFBD>ջ<EFBFBD><D5BB><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><CEAA>
    t.Erase(8);
    t.Erase(1);
    t.InOrder();

    // <20>ظ<EFBFBD>ɾ<EFBFBD><C9BE>
    t.Erase(5);
    t.InOrder();
}

void test_BSTree_2()
{
    BSTree<std::string, std::string> dict;
    dict.Insert("sort", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>");
    dict.Insert("string", "<EFBFBD>ַ<EFBFBD><EFBFBD><EFBFBD>");
    dict.Insert("vector", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>");
    dict.Insert("map", "ӳ<EFBFBD><EFBFBD>");
    dict.Insert("set", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>");
    dict.Insert("algorithm", "<EFBFBD>㷨");
    dict.Insert("iterator", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>");
    dict.Insert("stack", "ջ");
    dict.Insert("queue", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>");
    dict.Insert("list", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>");
    dict.Insert("deque", "˫<EFBFBD>˶<EFBFBD><EFBFBD><EFBFBD>");
    dict.Insert("priority_queue", "<EFBFBD><EFBFBD><EFBFBD>ȼ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>");
    dict.Insert("binary_search", "<EFBFBD><EFBFBD><EFBFBD>ֲ<EFBFBD><EFBFBD><EFBFBD>");
    dict.Insert("lower_bound", "<EFBFBD>½<EFBFBD>");
    dict.Insert("upper_bound", "<EFBFBD>Ͻ<EFBFBD>");

    dict.InOrder();

    std::string str;
    while (std::cin >> str)
    {
        BSTreeNode<std::string, std::string>* ret = dict.Find(str);
        if (ret)
        {
            std::cout << ret->_key << ":" << ret->_value << std::endl;
        }
        else
        {
            std::cout << "û<EFBFBD>ҵ<EFBFBD>" << std::endl;
        }
    }
}

void test_BSTree_3()
{
    std::string strArr[] = { "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "<EFBFBD>㽶", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ӣ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>",
                       "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "<EFBFBD>㽶", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ӣ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "<EFBFBD>㽶",
                       "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ӣ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "<EFBFBD>㽶", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ӣ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>",
                       "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "<EFBFBD>㽶", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ӣ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "ƻ<EFBFBD><EFBFBD>", "<EFBFBD><EFBFBD><EFBFBD><EFBFBD>", "<EFBFBD>㽶" };

    BSTree<std::string, int> countTree;

    for (auto str : strArr)
    {
        BSTreeNode<std::string, int>* ret = countTree.Find(str);
        if (ret == nullptr)
        {
            countTree.Insert(str, 1);
        }
        else
        {
            ret->_value++;
        }
    }

    countTree.InOrder();
}

int main()
{
    test_BSTree_1();
    //test_BSTree_2();
    test_BSTree_3();

    return 0;
}