2011-04-09 244 views

回答

3

我通常使用graphviz的點程序。它有一個簡單的online demo。這樣你就不必擔心間距或字體寬度。

3
cat 
    /\ 
cat1 cat2 

二叉樹由

  • 根節點
  • 左子樹
  • 一個右子樹

要打印這樣的樹,我們要打印的左邊和右邊的子樹除了另一邊(至少有一個空格)之外,然後在它上面打印根節點,集中在兩個子節點的中間ees,並用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方法?

  • 它會對葉節點(即無子節點)做什麼?
  • 如果我們有一個非葉節點,那麼如何將兩個這樣的調用(對於左右子樹)的結果(即指定的兩個字符串數組)結合到另一個字符串數組中,如上所述? (首先看看兩個陣列具有相同長度的簡單情況,即樹木具有相同的深度。)

祝你好運!

1

這是一個完整的,可運行的Demo,它是Scala代碼的翻譯版本,所以它不是慣用的Java。

有兩種實現方式,一種是採用Tree並從中生成JTree,另一種是使用drawString並將樹適合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,但你應該可以翻譯它們向左()或setLeft()/ getLeft( ) 等等。

我不記得ColorSwingPrinter從哪裏得到它的名字 - 它應該被命名爲ResizingCanvasPrinter或類似的東西。對不起。

下面是這兩種實現的截圖: enter image description here

定心像貓,CAT1較長的文本,CAT2將需要調整。到現在爲止,第一個字符被放置在後代的中心