將二叉樹打印到標準輸出Java

Question

我在Java中實現了紅/黑樹，並驗證我的樹是否正確，並且使調試更容易，我只需複製/粘貼將樹打印到標準輸出的方法即可。

對於輸入序列：29, 42, 23, 47, 11, 4
的方法將打印出：

有一點想象力其實這是一個紅色/黑色樹，只是沒有與節點之間的邊緣。
42是黑根與右黑色子47和左衝子23（紅色節點通過<包圍並>）等

這僅僅是細對於較小的樹木但成爲稍大複雜樹木。
現在，根位於左側，樹向右側擴展。 我想知道是否有任何現成的方法通過先打印出根，然後向下展開樹來打印出這樣的樹？

像這樣：

或者，如果沒有這樣現成的方法，我怎麼能改變目前的方法，因此打印像第二個形象？

這是當前的方法：

private static void printHelper(Node n, int indent) { 

    if (n.getRight() != null) { 
     printHelper(n.getRight(), indent + INDENT_STEP); 
    } 

    for (int i = 0; i < indent; i++) { 
     System.out.print(" "); 
    } 

    if (n.getColor() == BLACK) { 
     System.out.println(n.getValue()); 
    } else { 
     System.out.println("<" + n.getValue() + ">"); 
    } 

    if (n.getLeft() != null) { 
     printHelper(n.getLeft(), indent + INDENT_STEP); 
    } 
} 

而被調用與所述樹的根爲節點和0作爲縮進（和INDENT_STEP是4）。

編輯：現在我認爲這不是紅/黑樹的特定問題。因此，我從標題中刪除紅色/黑色，並用二叉樹替換它。

Answer 1

該死的，我很接近得到這個達到預期效果！有誰知道爲什麼這仍然達不到要求的結果？

package tree; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 

public class Tree { 

    private final static int BLACK = 1; 
    private final static int RED = 2; 
    private Tree left = null; 
    private Tree right = null; 
    private int color = BLACK; 
    private String value = ""; 

    Tree(final Tree left, final Tree right, final int color, final String value) { 
     this.left = left; 
     this.right = right; 
     this.color = color; 
     this.value = value; 
    } 

    Tree getLeft() { 
     return left; 
    } 

    Tree getRight() { 
     return right; 
    } 

    int getColor() { 
     return color; 
    } 

    String getValue() { 
     return value; 
    } 

    public static void main(String[] args) { 

     Tree leaf1 = new Tree(null, null, RED, "20"); 
     Tree leaf2 = new Tree(null, null, BLACK, "30"); 
     Tree leaf3 = new Tree(null, null, RED, "2"); 
     Tree leaf4 = new Tree(null, null, RED, "100"); 
     Tree leaf5 = new Tree(null, null, BLACK, "5"); 

     Tree middle1 = new Tree(leaf1, leaf2, RED, "40"); 
     Tree middle2 = new Tree(middle1, leaf3, BLACK, "200"); 
     Tree middle3 = new Tree(leaf4, leaf5, RED, "3"); 

     Tree root = new Tree(middle2, middle3, RED, "50"); 

     printTree(root); 

    } 

    static void printTree(final Tree t) { 

     final Map<Tree, Integer> widths = new HashMap<Tree, Integer>(); 
     final Map<Tree, Integer> offsets = new HashMap<Tree, Integer>(); 

     setWidths(widths, t); 

     setOffsets(offsets, widths, t, widths.get(t)/2); 

     final List<Tree> root = new ArrayList<Tree>(); 
     root.add(t); 
     printTree(offsets, root); 

    } 

    static int setWidths(final Map<Tree, Integer> widths, final Tree t) { 

     if(widths.containsKey(t)) 
      return widths.get(t); 

     int width = (t.getColor() == BLACK) ? t.getValue().length() 
        : t.getValue().length() + 2; 

     final Tree left = t.getLeft(); 
     final Tree right = t.getRight(); 

     if(left != null) 
      width += setWidths(widths, left); 
     if(right != null) 
      width += setWidths(widths, right); 

     widths.put(t, width); 

     return width; 

    } 

    static void setOffsets(final Map<Tree, Integer> offsets, final Map<Tree, Integer> widths, 
      final Tree t, final int offset) { 

     offsets.put(t, offset); 

     System.out.println("Parent offset for node " + t.getValue() + ", offset " + offset); 

     final Tree left = t.getLeft(); 
     final Tree right = t.getRight(); 

     if(left != null) 
      setOffsets(offsets, widths, left, offset - widths.get(left)/2); 
     if(right != null) 
      setOffsets(offsets, widths, right, offset + widths.get(right)/2); 

    } 

    static void printTree(final Map<Tree, Integer> offsets, final List<Tree> trees) { 

     if(trees.isEmpty()) 
      return; 

     final List<Tree> children = new ArrayList<Tree>(); 
     int linePos = 0; 

     for(int i = 0; i < trees.size(); ++i) { 

      final Tree t = trees.get(i); 

      int offset = offsets.get(t); 
      final char[] lead = new char[Math.max(offset - linePos, 0)]; 
      Arrays.fill(lead, ' '); 

      System.out.print(new String(lead)); 
      linePos += Math.max(offset, 0); 

      if(t.getColor() == RED) { 
       System.out.print(t.getValue()); 
       linePos += t.getValue().length(); 
      } else { 
       System.out.print("<" + t.getValue() + ">"); 
       linePos += t.getValue().length() + 2; 
      } 

      if(t.getLeft() != null) 
       children.add(t.getLeft()); 
      if(t.getRight() != null) 
       children.add(t.getRight()); 

     } 

     System.out.println(""); 

     printTree(offsets, children); 

    } 

} 

Answer 2

也許你可能會考慮使用不同的方法繪製更復雜的樹。一個很好的工具是dot language，它是Graphviz軟件的一部分。

這裏有一個如何從蟒蛇內寫入點紅黑樹的例子： http://code.activestate.com/recipes/576817-red-black-tree/