如何打印二叉树图?

发布于 2024-10-31 19:08:33 字数 113 浏览 2 评论 0原文

我如何在java中打印一棵二叉树,以便输出如下:

        cat
        /\
     cat1 cat2

值可以是多个字符。

How can i print a binary tree in java so that the output is like:

        cat
        /\
     cat1 cat2

the values can be more than one character.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

倾听心声的旋律 2024-11-07 19:08:33

我通常使用 graphviz 中的 dot 程序来实现此目的。有一个简单的在线演示。这样您就不必担心间距或字体宽度。

I usually use the dot program from graphviz for this. There is an easy online demo of it. This way you don't have to worry about spacing or font widths.

甜心 2024-11-07 19:08:33
    cat
    /\
 cat1 cat2

二叉树由

  • 根节点、
  • 左子树、
  • 右子树

组成。要打印这样一棵树,我们需要将左子树和右子树一个挨一个地打印(至少有一个空格),然后在其上打印根节点,以两个子树的中间为中心,并用 ASCII 线连接。为此,我们需要知道两个子树的宽度。

使用这些想法和递归来创建您的树图。


下面是一个可能有用的方法规范:

/**
 * creates an ASCII-drawing of a binary tree.
 * @param node the root node of the tree in question
 * @return a String[] of the individual lines of the drawing.
 *    The first line contains the representation of the root node,
 *    the last line only leaf nodes, interim lines may contain
 *    line drawing characters or interior nodes.
 * 
 *    All the contained strings have the same length (are padded
 *    with spaces, where necessary).
 */
String[] drawTree(Node node) {
   ...
}

要输出树,您只需执行以下操作:

for(String line : drawTree(root)) {
    System.out.println(line);
}

那么,我们如何实现 drawTree 方法呢?

  • 它对叶节点(即没有子节点的节点)有什么作用?
  • 如果我们有一个非叶节点,我们如何将两个此类调用的结果(对于左子树和右子树)(即指定的两个字符串数组)组合到另一个字符串数组(如上所述)? (首先看一下两个数组具有相同长度的简单情况,即树具有相同的深度。)

祝你好运!

    cat
    /\
 cat1 cat2

A binary tree consists of

  • a root node
  • a left subtree
  • a right subtree

To print such a tree, we want to print the left and right subtrees one besides the other (with at least one space), and then print the root node over it, centered over the middle of both subtrees, and connected with ASCII lines. For this to work, we need to know how wide both subtrees are.

Use these ideas and recursion to create your tree-drawing.


Here is a method specification which may be useful:

/**
 * creates an ASCII-drawing of a binary tree.
 * @param node the root node of the tree in question
 * @return a String[] of the individual lines of the drawing.
 *    The first line contains the representation of the root node,
 *    the last line only leaf nodes, interim lines may contain
 *    line drawing characters or interior nodes.
 * 
 *    All the contained strings have the same length (are padded
 *    with spaces, where necessary).
 */
String[] drawTree(Node node) {
   ...
}

To output the tree, you then only have to do this:

for(String line : drawTree(root)) {
    System.out.println(line);
}

So, how could we implement our drawTree method?

  • What would it do for leaf nodes (i.e. nodes without children)?
  • If we have a non-leaf node, how can we combine the results of two such calls (for the left and right subtree), i.e. two String arrays as specified, to another string array as said? (First have a look at the simple case where both arrays have same length, i.e. the trees have same depth.)

Good luck!

恏ㄋ傷疤忘ㄋ疼 2024-11-07 19:08:33

这是一个完整的、可运行的 Demo,它是 Scala 代码的匆忙翻译,因此它不是惯用的 Java。

有两种实现,一种采用 Tree 并从中生成 JTree,另一种使用 drawString 并使 Tree 适合 JFrame 大小。

import java.awt.*;
import javax.swing.*;
import javax.swing.tree.*; 
import javax.swing.JTree;

/**
    (c) GPLv3 2010-09-24
*/
class MNode {

    MNode l; // left
    MNode r; // right
    int t;   // value

    public MNode (int t, MNode l, MNode r) {
        this.l = l;
        this.r = r;
        this.t = t;
    }

    public void add (MNode mn) { 
        if (l == null && t > mn.t) 
            l = mn;
        else if (t > mn.t) 
            l.add (mn);
        else if (r == null) 
            r = mn;
        else    r.add (mn);     
    }
}

abstract class NodePrinter {

    abstract void nodeprint (MNode root);
    int max (int a, int b) { return (a > b) ? a : b; }
    int depth (MNode n) 
    {
        if (n.l == null && n.r == null) return 1;
        if (n.l == null) return 1 + depth (n.r);
        if (n.r == null) return 1 + depth (n.l);
        return 1 + max (depth (n.l), depth (n.r));
    }
}

class SwingPrinter extends NodePrinter {

    void nodeprint (MNode root) {   
        JFrame jf = new JFrame ("Mein Freund, der Baum, ist tot");
        jf.setSize (380, 380);
        jf.setLocationRelativeTo (null);
        JTree jt = new JTree (translate2SwingTree (root));
        jf.add (jt);
        openSubnodes (0, jt);
        jf.setDefaultCloseOperation (WindowConstants.DISPOSE_ON_CLOSE); 
        jf.setVisible (true);
    }

    /**
        Open current branch.
        We need TreePath AND row.
        Open the MNode, iterierate with the row one step, and check there, 
        whether the Branch is a part of the new branch. 
        @param row the row of the starting MNode. 
    */
    void openSubnodes (int row, JTree jt) {
        TreePath tp = jt.getPathForRow (row);
        jt.expandRow (row);
        if (tp.isDescendant (jt.getPathForRow (row + 1)))
            openSubnodes (row + 1, jt);
    }

    DefaultMutableTreeNode translate2SwingTree (MNode ast) 
    {
        DefaultMutableTreeNode dmtn = new DefaultMutableTreeNode ("" + ast.t);
        if (ast.l != null) 
            dmtn.add (translate2SwingTree (ast.l));
        if (ast.r != null) 
            dmtn.add (translate2SwingTree (ast.r));
        return dmtn;
    }   
}

class TreeCanvas extends JPanel {

    private MNode root;
    private NodePrinter np;

    public TreeCanvas (MNode root, NodePrinter np) {
        this.root = root;
        this.np = np;
        d = np.depth (root);
        rows = (2 * d); // - 1
        cols = 2 << d;
    }

    private int d;
    private int rows;
    private int cols;

    // @override 
    public void paint (Graphics g) {
        Dimension dim = getSize ();
        int xf = dim.width / cols;
        int yf = dim.height / rows;
        int fontsize = (xf + yf) / 2;
        g.setFont (g.getFont().deriveFont (fontsize* 1.5f));
        xyPrint (root, dim.width/2, dim.width/2, 1, xf, yf, g);
    }

    /**
        ___50 60 70__________________
      10    |     x0    x0-x1:  (50,30) - (60, 10)  
      20    |    /  \   x0-x2:  (60,10) - (70, 30)
      30    |  x1    x2
    */
    void xyPrint (MNode n, int x, int dx, int y, int xf, int yf, Graphics g) {
        Graphics2D g2d = (Graphics2D) g;
        g2d.setStroke (new BasicStroke (3.0f));

        g.drawString ("" + n.t, x - xf, (y+1) * yf);
        g.setColor (Color.BLACK);
        if (n.l != null) {
            g.drawLine (x - (dx/2) + xf, (y+2) * yf, x, (y+1) * yf); // line:Up
            xyPrint (n.l, x - dx/2, dx/2, y + 2, xf, yf, g);
        }
        if (n.r != null) {
            g.drawLine (x + xf, (y+1) * yf, x + (dx/2), (y+2) * yf); // line down
            xyPrint (n.r, x + dx/2, dx/2, y + 2, xf, yf, g);
        }
    }
}

class ColorSwingPrinter extends NodePrinter {

    void nodeprint (MNode root) {   
        JFrame jf = new JFrame ("Rootnode");
        jf.setSize (650, 520);
        jf.setLocationRelativeTo (null);
        jf.add (new TreeCanvas (root, this));
        jf.setDefaultCloseOperation (WindowConstants.DISPOSE_ON_CLOSE);
        jf.setVisible (true);
    }
}

class RootNode extends MNode {

    public RootNode (String s) 
    {
        super (Integer.parseInt ("" + s.charAt (0)), null, null);
        for (String elem: s.substring (2).split (" "))
        {
            int i = Integer.parseInt (elem);
            MNode mn = new MNode (i, null, null);
            super.add (mn);
        }
    }   
}

public class NodePrinterTest {

    public static void main (String [] args) 
    {
        String param = "6 7 4 3 8 2 9 5";
        /*              6
                     4      7
                3       5       8
            2                       9
        */              
        RootNode root = new RootNode (param);
        ColorSwingPrinter printer = new ColorSwingPrinter ();
        printer.nodeprint (root);
        SwingPrinter printer2 = new SwingPrinter ();
        printer2.nodeprint (root);
    }   
}

打印树当然需要一些调整,因为您的节点可能没有公共属性 l、r 和 t,但您应该能够将它们转换为 left () 或 setLeft ()/getLeft () 等。

我不记得 ColorSwingPrinter 从哪里得名 - 它应该命名为 ResizingCanvasPrinter 或类似的名称。对不起。

这是两种实现的屏幕截图:
在此处输入图像描述

将较长的文本(如 cat、cat1、cat2)居中需要调整。到现在为止,第一个字符已放置在后代的中心

Here is a complete, runnable Demo, which is a rush translation from Scala code, so it isn't idiomatic Java.

There are two implementations, one which takes a Tree and produces a JTree from it, another one which uses drawString and fits the Tree to the JFrame size.

import java.awt.*;
import javax.swing.*;
import javax.swing.tree.*; 
import javax.swing.JTree;

/**
    (c) GPLv3 2010-09-24
*/
class MNode {

    MNode l; // left
    MNode r; // right
    int t;   // value

    public MNode (int t, MNode l, MNode r) {
        this.l = l;
        this.r = r;
        this.t = t;
    }

    public void add (MNode mn) { 
        if (l == null && t > mn.t) 
            l = mn;
        else if (t > mn.t) 
            l.add (mn);
        else if (r == null) 
            r = mn;
        else    r.add (mn);     
    }
}

abstract class NodePrinter {

    abstract void nodeprint (MNode root);
    int max (int a, int b) { return (a > b) ? a : b; }
    int depth (MNode n) 
    {
        if (n.l == null && n.r == null) return 1;
        if (n.l == null) return 1 + depth (n.r);
        if (n.r == null) return 1 + depth (n.l);
        return 1 + max (depth (n.l), depth (n.r));
    }
}

class SwingPrinter extends NodePrinter {

    void nodeprint (MNode root) {   
        JFrame jf = new JFrame ("Mein Freund, der Baum, ist tot");
        jf.setSize (380, 380);
        jf.setLocationRelativeTo (null);
        JTree jt = new JTree (translate2SwingTree (root));
        jf.add (jt);
        openSubnodes (0, jt);
        jf.setDefaultCloseOperation (WindowConstants.DISPOSE_ON_CLOSE); 
        jf.setVisible (true);
    }

    /**
        Open current branch.
        We need TreePath AND row.
        Open the MNode, iterierate with the row one step, and check there, 
        whether the Branch is a part of the new branch. 
        @param row the row of the starting MNode. 
    */
    void openSubnodes (int row, JTree jt) {
        TreePath tp = jt.getPathForRow (row);
        jt.expandRow (row);
        if (tp.isDescendant (jt.getPathForRow (row + 1)))
            openSubnodes (row + 1, jt);
    }

    DefaultMutableTreeNode translate2SwingTree (MNode ast) 
    {
        DefaultMutableTreeNode dmtn = new DefaultMutableTreeNode ("" + ast.t);
        if (ast.l != null) 
            dmtn.add (translate2SwingTree (ast.l));
        if (ast.r != null) 
            dmtn.add (translate2SwingTree (ast.r));
        return dmtn;
    }   
}

class TreeCanvas extends JPanel {

    private MNode root;
    private NodePrinter np;

    public TreeCanvas (MNode root, NodePrinter np) {
        this.root = root;
        this.np = np;
        d = np.depth (root);
        rows = (2 * d); // - 1
        cols = 2 << d;
    }

    private int d;
    private int rows;
    private int cols;

    // @override 
    public void paint (Graphics g) {
        Dimension dim = getSize ();
        int xf = dim.width / cols;
        int yf = dim.height / rows;
        int fontsize = (xf + yf) / 2;
        g.setFont (g.getFont().deriveFont (fontsize* 1.5f));
        xyPrint (root, dim.width/2, dim.width/2, 1, xf, yf, g);
    }

    /**
        ___50 60 70__________________
      10    |     x0    x0-x1:  (50,30) - (60, 10)  
      20    |    /  \   x0-x2:  (60,10) - (70, 30)
      30    |  x1    x2
    */
    void xyPrint (MNode n, int x, int dx, int y, int xf, int yf, Graphics g) {
        Graphics2D g2d = (Graphics2D) g;
        g2d.setStroke (new BasicStroke (3.0f));

        g.drawString ("" + n.t, x - xf, (y+1) * yf);
        g.setColor (Color.BLACK);
        if (n.l != null) {
            g.drawLine (x - (dx/2) + xf, (y+2) * yf, x, (y+1) * yf); // line:Up
            xyPrint (n.l, x - dx/2, dx/2, y + 2, xf, yf, g);
        }
        if (n.r != null) {
            g.drawLine (x + xf, (y+1) * yf, x + (dx/2), (y+2) * yf); // line down
            xyPrint (n.r, x + dx/2, dx/2, y + 2, xf, yf, g);
        }
    }
}

class ColorSwingPrinter extends NodePrinter {

    void nodeprint (MNode root) {   
        JFrame jf = new JFrame ("Rootnode");
        jf.setSize (650, 520);
        jf.setLocationRelativeTo (null);
        jf.add (new TreeCanvas (root, this));
        jf.setDefaultCloseOperation (WindowConstants.DISPOSE_ON_CLOSE);
        jf.setVisible (true);
    }
}

class RootNode extends MNode {

    public RootNode (String s) 
    {
        super (Integer.parseInt ("" + s.charAt (0)), null, null);
        for (String elem: s.substring (2).split (" "))
        {
            int i = Integer.parseInt (elem);
            MNode mn = new MNode (i, null, null);
            super.add (mn);
        }
    }   
}

public class NodePrinterTest {

    public static void main (String [] args) 
    {
        String param = "6 7 4 3 8 2 9 5";
        /*              6
                     4      7
                3       5       8
            2                       9
        */              
        RootNode root = new RootNode (param);
        ColorSwingPrinter printer = new ColorSwingPrinter ();
        printer.nodeprint (root);
        SwingPrinter printer2 = new SwingPrinter ();
        printer2.nodeprint (root);
    }   
}

Printing your Tree needs of course some adaption, since your Nodes will probably not have public attributes l, r and t, but you should be able to translate them to left () or setLeft ()/getLeft () and so on.

I don't remember where ColorSwingPrinter got it's name from - it should be named ResizingCanvasPrinter or something like that. I'm sorry.

Here is a screenshot of both implementations:
enter image description here

Centering longer texts like cat, cat1, cat2 will need adjustment. By now, the first character is placed at the center of the descendants

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文