c - 二分探索木ノードの挿入が正しく機能しない

Question

二分探索木 (作成、削除、検索) を実装する宿題があります。先生から提供された例を使用しましたが、うまくいきません。

これまでの私のコードは次のとおりです。

void insert_node(int k){
    struct node *nodnou,*flow,*parent;

    nodnou = (struct node*)malloc(sizeof(node));
    nodnou->st = NULL;
    nodnou->dr = NULL;
    nodnou->nr = k;

    if (root==NULL)
    {
        root = (struct node*)malloc(sizeof(node));

        root = nodnou;
    }
    else
    {
        flow = (struct node*)malloc(sizeof(node));
        parent = (struct node*)malloc(sizeof(node));
        flow = root;
        parent = root;
        while (((flow->st!=NULL) || (flow->dr!=NULL)) && flow!=NULL)
        {
            if (k<flow->nr)
            {
                parent = flow;
                flow = flow->st;
            }
            else
            {
                parent = flow;
                flow = flow->dr;
            }
        }

        if (k<flow->nr)
        {
            parent->st = nodnou;
        }
        else
        {
            parent->dr = nodnou;
        }
    }
}

考え方: この関数は、挿入したいノードの値を k パラメータとして取得します。関数はツリーのルートのみを挿入します (ルートはグローバル変数です)。

私の最大の問題はwhile、ツリーをスイープして新しいノードの場所を見つけるループだと思います。

フローポインタが存在しないものへの割り当てを取得するため、使用while (flow!=NULL)しても機能しません。どこが間違っているかを理解するのを手伝ってください（宿題）。

score 3 · Accepted Answer

あなたのコードにはいくつかの重要な欠陥があります。その中には、C で動的メモリ割り当てがどのように機能するかについての誤解があります。次のようなパターンには決して従わないでください。

Type *pointer = malloc(sizeof(Type));
pointer = <<something else>>

文字通りメモリをリークし、2 つの短い行で何も得られません。これは、Java や C# のようなオブジェクト参照ベースの言語ではありません。ポインタは、メモリアドレスを保持する変数です。intが整数を保持できるように、ポインタはアドレスを保持します。そして、次の例のように:

int n = 6;
n = 5;      //Hmm. Where did the 6 go? Oh yeah, We overwrote it with 5.

ポインターで同じことを行うと、割り当てリンクが失われます。

struct node *root = malloc(sizeof(*root));
root = nodnou; // memory allocated above is gone. forever leaked.

ポインターは変数です。他の変数と同様に、値を保持します。ただし、ポインターの場合、その値はaddressです。ポインターへのポインターを含め、C ではほとんどすべてのポインターを使用できます。ポインター変数のアドレスを保持する変数。そして、挿入要件に対して特に洗練されたソリューションを提供するので、それらを取り上げます。

以下は、ツリー内での重複をサポートしないバイナリツリー挿入の一般的な実装です (重複を許可すると、コードはさらに短くなります)。さらに、提供された関数パラメーターを超えるローカル変数をまったく使用せずにこれを実行します。これを分析して、それがどのように機能するかを判断してください。if (root) {} else {}これは、最初は NULL のツリールートポインターでも機能するため、特別なケーシングロジックが不要になります。

void insert_node(struct node **pp, int k) 
{
    while (*pp)
    {
        if (k < (*pp)->nr)        // move down left side?
            pp = &(*pp)->st;

        else if ((*pp)->nr < k)   // move down right side?
            pp = &(*pp)->dr;

        else return;              // found the key, no dupes. leave
    }

    // pp contains the address of the pointer we need to set.
    *pp = malloc(sizeof(**pp)); 
    (*pp)->st = (*pp)->dr = NULL;
    (*pp)->nr = k;
}

ツリーが重複をサポートする必要がある場合は、それらが挿入される側について一貫性を保つ必要がありますが、上記のアルゴリズムを大幅に短縮します。

void insert_node(struct node **pp, int k) 
{
    while (*pp)
        pp = (k < (*pp)->nr) ? &(*pp)->st : &(*pp)->dr;

    // pp contains the address of the pointer we need to set.
    *pp = malloc(sizeof(**pp)); 
    (*pp)->st = (*pp)->dr = NULL;
    (*pp)->nr = k;
}

どちらの場合も、次のように呼び出し側で呼び出されます。

struct node *root = NULL;

insert(&root, 5);
insert(&root, 10);
insert(&root, 7); 
...etc...

score 0 · Accepted Answer

あなたはほとんどそれを手に入れました。ついていく！

最初に、メモリ割り当てをもう少しよく理解する必要があります。実際には、関数の最初のmalloc()呼び出しだけが必要です。insert_node()これは、各呼び出し中にツリーに追加するノードに割り当てるメモリです。malloc実行している残りのすべてのs は不要です。使用している他のポインターにメモリを割り当てる必要があると直感的に感じているようですが、それらはすべて一時的なものであり、割り当てを必要とせず、逆参照を試みる前に有効なノードに割り当てるだけです。実際、これらの不要な割り当てにより、次のようなコードでメモリリーク (要求したメモリを解放できない) が発生します。

root = (struct node*)malloc(sizeof(node));
root = nodnou;

2 番目の assignmet( root = nodnou) は、前のmalloc()呼び出しの結果を上書きします。上書きされたポインター値を他の場所に保存しなかったため、そのメモリを解放することはできなくなります。応用！

次に、挿入ポイントを探してツリーをたどるコードを単純化できます。flow が NULL になることを心配しているようですが、問題ありません。重要なノードは親です。while ループが終了すると、挿入されたノードをリンクする必要がある実際のノードがポイントされます。これがあなたのコードの修正版です。

void insert_node(int k) {
   struct node *nodnou, *flow, *parent;
   // this is the only memory allocation that should be done
   nodnou = (struct node*)malloc(sizeof(node));
   nodnou->st = NULL;
   nodnou->dr = NULL;
   nodnou->nr = k;

   parent = NULL;

   if( root == NULL ) {
      root = nodnou;
   } else {

      flow = root;
      // We will walk the tree in order until we reach the bottom of the 
      // tree (flow becomes null). What we are trying to do is to find out
      // the node that will become the parent of the new node we are inserting
      // It doesn't matter if flow becomes NULL, the important value after the
      // while loop ends is parent 
      while( flow != NULL ) {
         // update the current potential parent node
         parent = flow;
         if( k < flow->nr ) {
            // the number we are inserting is lower than the flow node, walk to the left
            flow = flow->st;
         } else {
            // the number we are inserting is greater or equal than the flow node, 
            // walk to the right
            flow = flow->dr;
         }
      }

      // We have reached the bottom, now compare number again with the node that
      // will become parent, to find out if we need to link this node to the left
      // or to the right of the parent node

      if( k < parent->nr ) {
         parent->st = nodnou;
      } else {
         parent->dr = nodnou;
      }
   }

}

それでおしまい。残りのツリー操作をコード化してみて、混乱した場合は遠慮なく尋ねてください。=)

score 0 · Accepted Answer

while(flow != NULL) を使用し、その後要素をフローとして挿入する必要があると思います。今のやり方では、停止すべきでない場合に停止し、停止するたびに奇妙なことをします。ペンと紙を使っていくつかの例に取り組んでみてください。

c - 二分探索木ノードの挿入が正しく機能しない

3 に答える 3

Related

Reference