Передача «постоянных указателей» на функции

Question

Я написал программу, которая выполняет различные операции над двоичным деревом. В начале я устанавливаю нулевой корневой указатель, затем вызываю пару функций insert(), которые добавляют новые узлы в дерево.

Наконец, я вызываю функцию search(), которая находит запрашиваемый узел структуры и возвращает его.

---

insert() функция принимает два параметра - ссылку на корневой указатель, и постоянный INT ключ, который будет преобразован в структуре узла и добавляется к дереву

search() функция принимает «постоянный корневой указатель» - а не ссылку, потому что я хочу напрямую работать с локальным указателем, и я не хочу, чтобы это было изменено. Другим аргументом, который он принимает, является ключ int.

---

Это целая программа:

#include <iostream> 

struct node 
{ 
    node *p; // parent 
    node *left, *right; 
    int key; 
}; 

void insert(node *&root, const int key) 
{ 
    node newElement = {}; 
    newElement.key = key; 

    node *y = NULL; 
    while(root) 
    { 
     if(key == root->key) exit(EXIT_FAILURE); 
     y = root; 
     root = (key < root->key) ? root->left : root->right; 
    } 

    newElement.p = y; 

    if(!y) root = &newElement; 
    else if(key < y->key) y->left = &newElement; 
    else y->right = &newElement; 
} 

node* search(const node *root, const int key) 
{ 
    while((root) && (root->key != key)) 
     root = (key < root->key) ? root->left : root->right; 

    return root; 
} 

int main() 
{ 
    using namespace std; 
    node *root = NULL; 
    insert(root, 5); 
    insert(root, 2); 

    cout << search(root, 5)->key << endl; 
    return 0; 
} 

Мой вопрос - Почему не ищет работу функции? Он отображает тип возвращаемого значения ошибки, не соответствующий типу функции. Но я возвращаю poiner, как это говорится в декларации!

Также есть "const" ключевое слово здесь o.k.?

Answer 1

root - const node*, а ваше возвращаемое значение - node*. Его следует заменить на const node*.

const node* search(const node *root, const int key); 

Если вам нужна search функцию, чтобы вернуть вам неконстантную node, то она должна принять неконстантную node параметр. Вы можете обеспечить перегрузку, чтобы обе возможности

node* search(node *root, const int key); 

Answer 2

Внутри search переменная root является const node*. Однако вы пытаетесь вернуть его как node*. Вы не можете этого сделать, потому что это нарушит const-correctness. Если вы вернули указатель на подлинно const объект, клиент сможет затем изменить этот объект.

Вместо этого вам необходимо вернуть функцию const node*. Либо это, либо root должно быть просто node*.

Answer 3

Поскольку вы возвращаете тот же указатель, вы не можете иметь константный аргумент и неконстантное возвращение. Вместо этого напишите две версии, одну константу и одну неконстантную.

Это один из немногих случаев, когда const_cast оправдан. Напишите две версии вашей функции поиска, можно вызвать другую, используя const_cast.

const node* search(const node *root, const int key) 
{ 
    while((root) && (root->key != key)) 
     root = (key < root->key) ? root->left : root->right; 

    return root; 
} 

node* search(node *root, const int key) 
{ 
    return const_cast<node *>(search(const_cast<const node *>(root), key)); 
}