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

   4 
  / \ 
 2   5 

我的节点:

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

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

当前回答

与垂直表示相比,水平表示有点复杂。垂直打印只是简单的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排序。

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

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

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

其他回答

一个Scala解决方案,改编自Vasya Novikov的答案,专门用于二叉树:

/** An immutable Binary Tree. */
case class BTree[T](value: T, left: Option[BTree[T]], right: Option[BTree[T]]) {

  /* Adapted from: http://stackoverflow.com/a/8948691/643684 */
  def pretty: String = {
    def work(tree: BTree[T], prefix: String, isTail: Boolean): String = {
      val (line, bar) = if (isTail) ("└── ", " ") else ("├── ", "│")

      val curr = s"${prefix}${line}${tree.value}"

      val rights = tree.right match {
        case None    => s"${prefix}${bar}   ├── ∅"
        case Some(r) => work(r, s"${prefix}${bar}   ", false)
      }

      val lefts = tree.left match {
        case None    => s"${prefix}${bar}   └── ∅"
        case Some(l) => work(l, s"${prefix}${bar}   ", true)
      }

      s"${curr}\n${rights}\n${lefts}"

    }

    work(this, "", true)
  }
}

我已经创建了简单的二叉树打印机。您可以随心所欲地使用和修改它,但无论如何它都没有优化。我认为这里有很多东西可以改进;)

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   

我需要在我的一个项目中打印一个二叉树,为此我准备了一个java类TreePrinter,其中一个示例输出是:

                [+]
               /   \
              /     \
             /       \
            /         \
           /           \
        [*]             \
       /   \             [-]
[speed]     [2]         /   \
                    [45]     [12]

下面是TreePrinter类和TextNode类的代码。为了打印任何树,你可以用TextNode类创建一个等效的树。


import java.util.ArrayList;

public class TreePrinter {

    public TreePrinter(){
    }

    public static String TreeString(TextNode root){
        ArrayList layers = new ArrayList();
        ArrayList bottom = new ArrayList();

        FillBottom(bottom, root);  DrawEdges(root);

        int height = GetHeight(root);
        for(int i = 0; i  s.length()) min = s.length();

            if(!n.isEdge) s += "[";
            s += n.text;
            if(!n.isEdge) s += "]";

            layers.set(n.depth, s);
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i  temp = new ArrayList();

            for(int i = 0; i  0) temp.get(i-1).left = x;
                temp.add(x);
            }

            temp.get(count-1).left = n.left;
            n.left.depth = temp.get(count-1).depth+1;
            n.left = temp.get(0);

            DrawEdges(temp.get(count-1).left);
        }
        if(n.right != null){
            int count = n.right.x - (n.x + n.text.length() + 2);
            ArrayList temp = new ArrayList();

            for(int i = 0; i  0) temp.get(i-1).right = x;
                temp.add(x);
            }

            temp.get(count-1).right = n.right;
            n.right.depth = temp.get(count-1).depth+1;
            n.right = temp.get(0);  

            DrawEdges(temp.get(count-1).right);
        }
    }

    private static void FillBottom(ArrayList bottom, TextNode n){
        if(n == null) return;

        FillBottom(bottom, n.left);

        if(!bottom.isEmpty()){            
            int i = bottom.size()-1;
            while(bottom.get(i).isEdge) i--;
            TextNode last = bottom.get(i);

            if(!n.isEdge) n.x = last.x + last.text.length() + 3;
        }
        bottom.add(n);
        FillBottom(bottom, n.right);
    }

    private static boolean isLeaf(TextNode n){
        return (n.left == null && n.right == null);
    }

    private static int GetHeight(TextNode n){
        if(n == null) return 0;

        int l = GetHeight(n.left);
        int r = GetHeight(n.right);

        return Math.max(l, r) + 1;
    }
}


class TextNode {
    public String text;
    public TextNode parent, left, right;
    public boolean isEdge;
    public int x, depth;

    public TextNode(String text){
        this.text = text;
        parent = null; left = null; right = null;
        isEdge = false;
        x = 0; depth = 0;
    }
}

最后,这里是一个打印给定样本的测试类:


public class Test {

    public static void main(String[] args){
        TextNode root = new TextNode("+");
        root.left = new TextNode("*");            root.left.parent = root;
        root.right = new TextNode("-");           root.right.parent = root;
        root.left.left = new TextNode("speed");   root.left.left.parent = root.left;
        root.left.right = new TextNode("2");      root.left.right.parent = root.left;
        root.right.left = new TextNode("45");     root.right.left.parent = root.right;
        root.right.right = new TextNode("12");    root.right.right.parent = root.right;

        System.out.println(TreePrinter.TreeString(root));
    }
}
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位整数(我懒得让它通用)

与垂直表示相比,水平表示有点复杂。垂直打印只是简单的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排序。

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

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

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