Java バイナリツリーの垂直での出力方法

Question

発生している問題・エラーメッセージ

前提・実現したいこと

バイナリツリーの垂直での出力方法に悩んでいます。
プリントクラスのコードがわかりません。
サンプルの出力は以下です。

public  class Node<T extends Comparable<T>> {
    T value;
    Node<T> left, right;

    public void insertToTree(T v) {
        if (value == null) {
            value = v;
            return;
        }
        if (v.compareTo(value) < 0) {
            if (left == null) {
                left = new Node<T>();
            }
            left.insertToTree(v);
        } else {
            if (right == null) {
                right = new Node<T>();
            }
            right.insertToTree(v);
        }
    }

    public void printTree(OutputStreamWriter out) throws IOException {
        if (right != null) {
            right.printTree(out, true, "");
        }
        printNodeValue(out);
        if (left != null) {
            left.printTree(out, false, "");
        }
    }
    private void printNodeValue(OutputStreamWriter out) throws IOException {
        if (value == null) {
            out.write("<null>");
        } else {
            out.write(value.toString());
        }
        out.write('\n');
    }
    // use string and not stringbuffer on purpose as we need to change the indent at each recursion
    private void printTree(OutputStreamWriter out, boolean isRight, String indent) throws IOException {
        if (right != null) {
            right.printTree(out, true, indent + (isRight ? "        " : " |      "));
        }
        out.write(indent);
        if (isRight) {
            out.write(" /");
        } else {
            out.write(" \");
        }
        out.write("----- ");
        printNodeValue(out);
        if (left != null) {
            left.printTree(out, false, indent + (isRight ? " |      " : "        "));
        }
    }

}

のコードはエラーが出ていないので合っていると思いますが、出力の際のコードがどうしてもわかりません。

試したこと

試したのは以下のプリントクラスコードです。

 private static Node<Integer> Tree() {
     Node<Integer> root = new Node<Integer>(99);
        Node<Integer> n1 = new Node<Integer>(97);
        Node<Integer> n2 = new Node<Integer>(92);
        Node<Integer> n3 = new Node<Integer>(83);
        Node<Integer> n4 = new Node<Integer>(72);
　　　　　・
　　　　　・
　　　　　・
　　　　　
        root.left = n1;
        root.right = n2;

        n1.left = n2;
        n1.right = n3;
       　・
　　　　　・
　　　　　・

public static void main(String[]args){
        binarytree b1=new binarytree();
        
        b1.root=new Node(2);
        
        b1.root.left=new Node(1);
        b1.root.right=new Node(5);
        ・
　　　　　・
　　　　　・

どちらもエラーとなりました。
様々なサイトを見て試してみましたがどうしても理解できません。

Comments

[momon-ga]

ごめんなさい。「プリントクラスのコードがわからない」の意味がわからないです・・・
もう少し適格に状況を質問に補足してもらえないでしょうか

プリントクラスとは？なんですか？
コードがわからない。とは、どういう状態ですか？
> 様々なサイトを見て試してみましたがどうしても理解できません。
・参考にしている？ソースのロジックがわからない
・出力するロジックが書けない？
・出力するロジックは書いた(コンパイルエラーはでない)けど、呼び方がわからない？

> どちらもエラーとなりました。
そもそもエラーになるとは、どういう状態？（例外が発生した？）

[ladyinredjes]

値を挿入するコードがわからないという意味です。
下の２つのコードが値を挿入しているクラスのコードです。
この二つだと出力するメソッドが呼び出せず、コンパイルエラーとなってしまいます。
わかりずらく、申し訳ありません。

[jimbe]

「サンプルのように表示されるためにツリー構造を作る部分が分からない」ということでしょうか.

[ladyinredjes]

そうです。ありがとうございます。

[jimbe]

ということは, Node クラスは修正せずにこのまま使うのでしょうか.

[ladyinredjes]

今の所エラーがないのでつかえれば良いですが、そもそもNodeクラスのコード自体が間違っているのでしょうか？

[jimbe]

それはまだ試しておりませんので分かりませんが, 少なくともサンプルには無い「｜」や「／」, 「<null>」等が表示されるかのようになっています.
ツリー構造さえ合っていれば, これらは有っても無くても構わないということでよいのでしょうか.
また, もし Node クラスの表示に不都合があれば, 修正しても良いのでしょうか.

[ladyinredjes]

一応構造が理解しやすいかなと思い、そのまま残しているだけなので気にされなくて大丈夫です。
はい。ありがとうございます。

Answer 1

「サンプルのように表示されるためにツリー構造を作る部分が分からない」ということでしたので, main を含む BTree クラスとしてツリーの生成・表示を行うコードを起しました.
なお, Node クラスの printTree (及びその下位メソッド) が OutputStreamWriter.write に出力していましたが, 直接表示するよう PrintStream.print に変更致しましたうえでのコードとなります.

public class BTree {
  public static void main(String[] args) throws IOException {
    int[] values = { 49, 83, 97, 99, 92, 71, 72, 69, 28, 40, 44, 32, 18, 19, 11 };

    Node<Integer> tree = new Node<>();
    for(int v : values) tree.insertToTree(v);

    tree.printTree(System.out);
  }
}

Node クラスは, insertToTree メソッドにより, 自身の値の設定 及び その値との比較によって左右に振り分けての下位構造の生成 は致しますが, バランスは取らないので, 生成する順に値を渡す必要があります.

Comments

[ladyinredjes]

できました。本当にありがとうございました(TT)

[jimbe]

Node クラスにはメソッドは4つしかありません. そのうち3つは表示にしか関係しませんので, Nodeの機能の中心は20行にも満たない1つのメソッドのみです.
せめて, その1つのメソッドをしっかりとご理解頂いてから, コードをお書きになったほうが良いかと思います. でなければ, エラーになったという2つのメソッドを書くのにも多少ともお時間がかかったことでしょうに, ムダになってしまいます.

Answer 2

あまりソース読んでないので、アイデアだけというか、大抵の人が考えそうなやりかただと。
サンプルのように出したいなら。

・より上側に表示するノードの存在確認（右ノード） // 1
存在した場合、インデントを増やして、その右ノードの表示処理
・自分自身の表示処理 // 2
より下側に表示するノードの存在確認（左ノード） // 3
・存在した場合、インデントを増やして、その左ノードの表示処理

を、再帰的に呼べばええんじゃないかと。

イメージ

public void printNode(Node n, String indent) {
    // 1
    if(n.right != null) {
        printNode(n.right, indent + "    ");
    }
    // 2
    System.out.println(indent + n.value);
    // 3
    if(n.left != null) {
        printNode(n.left, indent + "    ");
    }
}

Comments

[ladyinredjes]

回答ありがとうございます。ただ、出力の際のプリントクラスのコードがわからなくて...