将二叉树打印到标准输出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/