1

ノードとノードのサブツリーを削除するポップ機能を作りたいです。これが私のコードです

void pop(struct data *node,int num)
{
    if(node)
    {
        if(node->num==num)
        {
            pop(node->left,num);
            pop(node->right,num);
            free(node);
            node=NULL;
        }
        else
        {
            if(num> node->num)
                pop(node->right,num);
            else if (num< node->num)
                pop(node->left,num);
        }
    }
}
void pre(struct data *node)
{
    if(node)
    {
        printf("%d ",node->num);
        pre(node->left);
        pre(node->right);
    }
}
void main()
{
    push(&root,37);
    push(&root,20);
    push(&root,45);
    push(&root,5);
    push(&root,15);
    push(&root,40);
    push(&root,50);
    pre(root);
    pop(root,5);
    pre(root);
    getchar();
}

ポップを使用する前に、事前機能はうまく機能します。でもポップ機能を使ったらブレイク。誰がどこが間違っているのか知っていますか？

4

2 に答える 2

1

ではpop、次のことを行っています: node=NULL;-- ただし、これは関数に渡されたポインターのコピーにのみ影響し、元のツリーのポインターには影響しません。ツリーは、解放したデータへのポインタを保持します。次にツリーで多くのことを行うときに、そのポインターを逆参照しようとすると、物事がうまくいかなくなります (少なくとも、うまくいくことを願っていますが、さらに悪いことに、うまくいくように見えることもあります)。

これを修正する 1 つの方法は、次のように double ポインターを渡すことpopです。

void pop(struct data **node, int num) { 

    if ((*node)->num == num)
        // ...
        free(*node);
        *node = NULL;
    }
}

関数が受け取ったポインタのコピーを変更するのではなく、ツリー内のポインタを変更しています。

ただし、これはまだ正しく機能しません-pop(child, num);現在のノードのサブツリーを破棄することに依存していますがnum、それらが同じ値に設定されていない限り、何も削除されず、ツリーを下に移動して探します一致するノードの場合num。

おそらく、1 つの関数で気になるノードを見つけてツリーをたどり、次に、指定されたノードから開始してツリーをたどり、(無条件に) そのノードとそのサブツリーを破棄する 2 つ目の関数が必要になるでしょう。

于 2012-06-10T06:57:43.710 に答える
0

pop 関数は次のようになります。

struct data* pop(struct data *node,int num)
{
  struct data* temp=null;
if(node)
{
    if(node->num==num)
    {
      if(node->left)
        pop(node->left,node->left->num);
      if(node->right)
        pop(node->right,node->right->num);
      free(node);
    }
    else
    {
        if(num> node->num)
            temp=pop(node->right,num);
        else if (num< node->num)
            temp=pop(node->left,num);

       if(node->right==temp)
        node->right=null;
       else if(node->left==temp)
        node->left=null;
       return temp;
    }
 }
return node;
}

これは、目的のノードがツリーのルートになるように調整されている場合、呼び出されている場所からツリーのルートを無効にするロジックがある限り機能します。

于 2012-06-10T08:44:50.617 に答える