1

二分木に対してさまざまな操作を実行するプログラムを作成しました。insert()最初に、null ルート ポインターを設定し、ツリーに新しいノードを追加するいくつかの関数を呼び出します。

最後に、search()要求された構造ノードを見つけて返す関数を呼び出します。

insert()関数は、ルート ポインタへの参照と、ノード構造に変換されてツリーに追加される定数 int キーの 2 つのパラメータを取ります。

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


私の質問は -検索機能が機能しないのはなぜですか? エラーが表示されます - 戻り値の型が関数の型と一致しません。しかし、宣言にあるように、ポインタを返します!

また、"const"ここのキーワードは大丈夫ですか？

4

3 に答える 3

2

rootでありconst node*、戻り値はnode*です。に変更する必要がありますconst node*。

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

search非 const を返す関数が必要な場合は、非 constパラメーターnodeを取る必要があります。nodeオーバーロードを提供して、両方の可能性を可能にすることができます

node* search(node *root, const int key);
于 2013-04-20T09:51:17.960 に答える
1

同じポインターを返すため、const 引数と非 const 戻り値を持つことはできません。代わりに、const と non-const の 2 つのバージョンを記述します。

これは、const_cast が正当化される数少ないケースの 1 つです。検索関数の 2 つのバージョンを記述します。一方は 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-correctness に違反するため、これを行うことはできません。純粋なオブジェクトへのポインターを返すconstと、クライアントはそのオブジェクトを変更できます。

代わりに、関数が を返すようにする必要がありますconst node*。それか、root単にnode*.

于 2013-04-20T09:51:09.017 に答える