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

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

ただいまの
回答率

90.47%

  • Java

    14106questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

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

解決済

回答 4

投稿 編集

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

ryo1729_k

score 1

前提・実現したいこと

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/ツール等のバージョンなど)

より詳細な情報

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • swordone

    2017/09/29 17:00

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

    キャンセル

  • ryo1729_k

    2017/09/29 18:20

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

    キャンセル

回答 4

+3

inputメソッドの中で、ローカル変数がnewされてるだけだからだと思います。
それはforループの中でrightleftを表示すると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つで囲うときれいに表示されます。
ご修正を。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/09/30 13:46

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

    キャンセル

checkベストアンサー

+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のポインター変数相当と思って理解してもかまわないと思います。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/09/30 12:56

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

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

    キャンセル

+1

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

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);
        }
    }
}

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/09/30 13:36

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

    キャンセル

  • 2017/10/02 10:18

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

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

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

    キャンセル

0

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

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

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/09/29 19:28

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

    キャンセル

  • 2017/09/30 01:42

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

    キャンセル

関連した質問

  • 受付中

    JAVAに関する質問

    JAVAに関する質問です。 JAVAで以下のプログラムを作成しました。 import java.util.Scanner;  public class Sample {  /

  • 受付中

    ループ化の方法

    public class Gohkaku {     public static void main(String[] args){         int math = ne

  • 受付中

    社員情報のプログラム

    社員情報のプログラム (JAVA) プログラの機能 (1)社員情報の追加 入力項目としては、社員番号、氏名(性、名)、生年月日(年、月、日) (3)で読み込んだ情報を追加する仕

  • 解決済

    javaでデータを読み込んでソートしたいのですがうまく来ません

    コンパイルするとエラーになって 「シンボルが見つかりません」と表示されます。 他にも問題があれば教えてください import java.io.File; import

  • 解決済

    入力した値を表示させない方法

    初めまして。現在JAVAを学んでいる初心者です。 現在、配列に格納している値を表示させるプログラムを作っています。 ユーザーから入力があった場合、次に配列の値を表示させるとき、

  • 解決済

    javaで作れる学習プログラムってどのようなものが作れますか

    意図 javaを使って学習プログラムを作成してほしいといわれました。 しかし、イメージがわきません。 どんなものが作れるのでしょうか

  • 解決済

    Javaでマス当てゲームを作りたい

    前提・実現したいこと Javaで5*5のマス目から当たりを見つけるプログラムを作りたいと考えています。 インターネットで下記のプログラムを見つけ応用できないかと思っています。

  • 解決済

    改行区切りでの出力

    ランダムな整数を改行区切りで3個出力したくて以下のコードを打ってみたんですが間違いといわれました。どこが違うのか指摘お願いします  public class Main {  p

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

  • Java

    14106questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。