質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.62%

C言語 二分探索木のノードの削除

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 308

jun_T

score 2

C言語で自己参照構造体を用いた二分探索木の削除を行うプログラムが分かりません。

二分探索木から任意のデータのノードを削除する関数deleteがうまく記述できません。

葉のノードの削除はできているのですが、そうでないノードの削除をしようとすると、データ0を持つノードが表れてしまいます。

どのように修正すればよいのでしょうか

 

現在のソースコード

#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
struct node * left ;
struct node * right;
};
typedef struct node Node ;
Node *createNode(int data)
{
    Node *node;
    if ((node = (Node *) malloc(sizeof(Node))) == NULL) {
    fprintf(stderr, "Can't allocate memory\n");
    exit(1);
    }
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
Node *insert(Node *node, int data)
{
    if (node == NULL) {
    /* 空の木ならば,新しく作ったノードを根とする */
    node = createNode(data);
    }
    else {
    if (data < node->data) {
        /* dataはnodeの左の子に挿入 */
        node->left = insert(node->left, data);
    }
    else if (data > node->data) {
        /* dataはrootの右の子に挿入 */
        node->right = insert(node->right, data);
    }
    else {
        /* dataは既にあるので何もしない */  
          data == node->data;
        }
    }    
    return node; /* dataを挿入した後の部分木の根を返す */
}
Node *delete(Node *node, int data){
    Node *child;  //削除したいノードとデータを入れ替える子を記憶
    if(node == NULL){
        return node;
    }
    /*削除対象ノードの探索*/
    if(node->data > data){        //左の子を探索
        node->left = delete(node->left, data);
    }else if(node->data < data){   //右の子を探索
        node->right = delete(node->right, data);
    }else{   //探索完了
        if(node->left == NULL && node->right == NULL){     //葉ノード
            free(node);
            return NULL;
        }else if(node->left == NULL){      //右の子のみ存在
            /*データの入替*/
            child = node->right;
            node->data = child->data;
            node->left = child->left;
            node->right = child->right;
            free(child);        //子ノードを削除
            return node; /* dataを削除した後の部分木の根を返す */
        }else if(node->right == NULL){      //左の子のみ存在
            /*データの入替*/
            child = node->left;
            node->data = child->data;
            node->left = child->left;
            node->right = child->right;
            free(child);        //子ノードを削除
            return node; /* dataを削除した後の部分木の根を返す */
        }else{     //左右両方の子がいる
            child = node->left;
            Node *child_prev = node;
            while(child->right != NULL){//左の子の最大値を探索
                child_prev = child;
                child = child->right;
            }
            node->data = child->data;
            if(child->left != NULL){
                if(child_prev != node){
                child_prev->right = child->left;
                }
            }
            free(child);        //子ノードを削除
            return node; /* dataを削除した後の部分木の根を返す */
        }
    }
}
void print_tree(Node *node)
{
    static int depth = 0;
    printf("%*s", depth + 3, " - ");
    printf("[\"%d\"]\n", node->data);
    if(node->left != NULL){
        depth++;
        print_tree(node->left);
        depth--;
    }
    if(node->right != NULL){
        depth++;
        print_tree(node->right);
        depth--;
    }
}
int main (void)
{
    int data[11] = {6, 4, 11, 2, 5, 16, 29, 15, 18, 31, 42};
    int x;
    Node *root;
    for (int i = 0; i < 11; i++) {
        root = insert(root, data[i]);
    }
    print_tree(root);
    printf("delete ?"); scanf("%d",&x); puts("");
    root = delete(root, x);
    print_tree(root);puts("");

    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

0

お気楽C言語プログラミング超入門
「C言語 二分探索木のノードの削除」で検索してみました。
とても分かりやすい解説とコードがありますので参考にしてみてください。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/09/22 09:32

    理解できました!ありがとうございます!!

    キャンセル

0

左枝に繋がるnodeを削除したら、右枝から辿った最左の葉と置き換え
右枝に繋がるnodeを削除したら、左枝から辿った最右の葉と置き換え

でよくないかしら。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.62%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る