1

私は長い間ポインタ演算を行っていなかったので、Cで手を試し、単純な二分探索木を実行することにしました。しかし、削除のコツをつかむことはできません。これらの線に沿った何かが私が期待するように機能します：

typedef struct Node{
    int value;
    struct Node *left;
    struct Node *right;
}Node;

typedef struct Tree{
    struct Node* root;
}Tree;

int main(){
    Tree *tree = createTree(); 

    treeInsert(10, tree);    // Inserts 10 at root
    treeInsert(30, tree);    // Inserts 30 to root->right
    treeInsert(5, tree);     // Inserts 5 to root->left
    treeInsert(7, tree);     // Inserts 7 to root->left->right
    treeInsert(12, tree);    // Inserts 12 to root->right->left

    // Removes Node "7" from the tree successfully
    free(tree->root->left->right);   // Free memory for this node in the tree
    tree->root->left->right = NULL;  // Set the pointer to NULL

    return 0;
}

ノードに関連付けられているメモリを解放し、それをNULLにポイントする関数を記述したいのですがnodeDelete(Node *killNode)、期待どおりに機能しないことがわかりました。

int main(){
   // ... snip ...

   Node *kill = tree->root->left->right  // Points kill node to Node "7"
   free(kill);                           // Deallocates memory
   kill = NULL;                          // Points kill to NULL, but keeps 
                                         //   tree->root->left->right **undefined** 
   // ... snip ...
}

私の問題は、killNULLを指していることを伝えていることだと思います。これにより、ツリー内のノードから切断され、元のノードポインタに影響を与えません。tree->root->left->right代わりにNULLをポイントしたいことをどのように伝えることができますkillか？この場合、ポインターからポインターが必要ですか？

4

2 に答える 2

2

tree->root->left->rightはい、そのノードを削除する場合は、に設定する必要がありますNULL。これは、そのポインタの値を削除関数に渡すことはできないことを意味します。

2つのオプションがあります。削除するノードの親へのポインターと、削除する子に関する情報のいずれかを渡すことができます。

nodeDelete(Node *parent, int kill_right)
{
    Node *kill;

    if (kill_right) {
        kill = parent->right;
        parent->right = NULL;
    } else {
        kill = parent->left;
        parent->left = NULL;
    }

    free(kill);
}

この場合、を呼び出しますnodeDelete(tree->root->left, 1);。

または、削除するポインターにポインターを渡すこともできます。

nodeDelete(Node **killptr)
{
    free(*killptr);
    *killptr = NULL;
}

この場合、を呼び出しますnodeDelete(&tree->root->left->right);。

于 2012-07-26T14:07:23.863 に答える
0

はい、ダブルポインタを使用する必要があります。また、削除するノードの子を再帰的に削除することも忘れないでください。

void nodeDelete(Node **killNode)
{
    if(!*killNode)
        return;

    // Free child nodes
    nodeDelete((*killNode)->left);
    nodeDelete((*killNode)->right);

    // Free the node itself
    free(*killNode);
    *killNode=NULL;
}

nullポインターのチェックは、最初から意図的に実行されます。これにより、再帰呼び出しをnullポインターのチェックでラップする必要がなくなります。

于 2012-07-26T14:13:22.307 に答える