二分木図を印刷する方法

投稿日: 2022-11-08 2022-11-08
タグ: Data Structures, Java

1. 序章

印刷は、データ構造の非常に一般的な視覚化手法です。ただし、ツリーは階層的な性質があるため、ツリーに関しては注意が必要です。

このチュートリアルでは、Javaの二分木の印刷テクニックを学びます。

2. 樹形図

コンソール上に文字のみを使用して描画するという制限にもかかわらず、ツリー構造を表すためのさまざまな図の形状があります。それらの1つを選択することは、主に木のサイズとバランスに依存します。

印刷できる図の可能なタイプのいくつかを見てみましょう。

ただし、実装も簡単な実用的なものについて説明します。木が成長する方向を考慮に入れることにより、それを水平木と呼ぶことができます。

水平ツリーは常にテキストフローと同じ方向に流れるため、他の図よりも水平図を選択することにはいくつかの利点があります。

大きくて不均衡な木も視覚化できます
ノード値の長さは表示構造に影響しません
実装がはるかに簡単です

したがって、次のセクションでは、水平方向の図を使用して、単純な二分木プリンタークラスを実装します。

3. 二分木モデル

まず、数行のコードで実行できる基本的な二分木をモデル化する必要があります。

単純なBinaryTreeModelクラスを定義しましょう。

public class BinaryTreeModel {

    private Object value;
    private BinaryTreeModel left;
    private BinaryTreeModel right;

    public BinaryTreeModel(Object value) {
        this.value = value;
    }

    // standard getters and setters

}

4. サンプルテストデータ

バイナリツリープリンターの実装を開始する前に、視覚化を段階的にテストするためのサンプルデータを作成する必要があります。

BinaryTreeModel root = new BinaryTreeModel("root");

BinaryTreeModel node1 = new BinaryTreeModel("node1");
BinaryTreeModel node2 = new BinaryTreeModel("node2");
root.setLeft(node1);
root.setRight(node2);
 
BinaryTreeModel node3 = new BinaryTreeModel("node3");
BinaryTreeModel node4 = new BinaryTreeModel("node4");
node1.setLeft(node3);
node1.setRight(node4);
 
node2.setLeft(new BinaryTreeModel("node5"));
node2.setRight(new BinaryTreeModel("node6"));
 
BinaryTreeModel node7 = new BinaryTreeModel("node7");
node3.setLeft(node7);
node7.setLeft(new BinaryTreeModel("node8"));
node7.setRight(new BinaryTreeModel("node9"));

5. 二分木プリンター

確かに、単一責任原則のために、BinaryTreeModelをクリーンに保つために別のクラスが必要です。

これで、ビジターパターンを使用して、ツリーが階層を処理し、プリンターが印刷を処理するようになりました。ただし、このチュートリアルでは、単純にするためにそれらをまとめます。

したがって、 BinaryTreePrinter という名前のクラスを定義し、それを実装し始めます。

5.1. 事前注文トラバーサル

水平方向の図を考慮して、正しく印刷するには、pre-orderトラバーサルを使用して簡単に開始できます。

したがって、事前注文トラバーサルを実行するには、最初にルートノードにアクセスし、次に左のサブツリーにアクセスし、最後に右のサブツリーにアクセスする再帰メソッドを実装する必要があります。

ツリーをトラバースするメソッドを定義しましょう。

public void traversePreOrder(StringBuilder sb, BinaryTreeModel node) {
    if (node != null) {
        sb.append(node.getValue());
        sb.append("\n");
        traversePreOrder(sb, node.getLeft());
        traversePreOrder(sb, node.getRight());
    }
}

次に、printメソッドを定義しましょう。

public void print(PrintStream os) {
    StringBuilder sb = new StringBuilder();
    traversePreOrder(sb, this.tree);
    os.print(sb.toString());
}

したがって、テストツリーを簡単に印刷できます。

new BinaryTreePrinter(root).print(System.out);

出力は、トラバースされた順序でのツリーノードのリストになります。

root
node1
node3
node7
node8
node9
node4
node2
node5
node6

5.2. ツリーエッジの追加

ダイアグラムを正しく設定するために、「├──」、「└──」、「│」の3種類の文字を使用してノードを視覚化します。それらの最初の2つはポインター用で、最後の1つはエッジを埋めてポインターを接続するためのものです。

traversePreOrder メソッドを更新し、paddingおよびpointerとして2つのパラメーターを追加し、それぞれ文字を使用してみましょう。

public void traversePreOrder(StringBuilder sb, String padding, String pointer, BinaryTreeModel node) {
    if (node != null) {
        sb.append(padding);
        sb.append(pointer);
        sb.append(node.getValue());
        sb.append("\n");

        StringBuilder paddingBuilder = new StringBuilder(padding);
        paddingBuilder.append("│  ");

        String paddingForBoth = paddingBuilder.toString();
        String pointerForRight = "└──";
        String pointerForLeft = (node.getRight() != null) ? "├──" : "└──";

        traversePreOrder(sb, paddingForBoth, pointerForLeft, node.getLeft());
        traversePreOrder(sb, paddingForBoth, pointerForRight, node.getRight());
    }
}

また、printメソッドも更新します。

public void print(PrintStream os) {
    StringBuilder sb = new StringBuilder();
    traversePreOrder(sb, "", "", this.tree);
    os.print(sb.toString());
}

それでは、BinaryTreePrinterをもう一度テストしてみましょう。

したがって、すべてのパディングとポインターを使用して、図はうまく形作られました。

ただし、削除する追加の行がまだいくつかあります。

図を見ると、まだ3つの間違った場所に文字があります。

ルートノードの下の余分な行の列
右側のサブツリーの下の余分な行
右の兄弟がない左のサブツリーの下の余分な行

5.3. ルートノードと子ノードのさまざまな実装

余分な行を修正するために、トラバースメソッドを分割できます。 1つの動作をルートノードに適用し、別の動作を子ノードに適用します。

ルートノードのみのtraversePreOrderをカスタマイズしましょう。

public String traversePreOrder(BinaryTreeModel root) {

    if (root == null) {
        return "";
    }

    StringBuilder sb = new StringBuilder();
    sb.append(root.getValue());

    String pointerRight = "└──";
    String pointerLeft = (root.getRight() != null) ? "├──" : "└──";

    traverseNodes(sb, "", pointerLeft, root.getLeft(), root.getRight() != null);
    traverseNodes(sb, "", pointerRight, root.getRight(), false);

    return sb.toString();
}

次に、子ノード用の別のメソッドを次のように作成します。 traverseNodes。 A ちなみに、新しいパラメータを追加します hasRightSibling 前の行を正しく実装するには：

public void traverseNodes(StringBuilder sb, String padding, String pointer, BinaryTreeModel node, 
  boolean hasRightSibling) {
    if (node != null) {
        sb.append("\n");
        sb.append(padding);
        sb.append(pointer);
        sb.append(node.getValue());

        StringBuilder paddingBuilder = new StringBuilder(padding);
        if (hasRightSibling) {
            paddingBuilder.append("│  ");
        } else {
            paddingBuilder.append("   ");
        }

        String paddingForBoth = paddingBuilder.toString();
        String pointerRight = "└──";
        String pointerLeft = (node.getRight() != null) ? "├──" : "└──";

        traverseNodes(sb, paddingForBoth, pointerLeft, node.getLeft(), node.getRight() != null);
        traverseNodes(sb, paddingForBoth, pointerRight, node.getRight(), false);
    }
}

また、printメソッドに小さな変更を加える必要があります。

public void print(PrintStream os) {
    os.print(traversePreOrder(tree));
}

最後に、図はきれいな出力で素敵な形になりました。

6. 結論

この記事では、Javaでバイナリツリーを印刷する簡単で実用的な方法を学びました。

この記事のすべての例と追加のテストケースは、GitHubでから入手できます。

getdocs

13036