1

免責事項：これは割り当て用です。私は明示的なコードの答えを求めているのではなく、コードが機能しない理由を理解するのに役立つだけです。

基本的なバイナリ検索ツリーを実装しようとしていますが、_addNode(...)関数に問題があります。

ここに問題があります。デバッガーを使用してコードをウォークスルーすると、リーフノードが両側（左と右）に無限に作成されていることに気付きます。そのため、ルートの作成を除いて、リーフノードがであるポイントはありませんNULL。NULL問題は、リーフがある場所に値が見つかるたびに、プログラムに新しいノードを作成するように要求していることです。したがって、NULL値がまったくない場合、新しい葉が作成されることはありませんよね？

私が遭遇している他の問題は私のcompare(...)関数にあります。デバッガーでステップスルーすると、関数を数回繰り返すことが示され、実際に値が返されることはありません。呼び出し元の関数に戻ると、関数に戻り、compare(...)無限にループします。繰り返しますが、各ステートメントに有効なreturnステートメントがあることを考えると、なぜこれが発生しているのかわかりませんif。

これがおそらく必要になるすべてのコードです。何かを忘れてしまった場合は、お知らせください。投稿します。

struct Node {
    TYPE         val;
    struct Node *left;
    struct Node *right;
};

struct BSTree {
    struct Node *root;
    int          cnt;
};

struct data {
    int number;
    char *name;
};

int compare(TYPE left, TYPE right)
{
    assert(left != 0);
    assert(right != 0);

    struct data *leftData = (struct data *) left;
    struct data *rightData = (struct data *) right;

    if (leftData->number < rightData->number) {
        return -1;
    }
    if (leftData->number > rightData->number) {
        return 1;
    } else return 0;
}

void addBSTree(struct BSTree *tree, TYPE val)
{
    tree->root = _addNode(tree->root, val);
    tree->cnt++;
}

struct Node *_addNode(struct Node *cur, TYPE val)
{
    assert(val != 0);

    if(cur == NULL) {
        struct Node * newNode = malloc(sizeof(struct Node));
        newNode->val = val;
        return newNode;
    }
    if (compare(val, cur->val) == -1) {
        //(val < cur->val)
        cur->left = _addNode(cur->left, val);
    } else cur->right = _addNode(cur->right, val);

    return cur;
}

編集：以下の関数を追加します

int main(int argc, char *argv[])
{
    struct BSTree *tree = newBSTree();

    /*Create value of the type of data that you want to store*/
    struct data myData1;
    struct data myData2;
    struct data myData3;
    struct data myData4;

    myData1.number = 5;
    myData1.name = "rooty";
    myData2.number = 1;
    myData2.name = "lefty";
    myData3.number = 10;
    myData3.name = "righty";
    myData4.number = 3;
    myData4.name = "righty";

    /*add the values to BST*/
    addBSTree(tree, &myData1);
    addBSTree(tree, &myData2);
    addBSTree(tree, &myData3);
    addBSTree(tree, &myData4);

    /*Print the entire tree*/
    printTree(tree);
    /*(( 1 ( 3 ) ) 5 ( 10 ))*/
    return 1;
}
4

2 に答える 2

4

NULLたぶん、あなたは右と左から右に設定してみることができますmalloc：

struct Node * newNode = malloc(sizeof(struct Node));
newNode->left = NULL;
newNode->right = NULL;
于 2012-11-29T20:18:46.333 に答える
1

ここでこの行を確認してください（または左側の対応する行）：

cur-> right = _addNode（cur-> right、val）;

cur-> right == 0の場合、問題ありません。ただし、cur-> right！= 0の場合、そこにあったノードは_addNodeの戻り値に置き換えられます。これは、最終的にはブランチ全体ではなく、1つのノードになります。

memset（newNode、0、sizeof（struct Node））を使用して、mallocの後に構造体の値を明示的に0にするのが好きです。他の人は同意しないかもしれません。

于 2012-11-29T20:26:50.170 に答える