Как распечатать диаграмму двоичного дерева? - PullRequest
Новая
       118

Как распечатать диаграмму двоичного дерева?

146 голосов
/ 11 февраля 2011

Как я могу напечатать двоичное дерево на Java, чтобы вывод был таким: 

   4 
  / \ 
 2   5

Мой узел: 

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

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

Ответы [ 24 ]

257 голосов
/ 21 января 2012

Печать [большого] дерева по строкам.

пример вывода: 

└── 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 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. Извините, этот ответ не сфокусирован на двоичных деревьях. Он просто гуглится, когда запрашивает что-то для печати дерева. Решение вдохновлено командой "tree" в linux.

215 голосов
/ 11 февраля 2011

Я создал простой принтер бинарного дерева.Вы можете использовать и изменять его, как хотите, но он все равно не оптимизирован.Я думаю, что здесь многое можно улучшить;) 

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
41 голосов
/ 17 апреля 2015

Я сделал улучшенный алгоритм для этого, который прекрасно обрабатывает узлы с разным размером.Он печатает сверху вниз, используя строки. 

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
38 голосов
/ 21 октября 2013 
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

thisвариант от ответа @ anurag - мне было жаль видеть лишние | s

30 голосов
/ 26 ноября 2014

Адаптировано из Вася Новиков ответ , чтобы сделать его более двоичным , и использование 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
15 голосов
/ 07 июля 2013

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

Единственная проблема - с расширяющимися ветвями, я постараюсь решить проблему как можно скорее, но до тех пор вы тоже можете ее использовать.

13 голосов
/ 11 февраля 2011

Вашему дереву потребуется удвоенное расстояние для каждого слоя: 

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

Затем вы можете выполнить итерацию по массиву, чтобы напечатать ваше дерево, печатая пробелы перед первым элементом и между элементами в зависимости отглубина и печать линий в зависимости от того, заполнены ли соответствующие элементы в массиве для следующего слоя или нет.Если ваши значения могут быть длиной более одного символа, вам нужно найти самое длинное значение при создании представления массива и соответственно умножить всю ширину и количество строк.

9 голосов
/ 25 февраля 2017

Я нашел ответ ВасяНовикова очень полезным для печати большого общего дерева и изменил его для двоичного дерева

Код: 

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
5 голосов
/ 11 апреля 2017

Решение на языке 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

По сравнению с Java-решением, оно не имеет ненужного базового отступа и загрязняет String - немного лучше (StringBuilder под капотом).Это все еще может вызвать исключение StackOverflow для глубоко вложенного дерева.Комната для улучшения.; -)

4 голосов
/ 22 июня 2016

Я знаю, что у вас всех есть отличное решение;Я просто хочу поделиться своим - возможно, это не лучший способ, но он идеально подходит для меня!

С python и pip, это действительно довольно просто!BOOM!

На Mac или Ubuntu (у меня mac)

  1. открыть терминал
  2. $ pip install drawtree
  3. $python, войти в консоль Python;Вы можете сделать это другим способом
  4. from drawtree import draw_level_order
  5. draw_level_order('{2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}')

СДЕЛАНО! 

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

Отслеживание источника:

Прежде чем я увидел этот пост, я зашел в Google "бинарное дерево простого текста"

И я нашел это https://www.reddit.com/r/learnpython/comments/3naiq8/draw_binary_tree_in_plain_text/,, направьте меня к этому https://github.com/msbanik/drawtree

Страница:
...