[本质上,我是如何使用insert
函数比较字符串的砖墙,没有考虑大小写,同时将相同的字符串插入其原始大小写。
这是我的insert
功能。
TreeNode* Tree::insert(TreeNode* node, string value) {
transform(value.begin(), value.end(), value.begin(), ::tolower);
if (node == nullptr) {
return newTreeNode(value);
}
if (node->data < value) {
node->left = insert(node->left, value);
}
else if(node-> data > value) {
node->right = insert(node->right, value);
}
else {
return node;
}
node->height = 1 + max(height(node->left), height(node->right));
return node;
}
这是我的树头文件:
struct TreeNode {
public:
TreeNode* left;
TreeNode* right;
string data;
};
class Tree {
public:
TreeNode * newTreeNode(string data);
TreeNode * insert(TreeNode* node, string value);
void lexographicPrint(TreeNode* root);
};
newTreeNode功能:
TreeNode* AvlTree::newTreeNode(string value) {
TreeNode* treeNode = new TreeNode();
treeNode->data = value;
treeNode->left = nullptr;
treeNode->right= nullptr;
treeNode->height = 1;
return treeNode;
}
打印功能:
void AvlTree::lexographicPrint(TreeNode* root) {
if (root != nullptr) {
lexographicPrint(root->right);
cout << root->data << " ";
lexographicPrint(root->left);
}
}
这目前可以按照我的要求进行,但事实上Tree包含所有小写的值,这显然是由于transform
函数的缘故。我尝试使用holdValue
,例如:
string holdValue;
if (isupper(value[0]) {
holdValue = value;
}
在函数顶部,用insert
替换所有holdValue
调用。当我仍然用value
进行比较时,为什么会更改树的顺序,我感到困惑。我希望它能起作用,但事实并非如此。我尚未通过Google搜索找到解决方案。
您可以使用不区分大小写的比较,而不是使用std::string
的<
。
bool ci_less(const std::string & lhs, const std::string & rhs) {
return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), [](char l, char r){ return std::to_lower(l) < std::tolower(r); });
}
TreeNode* Tree::insert(TreeNode* node, std::string value) {
if (node == nullptr) {
return newTreeNode(std::move(value));
}
if (ci_less(node->data, value)) {
node->left = insert(node->left, std::move(value));
}
else if(ci_less(value, node->data)) {
node->right = insert(node->right, std::move(value));
}
else {
return node;
}
node->height = 1 + max(height(node->left), height(node->right));
return node;
}
#include <algorithm>
,您需要std::lexicographical_compare
。
类似,您可以定义case insensitive string type
struct ci_char_traits : public std::char_traits<char> {
static char to_upper(char ch) {
return std::toupper((unsigned char) ch);
}
static bool eq(char c1, char c2) {
return to_upper(c1) == to_upper(c2);
}
static bool lt(char c1, char c2) {
return to_upper(c1) < to_upper(c2);
}
static int compare(const char* s1, const char* s2, size_t n) {
while ( n-- != 0 ) {
if ( to_upper(*s1) < to_upper(*s2) ) return -1;
if ( to_upper(*s1) > to_upper(*s2) ) return 1;
++s1; ++s2;
}
return 0;
}
static const char* find(const char* s, int n, char a) {
auto const ua (to_upper(a));
while ( n-- != 0 )
{
if (to_upper(*s) == ua)
return s;
s++;
}
return nullptr;
}
};
using ci_string = std::basic_string<char, ci_char_traits>;
本质上,您想存储大小写混合的值,但是将它们排序为小写。
您可以做两件事。
用a < b
和a > b
替换所有的case_insensitive_compare(a, b) < 0
和case_insensitive_compare(a, b) > 0
检查,其中case_insensitive_compare
看起来像:
// +ve => l > r
// 0 => l equivalent to r (possibly different case)
// -ve => l < r
int case_insensitive_compare(const std::string& l, const std::string& r) noexcept {
std::size_t max_size = std::max(l.size(), r.size());
for (std::size_t i = 0; i < max_size; ++i) {
int cmp = std::tolower(l[i]) - std::tolower(r[i]);
if (cmp != 0) return cmp;
}
return l.size() - r.size();
}
// Or in c++20
// std::weak_ordering::greater => l > r
// std::weak_ordering::equivalent => l equivalent to r
// std::weak_ordering::less => l < r
std::weak_ordering case_insensitive_compare(const std::string& l, const std::string& r) noexcept {
std::size_t max_size = std::max(l.size(), r.size());
for (std::size_t i = 0; i < max_size; ++i) {
auto cmp = std::tolower(l[i]) <=> std::tolower(r[i]);
if (cmp != 0) return cmp;
}
return l.size() <=> r.size();
}
您应该能够将其推广到任何比较器功能(对于Tree<T>
,比较器cmp(const T&, const T&) -> int
)
使您的TreeNode
存储一个键/值对,其中键是小写字符串,而值是大小写混合的字符串。如果需要使树存储另一个值,请将该值设为std::tuple<std::string, ValueType>
。