我如何在Java中打印一个二叉树,这样输出就像:

   4 
  / \ 
 2   5 

我的节点:

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

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

当前回答

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回答的一个变体——看到额外的|让我很烦

其他回答

private StringBuilder prettyPrint(Node root, int currentHeight, int totalHeight) {
        StringBuilder sb = new StringBuilder();
        int spaces = getSpaceCount(totalHeight-currentHeight + 1);
        if(root == null) {
            //create a 'spatial' block and return it
            String row = String.format("%"+(2*spaces+1)+"s%n", "");
            //now repeat this row space+1 times
            String block = new String(new char[spaces+1]).replace("\0", row);
            return new StringBuilder(block);
        }
        if(currentHeight==totalHeight) return new StringBuilder(root.data+"");
        int slashes = getSlashCount(totalHeight-currentHeight +1);
        sb.append(String.format("%"+(spaces+1)+"s%"+spaces+"s", root.data+"", ""));
        sb.append("\n");
        //now print / and \
        // but make sure that left and right exists
        char leftSlash = root.left == null? ' ':'/';
        char rightSlash = root.right==null? ' ':'\\';
        int spaceInBetween = 1;
        for(int i=0, space = spaces-1; i<slashes; i++, space --, spaceInBetween+=2) {
            for(int j=0; j<space; j++) sb.append(" ");
            sb.append(leftSlash);
            for(int j=0; j<spaceInBetween; j++) sb.append(" ");
            sb.append(rightSlash+"");
            for(int j=0; j<space; j++) sb.append(" ");
            sb.append("\n");
        }
        //sb.append("\n");

        //now get string representations of left and right subtrees
        StringBuilder leftTree = prettyPrint(root.left, currentHeight+1, totalHeight);
        StringBuilder rightTree = prettyPrint(root.right, currentHeight+1, totalHeight);
        // now line by line print the trees side by side
        Scanner leftScanner = new Scanner(leftTree.toString());
        Scanner rightScanner = new Scanner(rightTree.toString());
//      spaceInBetween+=1;
        while(leftScanner.hasNextLine()) {
            if(currentHeight==totalHeight-1) {
                sb.append(String.format("%-2s %2s", leftScanner.nextLine(), rightScanner.nextLine()));
                sb.append("\n");
                spaceInBetween-=2;              
            }
            else {
                sb.append(leftScanner.nextLine());
                sb.append(" ");
                sb.append(rightScanner.nextLine()+"\n");
            }
        }

        return sb;

    }
private int getSpaceCount(int height) {
        return (int) (3*Math.pow(2, height-2)-1);
    }
private int getSlashCount(int height) {
        if(height <= 3) return height -1;
        return (int) (3*Math.pow(2, height-3)-1);
    }

https://github.com/murtraja/java-binary-tree-printer

只适用于1到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   

与垂直表示相比,水平表示有点复杂。垂直打印只是简单的RNL(右->节点->左或镜像的顺序)遍历,以便先打印右子树,然后打印左子树。

def printFullTree(root, delim=' ', idnt=[], left=None):
    if root:
        idnt.append(delim)
        x, y = setDelims(left)
        printFullTree(root.right, x, idnt, False)
        indent2(root.val, idnt)
        printFullTree(root.left, y, idnt, True)
        idnt.pop()

def setDelims(left):
    x = ' '; y='|'
    return (y,x) if (left == True) else (x,y) if (left == False) else (x,x)

def indent2(x, idnt, width=6):
    for delim in idnt:
        print(delim + ' '*(width-1), end='')
    print('|->', x)
output:
                        |-> 15
                  |-> 14
                  |     |-> 13
            |-> 12
            |     |     |-> 11
            |     |-> 10
            |           |-> 9
      |-> 8
            |           |-> 7
            |     |-> 6
            |     |     |-> 4
            |-> 3
                  |     |-> 2
                  |-> 1
                        |-> 0

在水平表示中,显示由TreeMap的HashMap或HashMap<Integer, TreeMap<Integer, Object>> xy构建;其中HashMap包含节点的y轴/level_no作为Key, TreeMap作为value。Treemap内部保存同一级别的所有节点,按它们的x轴值排序,作为键,从最左端开始-ve,根=0,最右端=+ve。

如果使用自平衡树/Treap,则使用HashMap使算法在每个级别的O(1)查找中工作,并在O(logn)中使用TreeMap排序。

不过,在这样做的时候,不要忘记为空子存储占位符,例如' '/空格,这样树看起来就像预期的那样。

现在唯一剩下的就是计算水平节点的距离,这可以用一些数学计算来完成,

计算树的宽度和高度。 一旦完成,在显示节点时,根据计算的宽度,高度和倾斜信息(如果有的话),以最佳距离呈现它们。

根据VasyaNovikov的回答。改进了一些Java魔术:泛型和函数接口。

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

初始调用示例:

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

将输出如下内容

└── rootNode
    ├── childNode1
    ├── childNode2
    │   ├── childNode2.1
    │   ├── childNode2.2
    │   └── childNode2.3
    ├── childNode3
    └── childNode4

在控制台打印:

                                                500
                       700                                             300   
    200                                   400                                                                                          

简单代码:

public int getHeight()
    {
        if(rootNode == null) return -1;
        return getHeight(rootNode);
    }

    private int getHeight(Node node)
    {
        if(node == null) return -1;

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

    public void printBinaryTree(Node rootNode)
    {
        Queue<Node> rootsQueue = new LinkedList<Node>();
        Queue<Node> levelQueue = new LinkedList<Node>();
        levelQueue.add(rootNode);
        int treeHeight = getHeight();
        int firstNodeGap;
        int internalNodeGap;
        int copyinternalNodeGap;
        while(true)
        {
            System.out.println("");
            internalNodeGap = (int)(Math.pow(2, treeHeight + 1) -1);  
            copyinternalNodeGap = internalNodeGap;
            firstNodeGap = internalNodeGap/2;

            boolean levelFirstNode = true;

            while(!levelQueue.isEmpty())
            {
                internalNodeGap = copyinternalNodeGap;
                Node currNode = levelQueue.poll();
                if(currNode != null)
                {
                    if(levelFirstNode)
                    {
                        while(firstNodeGap > 0)
                        {
                            System.out.format("%s", "   ");
                            firstNodeGap--; 
                        }
                        levelFirstNode =false;
                    }
                    else
                    {
                        while(internalNodeGap>0)
                        {
                            internalNodeGap--;
                            System.out.format("%s", "   ");
                        }
                    }
                    System.out.format("%3d",currNode.data);
                    rootsQueue.add(currNode);
                }
            }

            --treeHeight;

            while(!rootsQueue.isEmpty())
            {
                Node currNode = rootsQueue.poll();
                if(currNode != null)
                {
                    levelQueue.add(currNode.left);
                    levelQueue.add(currNode.right);
                }
            }

            if(levelQueue.isEmpty()) break;
        }

    }