如何打印二叉树图？

Question

如何在Java中打印二叉树,以便输出如下:

   4 
  / \ 
 2   5 

我的节点:

public class Node<A extends Comparable> {
    Node<A> left, right;
    A data;

    public Node(A data){
        this.data = data;
    }
}

Answer 1

按行打印[大]树.

输出示例:

z
??? c
?   ??? a
?   ??? b
??? d
??? e
?   ??? asdf
??? f

码:

public class TreeNode {

    final String name;
    final List<TreeNode> children;

    public TreeNode(String name, List<TreeNode> children) {
        this.name = name;
        this.children = children;
    }

    public String toString() {
        StringBuilder buffer = new StringBuilder(50);
        print(buffer, "", "");
        return buffer.toString();
    }

    private void print(StringBuilder buffer, String prefix, String childrenPrefix) {
        buffer.append(prefix);
        buffer.append(name);
        buffer.append('\n');
        for (Iterator<TreeNode> it = children.iterator(); it.hasNext();) {
            TreeNode next = it.next();
            if (it.hasNext()) {
                next.print(buffer, childrenPrefix + "??? ", childrenPrefix + "?   ");
            } else {
                next.print(buffer, childrenPrefix + "??? ", childrenPrefix + "    ");
            }
        }
    }
}

PS对不起,这个答案并不完全集中在"二元"树上.在请求打印树时,它只是用Google搜索.解决方案的灵感来自linux中的"tree"命令.

Answer 2

我已经创建了简单的二叉树打印机.您可以根据需要使用和修改它,但无论如何它都没有进行优化.我认为这里可以改进很多东西;)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BTreePrinterTest {

    private static Node<Integer> test1() {
        Node<Integer> root = new Node<Integer>(2);
        Node<Integer> n11 = new Node<Integer>(7);
        Node<Integer> n12 = new Node<Integer>(5);
        Node<Integer> n21 = new Node<Integer>(2);
        Node<Integer> n22 = new Node<Integer>(6);
        Node<Integer> n23 = new Node<Integer>(3);
        Node<Integer> n24 = new Node<Integer>(6);
        Node<Integer> n31 = new Node<Integer>(5);
        Node<Integer> n32 = new Node<Integer>(8);
        Node<Integer> n33 = new Node<Integer>(4);
        Node<Integer> n34 = new Node<Integer>(5);
        Node<Integer> n35 = new Node<Integer>(8);
        Node<Integer> n36 = new Node<Integer>(4);
        Node<Integer> n37 = new Node<Integer>(5);
        Node<Integer> n38 = new Node<Integer>(8);

        root.left = n11;
        root.right = n12;

        n11.left = n21;
        n11.right = n22;
        n12.left = n23;
        n12.right = n24;

        n21.left = n31;
        n21.right = n32;
        n22.left = n33;
        n22.right = n34;
        n23.left = n35;
        n23.right = n36;
        n24.left = n37;
        n24.right = n38;

        return root;
    }

    private static Node<Integer> test2() {
        Node<Integer> root = new Node<Integer>(2);
        Node<Integer> n11 = new Node<Integer>(7);
        Node<Integer> n12 = new Node<Integer>(5);
        Node<Integer> n21 = new Node<Integer>(2);
        Node<Integer> n22 = new Node<Integer>(6);
        Node<Integer> n23 = new Node<Integer>(9);
        Node<Integer> n31 = new Node<Integer>(5);
        Node<Integer> n32 = new Node<Integer>(8);
        Node<Integer> n33 = new Node<Integer>(4);

        root.left = n11;
        root.right = n12;

        n11.left = n21;
        n11.right = n22;

        n12.right = n23;
        n22.left = n31;
        n22.right = n32;

        n23.left = n33;

        return root;
    }

    public static void main(String[] args) {

        BTreePrinter.printNode(test1());
        BTreePrinter.printNode(test2());

    }
}

class Node<T extends Comparable<?>> {
    Node<T> left, right;
    T data;

    public Node(T data) {
        this.data = data;
    }
}

class BTreePrinter {

    public static <T extends Comparable<?>> void printNode(Node<T> root) {
        int maxLevel = BTreePrinter.maxLevel(root);

        printNodeInternal(Collections.singletonList(root), 1, maxLevel);
    }

    private static <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) {
        if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
            return;

        int floor = maxLevel - level;
        int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
        int firstSpaces = (int) Math.pow(2, (floor)) - 1;
        int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

        BTreePrinter.printWhitespaces(firstSpaces);

        List<Node<T>> newNodes = new ArrayList<Node<T>>();
        for (Node<T> node : nodes) {
            if (node != null) {
                System.out.print(node.data);
                newNodes.add(node.left);
                newNodes.add(node.right);
            } else {
                newNodes.add(null);
                newNodes.add(null);
                System.out.print(" ");
            }

            BTreePrinter.printWhitespaces(betweenSpaces);
        }
        System.out.println("");

        for (int i = 1; i <= endgeLines; i++) {
            for (int j = 0; j < nodes.size(); j++) {
                BTreePrinter.printWhitespaces(firstSpaces - i);
                if (nodes.get(j) == null) {
                    BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
                    continue;
                }

                if (nodes.get(j).left != null)
                    System.out.print("/");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(i + i - 1);

                if (nodes.get(j).right != null)
                    System.out.print("\\");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
            }

            System.out.println("");
        }

        printNodeInternal(newNodes, level + 1, maxLevel);
    }

    private static void printWhitespaces(int count) {
        for (int i = 0; i < count; i++)
            System.out.print(" ");
    }

    private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
        if (node == null)
            return 0;

        return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
    }

    private static <T> boolean isAllElementsNull(List<T> list) {
        for (Object object : list) {
            if (object != null)
                return false;
        }

        return true;
    }

}

输出1:

         2               
        / \       
       /   \      
      /     \     
     /       \    
     7       5       
    / \     / \   
   /   \   /   \  
   2   6   3   6   
  / \ / \ / \ / \ 
  5 8 4 5 8 4 5 8 

输出2:

       2               
      / \       
     /   \      
    /     \     
   /       \    
   7       5       
  / \       \   
 /   \       \  
 2   6       9   
    / \     /   
    5 8     4   

Answer 3

我为此做了一个改进的算法,它可以很好地处理不同大小的节点.它使用线条自上而下打印.

package alg;

import java.util.ArrayList;
import java.util.List;


/**
 * Binary tree printer
 * 
 * @author MightyPork
 */
public class TreePrinter
{
    /** Node that can be printed */
    public interface PrintableNode
    {
        /** Get left child */
        PrintableNode getLeft();


        /** Get right child */
        PrintableNode getRight();


        /** Get text to be printed */
        String getText();
    }


    /**
     * Print a tree
     * 
     * @param root
     *            tree root node
     */
    public static void print(PrintableNode root)
    {
        List<List<String>> lines = new ArrayList<List<String>>();

        List<PrintableNode> level = new ArrayList<PrintableNode>();
        List<PrintableNode> next = new ArrayList<PrintableNode>();

        level.add(root);
        int nn = 1;

        int widest = 0;

        while (nn != 0) {
            List<String> line = new ArrayList<String>();

            nn = 0;

            for (PrintableNode n : level) {
                if (n == null) {
                    line.add(null);

                    next.add(null);
                    next.add(null);
                } else {
                    String aa = n.getText();
                    line.add(aa);
                    if (aa.length() > widest) widest = aa.length();

                    next.add(n.getLeft());
                    next.add(n.getRight());

                    if (n.getLeft() != null) nn++;
                    if (n.getRight() != null) nn++;
                }
            }

            if (widest % 2 == 1) widest++;

            lines.add(line);

            List<PrintableNode> tmp = level;
            level = next;
            next = tmp;
            next.clear();
        }

        int perpiece = lines.get(lines.size() - 1).size() * (widest + 4);
        for (int i = 0; i < lines.size(); i++) {
            List<String> line = lines.get(i);
            int hpw = (int) Math.floor(perpiece / 2f) - 1;

            if (i > 0) {
                for (int j = 0; j < line.size(); j++) {

                    // split node
                    char c = ' ';
                    if (j % 2 == 1) {
                        if (line.get(j - 1) != null) {
                            c = (line.get(j) != null) ? '?' : '?';
                        } else {
                            if (j < line.size() && line.get(j) != null) c = '?';
                        }
                    }
                    System.out.print(c);

                    // lines and spaces
                    if (line.get(j) == null) {
                        for (int k = 0; k < perpiece - 1; k++) {
                            System.out.print(" ");
                        }
                    } else {

                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? " " : "?");
                        }
                        System.out.print(j % 2 == 0 ? "?" : "?");
                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? "?" : " ");
                        }
                    }
                }
                System.out.println();
            }

            // print line of numbers
            for (int j = 0; j < line.size(); j++) {

                String f = line.get(j);
                if (f == null) f = "";
                int gap1 = (int) Math.ceil(perpiece / 2f - f.length() / 2f);
                int gap2 = (int) Math.floor(perpiece / 2f - f.length() / 2f);

                // a number
                for (int k = 0; k < gap1; k++) {
                    System.out.print(" ");
                }
                System.out.print(f);
                for (int k = 0; k < gap2; k++) {
                    System.out.print(" ");
                }
            }
            System.out.println();

            perpiece /= 2;
        }
    }
}

要将它用于您的树,请让您的Node类实现PrintableNode.

示例输出:

                                         2952:0                                             
                    ?????????????????????????????????????????????????                       
                 1249:-1                                         5866:0                     
        ?????????????????????????                       ?????????????????????????           
     491:-1                  1572:0                  4786:1                  6190:0         
  ???????                                               ???????           ?????????????     
339:0                                                      5717:0      6061:0      6271:0   

Answer 4

public static class Node<T extends Comparable<T>> {
    T value;
    Node<T> left, right;

    public void insertToTree(T v) {
        if (value == null) {
            value = v;
            return;
        }
        if (v.compareTo(value) < 0) {
            if (left == null) {
                left = new Node<T>();
            }
            left.insertToTree(v);
        } else {
            if (right == null) {
                right = new Node<T>();
            }
            right.insertToTree(v);
        }
    }

    public void printTree(OutputStreamWriter out) throws IOException {
        if (right != null) {
            right.printTree(out, true, "");
        }
        printNodeValue(out);
        if (left != null) {
            left.printTree(out, false, "");
        }
    }
    private void printNodeValue(OutputStreamWriter out) throws IOException {
        if (value == null) {
            out.write("<null>");
        } else {
            out.write(value.toString());
        }
        out.write('\n');
    }
    // use string and not stringbuffer on purpose as we need to change the indent at each recursion
    private void printTree(OutputStreamWriter out, boolean isRight, String indent) throws IOException {
        if (right != null) {
            right.printTree(out, true, indent + (isRight ? "        " : " |      "));
        }
        out.write(indent);
        if (isRight) {
            out.write(" /");
        } else {
            out.write(" \\");
        }
        out.write("----- ");
        printNodeValue(out);
        if (left != null) {
            left.printTree(out, false, indent + (isRight ? " |      " : "        "));
        }
    }

}

将打印:

                 /----- 20
                 |       \----- 15
         /----- 14
         |       \----- 13
 /----- 12
 |       |       /----- 11
 |       \----- 10
 |               \----- 9
8
 |               /----- 7
 |       /----- 6
 |       |       \----- 5
 \----- 4
         |       /----- 3
         \----- 2
                 \----- 1

输入

8 4 12 2 6 10 14 1 3 5 7 9 11 13 20 15

这是@ anurag的回答的一个变种 - 看到额外的问题让我烦恼

Answer 5

改编自Vasya Novikov的答案,使其更加二进制,并使用StringBuilder效率(String在Java中将对象连接起来通常效率低下).

public StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) {
    if(right!=null) {
        right.toString(new StringBuilder().append(prefix).append(isTail ? "?   " : "    "), false, sb);
    }
    sb.append(prefix).append(isTail ? "??? " : "??? ").append(value.toString()).append("\n");
    if(left!=null) {
        left.toString(new StringBuilder().append(prefix).append(isTail ? "    " : "?   "), true, sb);
    }
    return sb;
}

@Override
public String toString() {
    return this.toString(new StringBuilder(), true, new StringBuilder()).toString();
}

输出:

?       ??? 7
?   ??? 6
?   ?   ??? 5
??? 4
    ?   ??? 3
    ??? 2
        ??? 1
            ??? 0

Answer 6

michal.kreuzman很好,我将不得不说.当我发现它真的帮助了我时,我自己在编写程序时感到很懒,并在网上搜索代码.但我担心它只能用于单个数字,就像你要使用多个数字一样,因为你使用的是空格而不是制表符,结构会被放错位置,程序将无法使用它.至于我后来的代码,我需要一些更大的输入(至少超过10个),这对我来说不起作用,并且在我没有找到任何东西后在网上搜索了很多,我自己做了一个程序.它现在有一些错误,现在我再次感觉懒得纠正它们但它打印得非常漂亮,节点可以承担任何大的价值.

树不会像提到的问题那样,但它旋转了270度:)

public static void printBinaryTree(TreeNode root, int level){
    if(root==null)
         return;
    printBinaryTree(root.right, level+1);
    if(level!=0){
        for(int i=0;i<level-1;i++)
            System.out.print("|\t");
            System.out.println("|-------"+root.val);
    }
    else
        System.out.println(root.val);
    printBinaryTree(root.left, level+1);
}    

将此函数放在您自己指定的TreeNode中,并将该级别初始化为0.

享受.以下是一些示例输出.

|       |       |-------11
|       |-------10
|       |       |-------9
|-------8
|       |       |-------7
|       |-------6
|       |       |-------5
4
|       |-------3
|-------2
|       |-------1


|       |       |       |-------10
|       |       |-------9
|       |-------8
|       |       |-------7
|-------6
|       |-------5
4
|       |-------3
|-------2
|       |-------1

唯一的问题是扩展分支我会尽快解决问题,但在此之前你也可以使用它.

Answer 7

您的树将需要每层的两倍距离:

       a
      / \
     /   \
    /     \
   /       \
   b       c
  / \     / \
 /   \   /   \
 d   e   f   g
/ \ / \ / \ / \
h i j k l m n o

您可以将树保存在一个数组数组中,每个深度都有一个数组:

[[a],[b,c],[d,e,f,g],[h,i,j,k,l,m,n,o]]

如果树未满,则需要在该数组中包含空值:

       a
      / \
     /   \
    /     \
   /       \
   b       c
  / \     / \
 /   \   /   \
 d   e   f   g
/ \   \ / \   \
h i   k l m   o
[[a],[b,c],[d,e,f,g],[h,i, ,k,l,m, ,o]]

然后,您可以遍历数组以打印树,在第一个元素之前打印空间,在元素之间打印空间,具体取决于深度并打印行,具体取决于是否填充了下一层数组中的相应元素.如果您的值可以超过一个字符长,则需要在创建数组表示时找到最长值,并相应地乘以所有宽度和行数.

Answer 8

我发现VasyaNovikov的答案对于打印大型通用树非常有用,并将其修改为二叉树

码:

class TreeNode {
    Integer data = null;
    TreeNode left = null;
    TreeNode right = null;

    TreeNode(Integer data) {this.data = data;}

    public void print() {
        print("", this, false);
    }

    public void print(String prefix, TreeNode n, boolean isLeft) {
        if (n != null) {
            System.out.println (prefix + (isLeft ? "|-- " : "\\-- ") + n.data);
            print(prefix + (isLeft ? "|   " : "    "), n.left, true);
            print(prefix + (isLeft ? "|   " : "    "), n.right, false);
        }
    }
}

样本输出:

\-- 7
    |-- 3
    |   |-- 1
    |   |   \-- 2
    |   \-- 5
    |       |-- 4
    |       \-- 6
    \-- 11
        |-- 9
        |   |-- 8
        |   \-- 10
        \-- 13
            |-- 12
            \-- 14

Answer 9

Scala语言的解决方案，类似于我在java中编写的内容：

case class Node(name: String, children: Node*) {

    def toTree: String = toTree("", "").mkString("\n")

    private def toTree(prefix: String, childrenPrefix: String): Seq[String] = {
        val firstLine = prefix + this.name

        val firstChildren = this.children.dropRight(1).flatMap { child =>
            child.toTree(childrenPrefix + "??? ", childrenPrefix + "?   ")
        }
        val lastChild = this.children.takeRight(1).flatMap { child =>
            child.toTree(childrenPrefix + "??? ", childrenPrefix + "    ")
        }
        firstLine +: firstChildren ++: lastChild
    }

}

输出示例：

vasya
??? frosya
?   ??? petya
?   ?   ??? masha
?   ??? kolya
??? frosya2

Answer 10

基于 VasyaNovikov 的回答。通过一些 Java 魔法进行了改进：泛型和函数式接口。

\n\n

/**\n * Print a tree structure in a pretty ASCII fromat.\n * @param prefix Currnet previx. Use "" in initial call!\n * @param node The current node. Pass the root node of your tree in initial call.\n * @param getChildrenFunc A {@link Function} that returns the children of a given node.\n * @param isTail Is node the last of its sibblings. Use true in initial call. (This is needed for pretty printing.)\n * @param <T> The type of your nodes. Anything that has a toString can be used.\n */\nprivate <T> void printTreeRec(String prefix, T node, Function<T, List<T>> getChildrenFunc, boolean isTail) {\n    String nodeName = node.toString();\n    String nodeConnection = isTail ? "\xe2\x94\x94\xe2\x94\x80\xe2\x94\x80 " : "\xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80 ";\n    log.debug(prefix + nodeConnection + nodeName);\n    List<T> children = getChildrenFunc.apply(node);\n    for (int i = 0; i < children.size(); i++) {\n        String newPrefix = prefix + (isTail ? "    " : "\xe2\x94\x82   ");\n        printTreeRec(newPrefix, children.get(i), getChildrenFunc, i == children.size()-1);\n    }\n}\n

\n\n

初始调用示例：

\n\n

Function<ChecksumModel, List<ChecksumModel>> getChildrenFunc = node -> getChildrenOf(node)\nprintTreeRec("", rootNode, getChildrenFunc, true);\n

\n\n

会输出类似的东西

\n\n

\xe2\x94\x94\xe2\x94\x80\xe2\x94\x80 rootNode\n    \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80 childNode1\n    \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80 childNode2\n    \xe2\x94\x82   \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80 childNode2.1\n    \xe2\x94\x82   \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80 childNode2.2\n    \xe2\x94\x82   \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80 childNode2.3\n    \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80 childNode3\n    \xe2\x94\x94\xe2\x94\x80\xe2\x94\x80 childNode4\n

\n