How to print binary tree diagram?

2019-01-01 08:23发布

站内文章 / Java
60 0 0

问题:

How can I print a binary tree in Java so that the output is like:

   4 
  / \\ 
 2   5

My node:

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

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

回答1:

I\'ve created simple binary tree printer. You can use and modify it as you want, but it\'s not optimized anyway. I think that a lot of things can be improved here ;)

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;
    }

}

Output 1 :

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

Output 2 :

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


回答2:

Print a [large] tree by lines.

output example:

└── z
    ├── c
    │   ├── a
    │   └── b
    ├── d
    ├── e
    │   └── asdf
    └── f

code:

public class TreeNode {

    final String name;
    final List<TreeNode> children;

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

    public void print() {
        print(\"\", true);
    }

    private void print(String prefix, boolean isTail) {
        System.out.println(prefix + (isTail ? \"└── \" : \"├── \") + name);
        for (int i = 0; i < children.size() - 1; i++) {
            children.get(i).print(prefix + (isTail ? \"    \" : \"│   \"), false);
        }
        if (children.size() > 0) {
            children.get(children.size() - 1)
                    .print(prefix + (isTail ?\"    \" : \"│   \"), true);
        }
    }
}

P.S. Sorry, this answer doesn\'t exactly focus on \"binary\" trees. It just gets googled when requesting somewhat for printing a tree. Solution is inspired by the \"tree\" command in linux.



回答3:

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 ? \" |      \" : \"        \"));
        }
    }

}

will print:

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

for the input

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

this is a variant from @anurag\'s answer - it was bugging me to see the extra |s



回答4:

I\'ve made an improved algorithm for this, which handles nicely nodes with different size. It prints top-down using lines.

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;
        }
    }
}

To use this for your Tree, let your Node class implement PrintableNode.

Example output:

                                         2952:0                                             
                    ┌───────────────────────┴───────────────────────┐                       
                 1249:-1                                         5866:0                     
        ┌───────────┴───────────┐                       ┌───────────┴───────────┐           
     491:-1                  1572:0                  4786:1                  6190:0         
  ┌─────┘                                               └─────┐           ┌─────┴─────┐     
339:0                                                      5717:0      6061:0      6271:0


回答5:

Adapted from Vasya Novikov\'s answer to make it more binary, and use a StringBuilder for efficiency (concatenating String objects together in Java is generally inefficient).

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();
}

Output:

│       ┌── 7
│   ┌── 6
│   │   └── 5
└── 4
    │   ┌── 3
    └── 2
        └── 1
            └── 0


回答6:

michal.kreuzman nice one i will have to say. I was feeling lazy to make a program by myself and searching for code on net when i found this it really helped me. But I am afraid to see that it works only for single digits as if you are going to use more than one digit, since you are using spaces and not tabs the structure is going to get misplaced and the program will loose its use. As for my later codes i needed some bigger inputs (at least more than 10) this didn\'t work for me, and after searching a lot on net when i didn\'t found anything, i made a program myself. It has some bugs now, again right now i am feeling lazy to correct them but it prints the very beautifully and the nodes can take any large value.

The tree is not going to be as the question mentions but it is 270 degrees rotated :)

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);
}

Place this function with your own specified TreeNode and keep the level initialy 0.

and enjoy. Here are some of the sample outputs.

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


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

Only problem is with the extending branches i will try to solve the problem as soon as possible but till then you can use it too.



回答7:

Your tree will need twice the distance for each layer:

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

You can save your tree in an array of arrays, one array for every depth:

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

If your tree is not full, you need to include empty values in that array:

       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]]

Then you can iterate over the array to print your tree, printing spaces before the first element and between the elements depending on the depth and printing the lines depending on if the corresponding elements in the array for the next layer are filled or not. If your values can be more than one character long, you need to find the longest value while creating the array representation and multiply all widths and the number of lines accordingly.



回答8:

I found VasyaNovikov\'s answer very useful for printing a large general tree, and modified it for a binary tree

Code:

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);
        }
    }
}

Sample output:

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


回答9:

public void printPreety() {
    List<TreeNode> list = new ArrayList<TreeNode>();
    list.add(head);
    printTree(list, getHeight(head));
}

public int getHeight(TreeNode head) {

    if (head == null) {
        return 0;
    } else {
        return 1 + Math.max(getHeight(head.left), getHeight(head.right));
    }
}

/**
 * pass head node in list and height of the tree 
 * 
 * @param levelNodes
 * @param level
 */
private void printTree(List<TreeNode> levelNodes, int level) {

    List<TreeNode> nodes = new ArrayList<TreeNode>();

    //indentation for first node in given level
    printIndentForLevel(level);

    for (TreeNode treeNode : levelNodes) {

        //print node data
        System.out.print(treeNode == null?\" \":treeNode.data);

        //spacing between nodes
        printSpacingBetweenNodes(level);

        //if its not a leaf node
        if(level>1){
            nodes.add(treeNode == null? null:treeNode.left);
            nodes.add(treeNode == null? null:treeNode.right);
        }
    }
    System.out.println();

    if(level>1){        
        printTree(nodes, level-1);
    }
}

private void printIndentForLevel(int level){
    for (int i = (int) (Math.pow(2,level-1)); i >0; i--) {
        System.out.print(\" \");
    }
}

private void printSpacingBetweenNodes(int level){
    //spacing between nodes
    for (int i = (int) ((Math.pow(2,level-1))*2)-1; i >0; i--) {
        System.out.print(\" \");
    }
}


Prints Tree in following format:
                4                               
        3               7               
    1               5       8       
      2                       10   
                             9


回答10:

A solution in Scala language, analogous to what I wrote in 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
    }

}

Output example:

vasya
├── frosya
│   ├── petya
│   │   └── masha
│   └── kolya
└── frosya2

Comparing to the java solution, it does not have the unneeded base indentation and contatenates String-s a bit better (StringBuilder under the hood). It can still cause a StackOverflow exception for a deeply nested tree. Room for improvement.;-)



回答11:

This is a very simple solution to print out a tree. It is not that pretty, but it is really simple:

enum { kWidth = 6 };
void PrintSpace(int n)
{
  for (int i = 0; i < n; ++i)
    printf(\" \");
}

void PrintTree(struct Node * root, int level)
{
  if (!root) return;
  PrintTree(root->right, level + 1);
  PrintSpace(level * kWidth);
  printf(\"%d\", root->data);
  PrintTree(root->left, level + 1);
}

Sample output:

      106
            105
104
            103
                  102
                        101
      100


回答12:

I know you guys all have great solution; I just want to share mine - maybe that is not the best way, but it is perfect for myself!

With python and pip on, it is really quite simple! BOOM!

On Mac or Ubuntu (mine is mac)

  1. open terminal
  2. $ pip install drawtree
  3. $python, enter python console; you can do it in other way
  4. from drawtree import draw_level_order
  5. draw_level_order(\'{2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}\')

DONE!

        2
       / \\
      /   \\
     /     \\
    1       3
   / \\     / \\
  0   7   9   1
 /   / \\     / \\
2   1   0   8   8
       /
      7

Source tracking:

Before I saw this post, I went google \"binary tree plain text\"

And I found this https://www.reddit.com/r/learnpython/comments/3naiq8/draw_binary_tree_in_plain_text/, direct me to this https://github.com/msbanik/drawtree



回答13:

I needed to print a binary tree in one of my projects, for that I have prepared a java class TreePrinter, one of the sample output is:

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

Here is the code for class TreePrinter along with class TextNode. For printing any tree you can just create an equivalent tree with TextNode class.


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;
    }
}

Finally here is a test class for printing given sample:


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));
    }
}


回答14:

You can use an applet to visualize this very easily. You need to print the following items.

  1. Print the nodes as circles with some visible radius

    • Get the coordinates for each node.

    • The x coordinate can be visualized as the number of nodes visited before the node is visited in its inorder traversal.

    • The y coordinate can be visualized as the depth of the particular node.

  1. Print the lines between parent and children

    • This can be done by maintaining the x and y coordinates of the nodes and the parents of each node in separate lists.

    • For each node except root join each node with its parent by taking the x and y coordinates of both the child and the parent.



回答15:

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

only works for 1 to 2 digit integers (i was lazy to make it generic)

\"skewed\" \"full\"



回答16:

Print in Console: 

                                                500
                       700                                             300   
    200                                   400

Simple code :

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;
        }

    }


回答17:

Here\'s a very versatile tree printer. Not the best looking, but it handles a lot of cases. Feel free to add slashes if you can figure that out. \"enter

package com.tomac120.NodePrinter;

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

/**
 * Created by elijah on 6/28/16.
 */
public class NodePrinter{
    final private List<List<PrintableNodePosition>> nodesByRow;
    int maxColumnsLeft = 0;
    int maxColumnsRight = 0;
    int maxTitleLength = 0;
    String sep = \" \";
    int depth = 0;

    public NodePrinter(PrintableNode rootNode, int chars_per_node){
        this.setDepth(rootNode,1);
        nodesByRow = new ArrayList<>(depth);
        this.addNode(rootNode._getPrintableNodeInfo(),0,0);
        for (int i = 0;i<chars_per_node;i++){
            //sep += \" \";
        }
    }

    private void setDepth(PrintableNode info, int depth){
        if (depth > this.depth){
            this.depth = depth;
        }
        if (info._getLeftChild() != null){
            this.setDepth(info._getLeftChild(),depth+1);
        }
        if (info._getRightChild() != null){
            this.setDepth(info._getRightChild(),depth+1);
        }
    }

    private void addNode(PrintableNodeInfo node, int level, int position){
        if (position < 0 && -position > maxColumnsLeft){
            maxColumnsLeft = -position;
        }
        if (position > 0 && position > maxColumnsRight){
            maxColumnsRight = position;
        }
        if (node.getTitleLength() > maxTitleLength){
           maxTitleLength = node.getTitleLength();
        }
        List<PrintableNodePosition> row = this.getRow(level);
        row.add(new PrintableNodePosition(node, level, position));
        level++;

        int depthToUse = Math.min(depth,6);
        int levelToUse = Math.min(level,6);
        int offset = depthToUse - levelToUse-1;
        offset = (int)(Math.pow(offset,Math.log(depthToUse)*1.4));
        offset = Math.max(offset,3);


        PrintableNodeInfo leftChild = node.getLeftChildInfo();
        PrintableNodeInfo rightChild = node.getRightChildInfo();
        if (leftChild != null){
            this.addNode(leftChild,level,position-offset);
        }
        if (rightChild != null){
            this.addNode(rightChild,level,position+offset);
        }
    }

    private List<PrintableNodePosition> getRow(int row){
        if (row > nodesByRow.size() - 1){
            nodesByRow.add(new LinkedList<>());
        }
        return nodesByRow.get(row);
    }

    public void print(){
        int max_chars = this.maxColumnsLeft+maxColumnsRight+1;
        int level = 0;
        String node_format = \"%-\"+this.maxTitleLength+\"s\";
        for (List<PrintableNodePosition> pos_arr : this.nodesByRow){
            String[] chars = this.getCharactersArray(pos_arr,max_chars);
            String line = \"\";
            int empty_chars = 0;
            for (int i=0;i<chars.length+1;i++){
                String value_i = i < chars.length ? chars[i]:null;
                if (chars.length + 1 == i || value_i != null){
                    if (empty_chars > 0) {
                        System.out.print(String.format(\"%-\" + empty_chars + \"s\", \" \"));
                    }
                    if (value_i != null){
                        System.out.print(String.format(node_format,value_i));
                        empty_chars = -1;
                    } else{
                        empty_chars = 0;
                    }
                } else {
                    empty_chars++;
                }
            }
            System.out.print(\"\\n\");

            int depthToUse = Math.min(6,depth);
            int line_offset = depthToUse - level;
            line_offset *= 0.5;
            line_offset = Math.max(0,line_offset);

            for (int i=0;i<line_offset;i++){
                System.out.println(\"\");
            }


            level++;
        }
    }

    private String[] getCharactersArray(List<PrintableNodePosition> nodes, int max_chars){
        String[] positions = new String[max_chars+1];
        for (PrintableNodePosition a : nodes){
            int pos_i = maxColumnsLeft + a.column;
            String title_i = a.nodeInfo.getTitleFormatted(this.maxTitleLength);
            positions[pos_i] = title_i;
        }
        return positions;
    }
}

NodeInfo class

package com.tomac120.NodePrinter;

/**
 * Created by elijah on 6/28/16.
 */
public class PrintableNodeInfo {
    public enum CLI_PRINT_COLOR {
        RESET(\"\\u001B[0m\"),
        BLACK(\"\\u001B[30m\"),
        RED(\"\\u001B[31m\"),
        GREEN(\"\\u001B[32m\"),
        YELLOW(\"\\u001B[33m\"),
        BLUE(\"\\u001B[34m\"),
        PURPLE(\"\\u001B[35m\"),
        CYAN(\"\\u001B[36m\"),
        WHITE(\"\\u001B[37m\");

        final String value;
        CLI_PRINT_COLOR(String value){
            this.value = value;
        }

        @Override
        public String toString() {
            return value;
        }
    }
    private final String title;
    private final PrintableNode leftChild;
    private final PrintableNode rightChild;
    private final CLI_PRINT_COLOR textColor;

    public PrintableNodeInfo(String title, PrintableNode leftChild, PrintableNode rightChild){
        this(title,leftChild,rightChild,CLI_PRINT_COLOR.BLACK);
    }

    public PrintableNodeInfo(String title, PrintableNode leftChild, PrintableNode righthild, CLI_PRINT_COLOR textColor){
        this.title = title;
        this.leftChild = leftChild;
        this.rightChild = righthild;
        this.textColor = textColor;
    }

    public String getTitle(){
        return title;
    }

    public CLI_PRINT_COLOR getTextColor(){
        return textColor;
    }

    public String getTitleFormatted(int max_chars){
        return this.textColor+title+CLI_PRINT_COLOR.RESET;
        /*
        String title = this.title.length() > max_chars ? this.title.substring(0,max_chars+1):this.title;
        boolean left = true;
        while(title.length() < max_chars){
            if (left){
                title = \" \"+title;
            } else {
                title = title + \" \";
            }
        }
        return this.textColor+title+CLI_PRINT_COLOR.RESET;*/
    }

    public int getTitleLength(){
        return title.length();
    }

    public PrintableNodeInfo getLeftChildInfo(){
        if (leftChild == null){
            return null;
        }
        return leftChild._getPrintableNodeInfo();
    }

    public PrintableNodeInfo getRightChildInfo(){
        if (rightChild == null){
            return null;
        }
        return rightChild._getPrintableNodeInfo();
    }
}

NodePosition class

package com.tomac120.NodePrinter;

/**
 * Created by elijah on 6/28/16.
 */
public class PrintableNodePosition implements Comparable<PrintableNodePosition> {
    public final int row;
    public final int column;
    public final PrintableNodeInfo nodeInfo;
    public PrintableNodePosition(PrintableNodeInfo nodeInfo, int row, int column){
        this.row = row;
        this.column = column;
        this.nodeInfo = nodeInfo;
    }

    @Override
    public int compareTo(PrintableNodePosition o) {
        return Integer.compare(this.column,o.column);
    }
}

And, finally, Node Interface

package com.tomac120.NodePrinter;

/**
 * Created by elijah on 6/28/16.
 */
public interface PrintableNode {
    PrintableNodeInfo _getPrintableNodeInfo();
    PrintableNode _getLeftChild();
    PrintableNode _getRightChild();
}


回答18:

C++:

  struct node{
    string key;
    struct node *left, *right;
  };

  void printBFS(struct node *root){
    std::queue<struct node *> q;
    q.push(root);

    while(q.size() > 0){
      int levelNodes = q.size();
      while(levelNodes > 0){
        struct node *p = q.front(); 
        q.pop();
        cout << \" \" << p->key ;
        if(p->left != NULL) q.push(p->left);
        if(p->right != NULL) q.push(p->right);
        levelNodes--;
      }
      cout << endl;
    }
  }

Input :

Balanced tree created from:

 string a[] = {\"a\",\"b\",\"c\",\"d\",\"e\",\"f\",\"g\",\"h\",\"i\",\"j\",\"k\",\"l\",\"m\",\"n\"};

Output:

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

Algorithm:

  1. Create a ArrayList of Linked List Nodes.
  2. Do the level order traversal using queue(Breadth First Search).
  3. For getting all the nodes at each level, before you take out a node from queue, store the size of the queue in a variable, say you call it as levelNodes.
  4. Now while levelNodes > 0, take out the nodes and print it and add their children into the queue.
  5. After this while loop put a line break.


回答19:

A Scala solution, adapted from Vasya Novikov\'s answer and specialized for binary trees:

/** 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)
  }
}


回答20:

See also these answers.

In particular it wasn\'t too difficult to use abego TreeLayout to produce results shown below with the default settings.

If you try that tool, note this caveat: It prints children in the order they were added. For a BST where left vs right matters I found this library to be inappropriate without modification.

Also, the method to add children simply takes a parent and child node as parameters. (So to process a bunch of nodes, you must take the first one separately to create a root.)

I ended up using this solution above, modifying it to take in the type <Node> so as to have access to Node\'s left and right (children).

\"tree



回答21:

Here is another way to visualize your tree: save the nodes as an xml file and then let your browser show you the hierarchy:

class treeNode{
    int key;
    treeNode left;
    treeNode right;

    public treeNode(int key){
        this.key = key;
        left = right = null;
    }

    public void printNode(StringBuilder output, String dir){
        output.append(\"<node key=\'\" + key + \"\' dir=\'\" + dir + \"\'>\");
        if(left != null)
            left.printNode(output, \"l\");
        if(right != null)
            right.printNode(output, \"r\");
        output.append(\"</node>\");
    }
}

class tree{
    private treeNode treeRoot;

    public tree(int key){
        treeRoot = new treeNode(key);
    }

    public void insert(int key){
        insert(treeRoot, key);
    }

    private treeNode insert(treeNode root, int key){
        if(root == null){
            treeNode child = new treeNode(key);
            return child;
        }

        if(key < root.key)
            root.left = insert(root.left, key);
        else if(key > root.key)
            root.right = insert(root.right, key);

        return root;
    }

    public void saveTreeAsXml(){
        StringBuilder strOutput = new StringBuilder();
        strOutput.append(\"<?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?>\");
        treeRoot.printNode(strOutput, \"root\");
        try {
            PrintWriter writer = new PrintWriter(\"C:/tree.xml\", \"UTF-8\");
            writer.write(strOutput.toString());
            writer.close();
        }
        catch (FileNotFoundException e){

        }
        catch(UnsupportedEncodingException e){

        }
    }
}

Here is code to test it:

    tree t = new tree(1);
    t.insert(10);
    t.insert(5);
    t.insert(4);
    t.insert(20);
    t.insert(40);
    t.insert(30);
    t.insert(80);
    t.insert(60);
    t.insert(50);

    t.saveTreeAsXml();

And the output looks like this:

\"enter



回答22:

Based on VasyaNovikov answer. Improved with some Java magic: Generics and Functional interface.

/**
 * 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);
    }
}

Example initial call:

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

Will output something like

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


标签： java printing binary-tree
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~