Esencialmente, soy un muro de ladrillos en cuanto a cómo debo comparar cadenas con mi función insert, sin tener en cuenta las mayúsculas y minúsculas al insertar simultáneamente esas mismas cadenas con su caja original.

Aquí está mi función 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;
}

Aquí está mi archivo de encabezado de árbol:

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);
};

Nueva función TreeNode:

TreeNode* AvlTree::newTreeNode(string value) {
    TreeNode* treeNode = new TreeNode();
    treeNode->data = value;
    treeNode->left = nullptr;
    treeNode->right= nullptr;
    treeNode->height = 1;
    return treeNode;
}

Función de impresión:

void AvlTree::lexographicPrint(TreeNode* root) {
    if (root != nullptr) {
        lexographicPrint(root->right);
        cout << root->data << " ";
        lexographicPrint(root->left);
    }
}

Actualmente funciona como quiero, excepto por el hecho de que el Árbol contiene todos los valores en minúsculas, obviamente debido a la función transform. He intentado usar un holdValue, así:

string holdValue;
if (isupper(value[0]) {
    holdValue = value;
}

En la parte superior de mi función, reemplazando todas las llamadas insert con holdValue. No estoy seguro de por qué eso cambia el orden de mi árbol cuando todavía se hacen comparaciones con value. Esperaba que eso funcionara, pero no es así. Todavía tengo que encontrar una solución a través de las búsquedas de Google.

0
Suede 24 feb. 2020 a las 02:14

2 respuestas

La mejor respuesta

En lugar de usar std::string 's <, puede usar una comparación que no distinga entre mayúsculas y minúsculas.

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;
}

Necesitará #include <algorithm> para std::lexicographical_compare.

De manera similar, podría definir un tipo de cadena insensible a mayúsculas y minúsculas

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>;
1
Caleth 23 feb. 2020 a las 23:50

Esencialmente, desea almacenar valores de mayúsculas y minúsculas, pero ordenados como si fueran minúsculas.

Hay dos cosas que puedes hacer.

  1. Reemplace todos sus cheques a < b y a > b con case_insensitive_compare(a, b) < 0 y case_insensitive_compare(a, b) > 0, donde case_insensitive_compare se parece a:

    // +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();
    }
    

    Debería poder generalizar esto a cualquier función de comparación (para un Tree<T>, un comparador cmp(const T&, const T&) -> int)

  2. Haga que su TreeNode almacene un par clave / valor, donde la clave es la cadena en minúsculas y el valor es la cadena de mayúsculas y minúsculas. Si necesita hacer que el árbol almacene otro valor, haga que el valor sea std::tuple<std::string, ValueType>.

1
Artyer 23 feb. 2020 a las 23:35