構造体のポインタ渡しの仕組みが分からない

Question

Cで英単語の処理をするプログラムを作るために、二分探索木を実装しています。
二分探索木で新たなノードを追加する再帰関数を書いたのですが、構造体のポインタに関して分からない事があったので質問させてください。

二分探索木のノードの構造体と、ノードを追加する関数↓

/* ノードの構造体 */
typedef struct BINNODE {
    char *word;
	struct BINNODE *pLeft;
	struct BINNODE *pRight;
} BinNode;

/* pNodeの木にwordをメンバ変数に持つノードを追加する再帰関数 */
BinNode *apndNode(BinNode *pNode, char *word) {
    int cond;
    if(pNode == NULL) {
        pNode = (BinNode*)malloc(sizeof(BinNode));
        pNode->word = (char*)malloc(strlen(word)+1);
        strcpy(pNode->word, word);
        pNode->pLeft = pNode->pRight = NULL;   
    }
    else if(strcmp(pNode->word, word) < 0)  
        pNode->pRight = apndNode(pNode->pRight, word);　//"pNode->pRight = "はなぜいる？
    else
        pNode->pLeft = apndNode(pNode->pLeft, word);　//"pNode->pLeft = "はなぜいる？
    return pNode;
}

下から4行目と2行目の
**pNode->pRight = apndNode(pNode->pRight, word);と
pNode->pLeft = apndNode(pNode->pRight, word);
なのですが、pNode->pRight，pNode-pLeftへ代入する処理をなくしてapndNode関数だけ呼び出すようにした場合、ノードへの変更が反映されなくなりました。（例えば apndNode(rootNode->pRight, hoge）**を呼び出してもrootNode->pRightはNULLのままになってしまう）

ポインタ渡しならば、apndNode(pNode->pRight, word)を呼び出すだけでpNode->pRightのメモリの確保やメンバ変数の変更も反映されると思うのですが、なぜ代入をしないと反映されなくなるのでしょうか。

実行環境はvscodeです。
拙い説明ですが、回答よろしくお願いいたします。

Answer 1

ポインタ渡しならば、apndNode(pNode->pRight, word)を呼び出すだけでpNode->pRightのメモリの確保やメンバ変数の変更も反映されると思うのですが、

void allocate(int* p) {
  p = (int*)malloc(sizeof(int)); /* 領域を確保する */
}

int main() {
  int* int_ptr = NULL;
  allocate(int_ptr);
  ...
}

上記コードで、int_ptr には allocate() で確保された領域がセットされない。

void fill_zero(int n) {
  n = 0;
}

int main() {
  int n = 123;
  fill_zero(n);
  ...

これ↑で n == 0 とならないのと同じ理由で。

ポインタ値を変更したいなら

void allocate(int** p) {
  *p = (int*)malloc(sizeof(int)); /* 領域を確保する */
}

int main() {
  int* int_ptr = NULL;
  allocate(&int_ptr);
  ...
}

あるいは

int* allocate() {
  return (int*)malloc(sizeof(int)); /* 領域を確保する */
}

int main() {
  int* int_ptr = NULL;
  int_ptr = allocate();
  ...
}

Comments

[misemi]

ポインタにアドレスを代入しても元のポインタには反映されないんですね。とても腑に落ちました。
丁寧に例示して頂きありがとうございます。

Answer 2

ちょっと難しい回答になるけど・・・
ポインタを渡しても呼び出し元の変数には代入できないので、呼び出し元で変数に代入する必要があります。
参照渡しできる言語（C++, C#, PHP)ならば、呼び出した先で呼び出し元の変数に代入できるので、呼び出し元での代入を省略できます。

参照渡しにしたコードを書いてみました。g++でコンパイルして実行してみてください。

#include <iostream>
#include <cstring>

#define MAX 1000000

/* ノードの構造体 */
typedef struct BINNODE {
    char *word;
    struct BINNODE *pLeft;
    struct BINNODE *pRight;
} BinNode;

/* pNodeの木にwordをメンバ変数に持つノードを追加する再帰関数 */
void apndNode(BinNode *&pNode, const char *word) {
    int cond;
    if(pNode == NULL) {
        pNode = (BinNode*)malloc(sizeof(BinNode));  //呼び出し元の変数に代入
        pNode->word = (char*)malloc(strlen(word)+1);
        strcpy(pNode->word, word);
        pNode->pLeft = pNode->pRight = NULL;
    }
    else if(strcmp(pNode->word, word) < 0)
        apndNode(pNode->pRight, word);  //呼び出し元での"pNode->pRight = "は不要
    else
        apndNode(pNode->pLeft, word);  //呼び出し元での"pNode->pLeft = "は不要
}

int main(){
    struct BINNODE *root = NULL;
    apndNode(root, "hello");
    apndNode(root, "world");
    printf("word: %s\n", root->word);
    printf("right: %s\n", root->pRight ? root->pRight->word : "NULL");
    printf("left: %s\n", root->pLeft ? root->pLeft->word: "NULL");
}

Comments

[misemi]

参照渡しの例とても参考になりました。C++などではこちらを使っていきたいと思います。ありがとうございます。

Answer 3

pNode->pRigh
というのは、
(*pNode).pRigh
と同じです。
そこから考えてみればいいかと。