1

我编写了在二叉树上执行各种操作的程序。一开始我设置了空根指针，然后调用了几个insert()向树添加新节点的函数。

最后，我调用search()函数找到请求的结构节点并返回它。

insert()函数有两个参数 - 对根指针的引用和常量 int 键，它将被转换为节点结构并添加到树中

search()函数采用“恒定根指针” - 不是引用，因为我想直接对本地指针进行操作，并且我不希望更改它。它需要的另一个参数是 int key。

这是整个程序：

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


我的问题是 -为什么搜索功能不起作用？它显示错误 - 返回值类型与函数类型不匹配。但我归还了指针，就像声明中所说的那样！

另外，"const"这里的关键字可以吗？

4

3 回答 3

2

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);
于 2013-04-20T09:51:17.960 回答
1

由于您返回的是相同的指针，因此您不能有一个 const 参数和一个非常量返回。而是编写两个版本，一个 const 和一个非常量。

这是 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));
}
于 2013-04-20T09:54:03.623 回答
0

在里面search，变量root是一个const node*。但是，您试图将其作为node*. 你不能这样做，因为它会违反 const 正确性。如果您返回一个指向真正const对象的指针，那么客户端将能够修改该对象。

相反，您需要使函数返回一个const node*. 要么，要么root应该只是一个node*.

于 2013-04-20T09:51:09.017 回答