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

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

新規登録して質問してみよう
ただいま回答率
85.50%
データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

ポインタ

ポインタはアドレスを用いてメモリに格納された値を"参照する"変数です。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1789閲覧

【C++】ポインタのポインタに間接参照演算子をつけたものへの代入がうまく行かない

退会済みユーザー

退会済みユーザー

総合スコア0

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

ポインタ

ポインタはアドレスを用いてメモリに格納された値を"参照する"変数です。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2020/03/04 16:38

実現しようとしていること

AOJ ALDS1_8_Cの二分探索木を以下のように実装しようとしましたが、void binaryTree::erase(int) 内の、子を持たない節点 **ppV の削除のところで、メモリ解放後に親節点からの参照を切りたいです。

わからないこと

ppV は削除する節点への親節点からのポインタ(pParent->left || pParent->right)のポインタなので、v に nullptr を代入すればいいと考えて実装してみたのですが、親節点に反映されなくて困っています。
私の認識では、ポインタはある値を格納している変数のメモリのアドレスで、それに
をつけたものへの代入は変数そのものへの代入と同じ動作をするものと思っていたのですが、違うのでしょうか?
ご教授願います。

該当のソースコード

c++

1#include <iostream> 2 3using namespace std; 4 5struct node { 6 int key; 7 node *parent; 8 node *left; 9 node *right; 10}; 11 12void walkInOrder(node *cur) { 13 if (cur == nullptr) return; 14 walkInOrder(cur->left); 15 printf(" %d", cur->key); 16 walkInOrder(cur->right); 17} 18 19void walkPreOrder(node *cur) { 20 if (cur == nullptr) return; 21 printf(" %d", cur->key); 22 walkPreOrder(cur->left); 23 walkPreOrder(cur->right); 24} 25 26struct binaryTree { 27 node *root; 28 29 binaryTree() { 30 root = nullptr; 31 } 32 33 void insert(int x) { 34 node *pParent = nullptr; 35 node **v = &root; 36 node *nodeX = (node *) malloc(sizeof(node)); 37 nodeX->key = x; 38 nodeX->left = nodeX->right = nullptr; 39 while (*v != nullptr) { 40 pParent = *v; 41 v = &((*v)->key <= x ? (*v)->right : (*v)->left); 42 } 43 nodeX->parent = pParent; 44 *v = nodeX; 45 } 46 47 void erase(int x) { 48 node *pParent = nullptr; 49 node **ppV = &root; 50 while (*ppV != nullptr && (*ppV)->key != x) { 51 pParent = *ppV; 52 ppV = &((*ppV)->key <= x ? (*ppV)->right : (*ppV)->left); 53 } 54 if ((*ppV) == nullptr) return; 55 if ((*ppV)->left != nullptr && (*ppV)->right != nullptr) { 56 pParent = *ppV; 57 node *nextNode = pParent->right; 58 while (nextNode->left != nullptr) { 59 pParent = nextNode; 60 nextNode = pParent->left; 61 } 62 (*ppV)->key = nextNode->key; 63 ppV = &nextNode; 64 } 65 if ((*ppV)->left == nullptr && (*ppV)->right == nullptr) { 66 free((*ppV)); 67 *ppV = nullptr; 68 } else { 69 node *vChild = (*ppV)->left != nullptr ? (*ppV)->left : (*ppV)->right; 70 free((*ppV)); 71 *ppV = vChild; 72 vChild->parent = pParent; 73 } 74 } 75 76 void find(int x) { 77 node *v = root; 78 while (v != nullptr) { 79 if (x < v->key) v = v->left; 80 else if (v->key < x) v = v->right; 81 else break; 82 } 83 printf("%s\n", v == nullptr ? "no" : "yes"); 84 } 85 86 void print() { 87 walkInOrder(root); 88 printf("\n"); 89 walkPreOrder(root); 90 printf("\n"); 91 } 92}; 93 94int main() { 95 int n, x; 96 string op; 97 binaryTree tree; 98 cin >> n; 99 for (int i = 0; i < n; ++i) { 100 cin >> op; 101 if (op[0] == 'p') { 102 tree.print(); 103 } else { 104 cin >> x; 105 if (op[0] == 'i') tree.insert(x); 106 else if (op[0] == 'f') tree.find(x); 107 else tree.erase(x); 108 } 109 } 110 return 0; 111}

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

問題はその上の

ppV = &nextNode;

ではないかと思います。
これによって、*ppv=nullptrnextNode=nullptrとなります。

投稿2020/03/04 22:20

asm

総合スコア15147

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2020/03/04 22:58 編集

削除する節点に2つの子がある時に、次節点の値をコピーして、代わりに次節点の方を削除するというアルゴリズムが http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_C&lang=ja で指定されているので、そのように実装していますが問題でしょうか?デバッガーも使いながら、各変数の値の遷移に異常がないことは確かめているのでないとは思いますが、
asm

2020/03/04 23:23 編集

node **nextNode = &pParent->right; ppV = nextNode; にしてみては?
退会済みユーザー

退会済みユーザー

2020/03/04 23:28

なるほど、ppVの指している変数がnextNodeそのものになっていたということですか。そのようにしたら、確かにうまくいきました。ありがとうございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問