136 lines
3.2 KiB
C++
136 lines
3.2 KiB
C++
|
#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);
|
||
|
}
|
||
|
|
||
|
// 搜索二叉树的中序遍历
|
||
|
t.InOrder();
|
||
|
// 搜索二叉树的前序遍历
|
||
|
t.PreOrder();
|
||
|
// 搜索二叉树的后序遍历
|
||
|
t.PostOrder();
|
||
|
// 搜索二叉树的层序遍历
|
||
|
t.LevelOrder();
|
||
|
|
||
|
auto node = t.Find(5);
|
||
|
if (node != nullptr)
|
||
|
{
|
||
|
std::cout << node->_value << std::endl;
|
||
|
}
|
||
|
else
|
||
|
{
|
||
|
std::cout << "没找到" << std::endl;
|
||
|
}
|
||
|
|
||
|
auto pre = t.FindPredecessor(node);
|
||
|
if (pre != nullptr)
|
||
|
{
|
||
|
std::cout << node->_key << " 的前驱节点是: " << pre->_key << std::endl;
|
||
|
}
|
||
|
else
|
||
|
{
|
||
|
std::cout << "前驱节点为空" << std::endl;
|
||
|
}
|
||
|
|
||
|
auto suc = t.FindSuccessor(node);
|
||
|
if (suc != nullptr)
|
||
|
{
|
||
|
std::cout << node->_key << " 的后继节点是: " << suc->_key << std::endl;
|
||
|
}
|
||
|
else
|
||
|
{
|
||
|
std::cout << "后继节点为空" << std::endl;
|
||
|
}
|
||
|
|
||
|
// 1. 叶子
|
||
|
t.Erase(5);
|
||
|
t.InOrder();
|
||
|
|
||
|
// 左为空或者右为空
|
||
|
t.Erase(8);
|
||
|
t.Erase(1);
|
||
|
t.InOrder();
|
||
|
|
||
|
// 重复删除
|
||
|
t.Erase(5);
|
||
|
t.InOrder();
|
||
|
}
|
||
|
|
||
|
void test_BSTree_2()
|
||
|
{
|
||
|
BSTree<std::string, std::string> dict;
|
||
|
dict.Insert("sort", "排序");
|
||
|
dict.Insert("string", "字符串");
|
||
|
dict.Insert("vector", "向量");
|
||
|
dict.Insert("map", "映射");
|
||
|
dict.Insert("set", "集合");
|
||
|
dict.Insert("algorithm", "算法");
|
||
|
dict.Insert("iterator", "迭代器");
|
||
|
dict.Insert("stack", "栈");
|
||
|
dict.Insert("queue", "队列");
|
||
|
dict.Insert("list", "链表");
|
||
|
dict.Insert("deque", "双端队列");
|
||
|
dict.Insert("priority_queue", "优先级队列");
|
||
|
dict.Insert("binary_search", "二分查找");
|
||
|
dict.Insert("lower_bound", "下界");
|
||
|
dict.Insert("upper_bound", "上界");
|
||
|
|
||
|
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 << "没找到" << std::endl;
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
|
||
|
void test_BSTree_3()
|
||
|
{
|
||
|
std::string strArr[] = {"西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果",
|
||
|
"西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉",
|
||
|
"西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果",
|
||
|
"西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉"};
|
||
|
|
||
|
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;
|
||
|
}
|