Javaの二分木探索の挿入がうまくいかない

Question

###前提・実現したいこと
Java言語の初心者です.

クラスの再帰を利用した2分木をで挿入・表示を行おうとしているのですが, 挿入がうまくできません.

C言語では, 2分木を扱ったことがあるのですがあっちはポインタなので新しく勉強中です.

###発生している問題・エラーメッセージ
Java, 環境はEclipse Neon 4.6

まず, サイトを参考にして手作業で木を作成し(コメントで除外した部分)、表示させることは出来ました.

しかし, ランダムに表れた数字を2分木に格納しようとしたときに問題が生じました.
ソースコードの【問題箇所】とコメントしているメソッドとfor文に問題があります.
メソッドを再帰させtreeを辿って, 該当箇所に新しくクラスをインスタンス化し, コンストラクタを使用してtree.dataに数字を代入しています.

本当なら, 表示させたときに入れた数字がすべて表示されるはずなのですが上手くいきません. 恐らく, 正しく木を生成できていないと思います.
2時間ほど考えたのですが全くわからないので質問させていただきました.

###該当のソースコード

import java.util.Random;

/*
 * Javaによる二分木の実装例
 */

class TreeNode{
	//中身の宣言
	int data;
	TreeNode left;
	TreeNode right;

	//コンストラクタ(生成時に引数とする初期化方法)
	TreeNode (int data, TreeNode left, TreeNode right){
		this.data = data;
		this.left = left;
		this.right = right;
	}
}

public class TreeTraverse {
	public static void main (String[] args) {

		//Randomクラスのインスタンス化
		Random Rnd = new Random();

		//ダミーの初期化
		int DUMMY = 5;

		//頑張って格納
		
        TreeNode tree = new TreeNode(DUMMY, null, null);
        
        /*除外
		tree.right = new TreeNode(6, null, null);
		tree.right.left = new TreeNode(2, null, null);
		tree.right.right = new TreeNode(3, null, null);
		tree.right.left.left = new TreeNode(4, null, null);
		tree.right.left.right = new TreeNode(5, null, null);
		tree.right.right.left = new TreeNode(6, null, null);
		tree.right.right.right = new TreeNode(7, null, null);
		tree.right.left.left.left = new TreeNode(8, null, null);
		tree.right.left.left.right = new TreeNode(9, null, null);
		*/

		//【問題箇所】ダミーを5に設定し、0～10までの数字をランダムに10つ二分木に格納してみる
		int N = 10;
		int num = 0;
		for(int i = 0;i<N;i++){
			num = Rnd.nextInt(10);
			System.out.println(num + "\n");
			input(tree, num);
		}

		System.out.print("Preorder:  ");
		preorder(tree.right);
		System.out.println();
		System.out.print("Inorder:   ");
		inorder(tree.right);
		System.out.println();
		System.out.print("Postorder: ");
		postorder(tree.right);
		System.out.println();
	}

//【問題箇所】
static void input(TreeNode tree, int num){
	if(tree == null){
		tree = new TreeNode(num, null, null);
		System.out.println(tree.data + " put\n");
	}else if(tree.data <= num){
		System.out.println("moved right.\n");
			input(tree.right, num);
	}else if(tree.data >= num){
		System.out.println("moved left.\n");
		input(tree.left, num);
	}
}

static void preorder (TreeNode tree) {
	if (tree != null) {
		System.out.print(" " + tree.data);
		preorder(tree.left);
		preorder(tree.right);
	}
}

static void inorder (TreeNode tree) {
	if (tree != null) {
		inorder(tree.left);
		System.out.print(" " + tree.data);
		inorder(tree.right);
	}
}

static void postorder (TreeNode tree) {
	if (tree != null) {
			postorder(tree.left);
			postorder(tree.right);
			System.out.print(" " + tree.data);
		}
	}
}

###試したこと
デバッグするために, mainメソッドからtree.right.dataなどを表示させてみたのですがそもそも最初のダミー部分以外, インスタンス化できていないようです.
しかし, その理由がいくら考えてもわかりません.

###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報

Comments

[swordone]

コードのマークダウンをお願いします。まず、質問編集画面でコードの部分を選択し、編集枠上部にある<code>というボタンを押します。そうするとコードがバッククォートで囲まれるとともに「ここに言語を入力」という文字が出ます。その部分を「java」に書き換えて投稿してください。

[ryo1729_k]

ご指摘の箇所を修正致しました、ありがとうございます。

Answer 1

inputメソッドの中で、ローカル変数がnewされてるだけだからだと思います。
それはforループの中でrightとleftを表示するとnullなので、そこから想定できます。

ボクもあまり詳しく説明できるほど知識はないんですが、
Cで言うポインタという概念はあまり表層化してないみたいです。
この辺りが参考になるでしょうか。。

あくまで値渡しという風に書いてあるので、

// 【問題箇所】
static TreeNode input(TreeNode tree, int num) {
  if (tree == null) {
    tree = new TreeNode(num, null, null);
  } else if (tree.data <= num) {
    tree.right = input(tree.right, num);
  } else if (tree.data >= num) {
    tree.left = input(tree.left, num);
  }
  return tree;
}

こんな風に書くと期待値に近づくでしょうか。
（実行はできましたが、詳しく見てないので違うかもしれません。）
treeで明示的に値を渡してあげてるイメージです。

あとソースはバッククォート3つで囲うときれいに表示されます。
ご修正を。

Comments

[ryo1729_k]

回答ありがとうございます.
非常にわかりやすい説明でした. URLも読みました, 参照渡しと値渡しの違いについてしっかり理解してゆこうと思います.
最後にreturnをまとめることでとてもきれいな記述になっていますね！

Answer 2

inputメソッドで例えば引数treeがnullの場合、新たなノードインスタンスを生成してinputメソッドの仮引数treeに代入していますね。メソッドの仮引数はメソッド内部を実行中でのみ存在しておりメソッド完了時に消滅します(Cでも同様)。仮引数に代入していた値は仮引数が消滅すると「どこからも参照されない宙ぶらりんのインスタンス」となり、inputメソッド呼び出し元からみると「せっかく生成したTreeNodeのインスタンスはどこにも結果が残らない」ことになります。それが期待通りに動かない原因です。(しかしおそらくJavaの参照型の値や変数への代入がどういうことかピンときていなければ以上の説明はやはりピンとこないと思います)

まず結論からいえば、とりあえず、こういうふうに書けばよいです。

TreeNode input(TreeNode tree, int num) {
  if (tree == null) {
    return new TreeNode(num, null, null);
  } else if (tree <= tree.data) {
    tree.left = input(tree.left, num);
    return tree;
  } else {
    tree.right = input(tree.right, num);
    return tree;
  }
}
...
TreeNode root = null; // 必ずしもDUMMYノードは必要ない
root = input(root, 1);
root = input(root, 2);
...

inputメソッドは「引数に指定したツリー（のルート）に値を挿入し、新たに構築されたツリー（のルート）を返す」のようにし、inputを使う側では常に戻り値をしかるべき変数へ代入して結果をその都度更新するのです。

ちなみに、上記のjavaのコードが実際にどう動くかのイメージを(厳密ではありませんが※)Cで書くと次のようになります。

例1

#include <malloc.h>

typedef struct _TreeNode *TreeNode;
struct _TreeNode {
  int data;
  TreeNode left;
  TreeNode right;
};

TreeNode newTreeNode(int num, TreeNode left, TreeNode right) {
  TreeNode node = (TreeNode)malloc(sizeof(struct _TreeNode));
  node->data = num;
  node->left = left;
  node->right = right;
  return node;
}

TreeNode input(TreeNode tree, int num) {
  if (tree == NULL) {
    return newTreeNode(num, NULL, NULL);
  } else if (num <= tree->data) {
    tree->left = input(tree->left, num);
    return tree;
  } else {
    tree->right = input(tree->right, num);
    return tree;
  }
}

int main(int argc, const char* argv[]) {
  ...
  TreeNode root = NULL; // やはり必ずしもDUMMYノードは必要ない
  root = input(root, 1);
  root = input(root, 2);
  ...
}

おそらく質問者さんは上記とはちょっと違うような実装をCでやっていたのではないでしょうか。

例2

void input(TreeNode* tree, int num) {
  if (*tree == NULL) {
    *tree = newTreeNode(num, NULL, NULL);
  } else if (num <= (*tree)->data) {
    input(&(*tree)->left, num);
  } else {
    input(&(*tree)->right, num);
  }
}

...

TreeNode root = NULL;
input(&root, 1);
input(&root, 2);
...

Javaではポインターがありませんが、実のところ参照型(TreeNodeもそう)の値は実質的にはCのポインター相当のように扱われています。

ただし、Cではポインター変数pに対して*p = ...と書けるのでinputメソッドの引数をstruct _TreeNodeのポインターのポインターにしておけば、input関数に戻り値は必要なく、関数内部で構造の変更を完全に記述できます。

しかしjavaではそういう書き方がありません。*tree = ...のように書けないわけです。tree = ...としか書けないのですから参照型変数への代入はC言語で言うとポインター変数に別のポインターを代入することのみしかできないと言えます。故にCで表現した場合の例2のようなインターフェースにはできず例1のようにしか実装できません。このように理解しておくと、Cとの対比でjavaでどう書かなければならないか見えてくるのではないでしょうか？

おそらくCでポインターを使った実装に慣れているとJavaで若干の不便さを感じるかも知れませんが、そのあたりは慣れと思います。

---

※:厳密ではないとは
javaでの参照型変数はCでのポインターと書きましたが、厳密には違います。Cでヒープからmallocした領域は決してアドレスが変化しませんが、javaではガベージコレクターが自動的に場所を移動（再配置）する点が違っています。しかし本件ではとりあえずjavaのメモリーの再配置については気にせず、javaの参照型変数がCのポインター変数相当と思って理解してもかまわないと思います。

Comments

[ryo1729_k]

詳しい解説ありがとうございます.
今回の質問を例にとれば, treeというクラス型変数がrightを参照し, rightもまたクラス型変数なので参照できる. そして, 参照すべき実体を作るためにnewメソッドを使ってインスタンス化しているのだと理解しました.
そして, 参照している実体のアドレスはCとは違い再配置されるものなのですね. 記憶に留めておきます.

Cでの詳しい解説もありがとうございます！！
僕はずっと, 下の例のようにポインタのポインタにしていたので同じような気分でvoidメソッドにしていたようです...
Cとjavaの対比については, これからしっかり理解していけたらと思います.

Answer 3

説明は有識者の方がばっちりしてくれたので、
私だったらこうするを書きます。

static void input(TreeNode tree, int num){
    // treeにnullを渡したらおとなしく落ちろ・・・
    if(tree.data <= num){
        if (tree.right == null) {
            tree.right = new TreeNode(num, null, null); 
        } else {
            input(tree.right, num);
        }
    } else if(tree.data >= num){
        if (tree.left== null) {
            tree.left = new TreeNode(num, null, null); 
        } else {
            input(tree.left, num);
        }
    }
}

Comments

[ryo1729_k]

回答ありがとうございます！
これって, 新たなノードインスタンスを仮引数treeに代入しているだけなので, 一見実引数の方に代入しないと反映されないように思われるのですがどのような仕組みになっているのでしょうか？
よろしければ教えていただけると幸いです.

[abs123]

参照型を介した操作は、
参照型が指し示すインスタンスに対する操作になります。

仮引数と実引数で見ているものが同じであれば、
その見ているものに対して何らかの操作をした結果も、
仮引数と実引数で同じように見えるはずです。

Cで言うと、ポインタに対しアロー演算子を使った操作をしているといった感じでしょうか？

Answer 4

回答してくださった方々、本当にありがとうございます。
仮引数を変更しても、実引数は変更されないことを失念しておりました。それはCでも定番ですね汗
回答者へのコメントに関しては、もう少し調べて理解出来たら返信させていただきます。

9/30追記
BAを付けなければならないところを、自己解決でコメントしてしまいました。
そのため、今回回答して頂いた方々にご迷惑をおかけしました。
お詫び申し上げます。
ただいま修正しました

Comments

[swordone]

回答者の回答が参考になったなら、そちらにベストアンサーを付けるべきです。

[ryo1729_k]

すみません。
自己解決の使い方を誤っていたようです。
ご指摘いただきありがとうございます。