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

Question

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

   4 
  / \ 
 2   5 

Мой узел:

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

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

Answer 1

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   

Answer 2

Это очень простое решение для распечатки дерева.Это не так красиво, но это действительно просто:

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

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

      106
            105
104
            103
                  102
                        101
      100

Answer 3

Это было самое простое решение для горизонтального обзора.Пробовал с кучей примеров.Хорошо работает для моей цели.Обновлено с @ nitin-k's answer.

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

Звоните:

bst.print("", bst.root, false);

Решение:

                         |-- 80
                    |-- 70
               |-- 60
          |-- 50
     |-- 40
|-- 30
     |-- 20
          |-- 10

Answer 4

Вы можете использовать апплет для визуализации этого очень легко.Вам необходимо напечатать следующие элементы.

1. Печать узлов в виде кругов с некоторым видимым радиусом

   • Получить координаты для каждого узла.

   • Координата x может быть визуализирована как число узлов, посещенных до посещения узла при его обходе по порядку.

   • Координата y можетвизуализируется как глубина конкретного узла.

---

Вывести строки между родителем и потомком

• Это можно сделать, сохранив координаты x и y узлов и родителей каждого узла в отдельных списках.

• Для каждого узла, кроме корневого, объедините каждый узел с его родителем, взяв координаты x и y дочернего и родительского элементов.

Answer 5

Мне нужно было распечатать двоичное дерево в одном из моих проектов, для этого я подготовил 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));
    }
}

Answer 6

Я написал двоичное дерево принтера на Java.

Код: на GitHub здесь .

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

1. Он эффективно использует пространство, поскольку большое поддерево максимально расширяется под меньшее.
2. Существует параметр для установкиминимальное горизонтальное пространство между метками узла.
3. Метки узла - это строки произвольной длины.
4. В дополнение к способу печати одного дерева, существует метод печати списка деревьев по горизонтали черезстраница (с параметром для ширины страницы), используя столько строк, сколько необходимо.
5. Существует возможность печати деревьев с диагональными ветвями (используя символы косой черты и обратной косой черты) или с горизонтальными ветвями (используя символы рисования ascii box),Последний более компактен и делает уровни дерева более наглядными.
6. Работает.

Некоторые демонстрационные / тестовые программы включены.

Пример случайным образомСгенерированное двоичное дерево, как напечатано программой, следует.Это иллюстрирует эффективное использование пространства с большим правым поддеревом, простирающимся под маленьким левым поддеревом:

             seven                                        
              / \                                         
             /   \                                        
            /     \                                       
           /       \                                      
          /         \                                     
         /           \                                    
       five        thirteen                               
       / \           / \                                  
      /   \         /   \                                 
     /     \       /     \                                
  three    six    /       \                               
   / \           /         \                              
  /   \         /           \                             
one   four     /             \                            
  \           /               \                           
  two        /                 \                          
           nine            twenty four                    
           / \                 / \                        
          /   \               /   \                       
         /     \             /     \                      
      eight   twelve        /       \                     
               /           /         \                    
             ten          /           \                   
               \         /             \                  
              eleven    /               \                 
                       /                 \                
                      /                   \               
                     /                     \              
                 eighteen              twenty seven       
                   / \                     / \            
                  /   \                   /   \           
                 /     \                 /     \          
                /       \               /       \         
               /         \             /         \        
              /           \           /           \       
             /             \    twenty five   twenty eight
            /               \         \             \     
           /                 \     twenty six      thirty 
       fourteen            nineteen                 /     
           \                   \              twenty nine 
         sixteen           twenty three                   
           / \                 /                          
          /   \           twenty two                      
         /     \             /                            
        /       \         twenty                          
       /         \           \                            
   fifteen    seventeen   twenty one                      

Пример печати всех пяти двоичных деревьев узла (с метками в порядке) по странице:

one           one         one          one        one       one         one     
  \             \           \            \          \         \           \     
  two           two         two          two        two      three       three  
    \             \           \            \          \       / \         / \   
   three         three        four         five       five  two four    two five
      \             \         / \          /          /           \         /   
      four          five     /   \      three       four          five    four  
        \           /     three  five      \        /                           
        five      four                     four  three                          



one          one        one        one       one       one         one        two        
  \            \          \          \         \         \           \        / \        
  four         four       five       five      five      five        five    /   \       
  / \          / \        /          /         /         /           /     one  three    
two five      /   \     two        two      three      four        four            \     
  \        three  five    \          \       / \       /           /               four  
 three      /            three       four  two four  two        three                \   
          two               \        /                 \         /                   five
                            four  three               three    two                       



   two          two          two        two      three         three         three    
   / \          / \          / \        / \       / \           / \           / \     
  /   \       one four     one five   one five  one four       /   \        two four  
one  three        / \          /          /       \   \       /     \       /     \   
        \        /   \      three       four      two five  one     five  one     five
        five  three  five      \        /                     \     /                 
        /                      four  three                    two four                
      four                                                                            



   three      four      four         four         four            four       five    
    / \       / \       / \          / \          / \             / \        /       
  two five  one five  one five     two five      /   \           /   \     one       
  /   /       \         \          / \        three  five     three  five    \       
one four      two      three      /   \        /               /             two     
                \       /       one  three   one             two               \     
               three  two                      \             /                three  
                                               two         one                   \   
                                                                                 four



  five      five      five      five       five         five      five        five
  /         /         /         /          /            /         /           /   
one       one       one       one        two          two      three       three  
  \         \         \         \        / \          / \       / \         / \   
  two      three      four      four    /   \       one four  one four    two four
    \       / \       /         /     one  three        /       \         /       
    four  two four  two      three            \      three      two     one       
    /                 \       /               four                                
 three               three  two                                                   



    five      five         five        five          five
    /         /            /           /             /   
  four      four         four        four          four  
  /         /            /           /             /     
one       one          two        three         three    
  \         \          / \         /             /       
  two      three      /   \      one           two       
    \       /       one  three     \           /         
   three  two                      two       one 

Ниже приведен пример того же дерева, напечатанного 4 разными способами, с горизонтальным интервалом 1 и 3 и с диагональными и горизонтальными ветвями.

                   27        
             ┌─────┴─────┐   
             13          29  
      ┌──────┴──────┐  ┌─┴─┐ 
      8             23 28  30
   ┌──┴──┐       ┌──┴──┐     
   4     11      21    26    
 ┌─┴─┐  ┌┴┐    ┌─┴─┐  ┌┘     
 2   5  9 12   18  22 24     
┌┴┐  └┐ └┐   ┌─┴─┐    └┐     
1 3   6  10  17  19    25    
      └┐    ┌┘   └┐          
       7    15    20         
          ┌─┴─┐              
          14  16             


                 27        
                / \        
               /   \       
              13    29     
             / \   / \     
            /   \ 28  30   
           /     \         
          /       \        
         /         \       
        /           \      
       8             23    
      / \           / \    
     /   \         /   \   
    4     11      /     \  
   / \   / \     21      26
  2   5 9   12  / \     /  
 / \   \ \     18  22  24  
1   3   6 10  / \       \  
         \   17  19      25
          7 /     \        
           15      20      
          / \              
         14  16            


                             27            
                    ┌────────┴────────┐    
                    13                29   
          ┌─────────┴─────────┐    ┌──┴──┐ 
          8                   23   28    30
     ┌────┴────┐         ┌────┴────┐       
     4         11        21        26      
  ┌──┴──┐    ┌─┴─┐    ┌──┴──┐     ┌┘       
  2     5    9   12   18    22    24       
┌─┴─┐   └┐   └┐    ┌──┴──┐        └┐       
1   3    6    10   17    19        25      
         └┐       ┌┘     └┐                
          7       15      20               
               ┌──┴──┐                     
               14    16                    


                      27         
                     / \         
                    /   \        
                   /     \       
                  /       \      
                 13        29    
                / \       / \    
               /   \     /   \   
              /     \   28    30 
             /       \           
            /         \          
           /           \         
          /             \        
         /               \       
        8                 23     
       / \               / \     
      /   \             /   \    
     /     \           /     \   
    4       11        /       \  
   / \     / \       21        26
  2   5   9   12    / \       /  
 / \   \   \       /   \     24  
1   3   6   10    18    22    \  
         \       / \           25
          7     /   \            
               17    19          
              /       \          
             15        20        
            / \                  
           /   \                 
          14    16               

Answer 7

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 (мне было лениво делать это обобщенно)

Answer 8

На основании ответа ВасяНовикова.Улучшено с помощью магии 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

Answer 9

Вот еще один способ визуализации вашего дерева: сохраните узлы в виде XML-файла, а затем разрешите браузеру показать вам иерархию:

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){

        }
    }
}

Вот код для его проверки:

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

И вывод выглядит так:

Answer 10

См. Также эти ответы .

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

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

Кроме того, метод добавления потомков просто принимает в качестве параметров узлы parent и child.(Таким образом, чтобы обработать группу узлов, вы должны взять первый узел отдельно для создания корня.)

В итоге я использовал это решение выше, изменив его так, чтобы он принимал тип <Node> чтобы иметь доступ к Node слева и справа (детям).