Come stampare il diagramma ad albero binario?

Come posso stampare un albero binario in Java in modo che l’output sia simile a:

4 / \ 2 5 

Il mio nodo:

 public class Node { Node left, right; A data; public Node(A data){ this.data = data; } } 

Ho creato una semplice stampante ad albero binario. Puoi usarlo e modificarlo come vuoi, ma non è comunque ottimizzato. Penso che molte cose possano essere migliorate qui;)

 import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BTreePrinterTest { private static Node test1() { Node root = new Node(2); Node n11 = new Node(7); Node n12 = new Node(5); Node n21 = new Node(2); Node n22 = new Node(6); Node n23 = new Node(3); Node n24 = new Node(6); Node n31 = new Node(5); Node n32 = new Node(8); Node n33 = new Node(4); Node n34 = new Node(5); Node n35 = new Node(8); Node n36 = new Node(4); Node n37 = new Node(5); Node n38 = new Node(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 test2() { Node root = new Node(2); Node n11 = new Node(7); Node n12 = new Node(5); Node n21 = new Node(2); Node n22 = new Node(6); Node n23 = new Node(9); Node n31 = new Node(5); Node n32 = new Node(8); Node n33 = new Node(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> { Node left, right; T data; public Node(T data) { this.data = data; } } class BTreePrinter { public static > void printNode(Node root) { int maxLevel = BTreePrinter.maxLevel(root); printNodeInternal(Collections.singletonList(root), 1, maxLevel); } private static > void printNodeInternal(List> 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> newNodes = new ArrayList>(); for (Node 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 > int maxLevel(Node node) { if (node == null) return 0; return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1; } private static  boolean isAllElementsNull(List list) { for (Object object : list) { if (object != null) return false; } return true; } } 

Uscita 1:

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

Uscita 2:

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

Stampa un [grande] albero per linee.

esempio di output:

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

codice:

 public class TreeNode { final String name; final List children; public TreeNode(String name, List 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); } } } 

PS Siamo spiacenti, questa risposta non si concentra esattamente sugli alberi “binari”. Diventa semplicemente google quando richiede un po ‘di stampare un albero. La soluzione è ispirata al comando “tree” in linux.

 public static class Node> { T value; Node left, right; public void insertToTree(T v) { if (value == null) { value = v; return; } if (v.compareTo(value) < 0) { if (left == null) { left = new Node(); } left.insertToTree(v); } else { if (right == null) { right = new Node(); } 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(""); } 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 ? " | " : " ")); } } } 

stamperà:

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

per l’input

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

questa è una variante della risposta di @ anurag: mi dava fastidio vedere gli extra | s

Ho realizzato un algoritmo migliorato per questo, che gestisce bene nodes con dimensioni diverse. Stampa dall’alto verso il basso usando le linee.

 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> lines = new ArrayList>(); List level = new ArrayList(); List next = new ArrayList(); level.add(root); int nn = 1; int widest = 0; while (nn != 0) { List line = new ArrayList(); 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 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 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; } } } 

Per usare questo per la tua Struttura, consenti alla class Node implementare PrintableNode .

Esempio di output:

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

Adattato dalla risposta di Vasya Novikov per renderlo più binario , e usare uno StringBuilder per efficienza (concatenare insieme gli oggetti String in Java è generalmente inefficiente).

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

Produzione:

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

michal.kreuzman bello, dovrò dire. Mi sentivo pigro per fare un programma da solo e alla ricerca di codice su rete quando ho trovato questo mi ha davvero aiutato. Ma ho paura di vedere che funziona solo per le singole cifre come se si usasse più di una cifra, dal momento che si utilizzano spazi e non tabulazioni, la struttura si troverà male e il programma perderà il suo uso. Per quanto riguarda i miei codici successivi avevo bisogno di alcuni input più grandi (almeno più di 10) questo non ha funzionato per me, e dopo aver cercato molto in rete quando non ho trovato nulla, ho fatto un programma io stesso. Ha alcuni bug ora, di nuovo in questo momento mi sento pigro per correggerli ma stampa molto bene ei nodes possono assumere qualsiasi valore.

L’albero non sarà come la domanda menziona ma è ruotato di 270 gradi 🙂

 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 

Posiziona questa funzione con il tuo TreeNode specificato e mantieni il livello iniziale 0.

e goditelo. Ecco alcuni degli output di esempio.

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

L'unico problema è con i rami di estensione che cercherò di risolvere il problema il prima ansible ma fino ad allora puoi usarlo anche tu.

Il tuo albero avrà bisogno di un doppio della distanza per ogni strato:

  un
       / \
      / \
     / \
    / \
    avanti Cristo
   / \ / \
  / \ / \
  DEFG
 / \ / \ / \ / \
 hijklmno 

Puoi salvare il tuo albero in una serie di matrici, una matrice per ogni profondità:

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

Se il tuo albero non è pieno, devi includere valori vuoti in quell’array:

  un
       / \
      / \
     / \
    / \
    avanti Cristo
   / \ / \
  / \ / \
  DEFG
 / \ \ / \ \
 hiklmo
 [[a], [b, c], [d, e, f, g], [h, i,, k, l, m,, o]] 

Quindi puoi scorrere l’array per stampare il tuo albero, stampare spazi prima del primo elemento e tra gli elementi a seconda della profondità e stampare le linee a seconda se gli elementi corrispondenti nella matrice per il livello successivo sono riempiti o meno. Se i tuoi valori possono essere più lunghi di un carattere, devi trovare il valore più lungo mentre crei la rappresentazione dell’array e moltiplica tutte le larghezze e il numero di linee di conseguenza.

Ho trovato la risposta di VasyaNovikov molto utile per stampare un grande albero generale e modificato per un albero binario

Codice:

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

Uscita di esempio:

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

Una soluzione in linguaggio Scala , analogo a quanto ho scritto 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 } } 

Esempio di uscita:

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

Paragonato alla soluzione java, non ha il rientro di base non necessario e si lega a String -s un po ‘meglio ( StringBuilder sotto il cofano). Può ancora causare un’eccezione StackOverflow per un albero profondamente annidato. Margini di miglioramento.;-)

 public void printPreety() { List list = new ArrayList(); 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 levelNodes, int level) { List nodes = new ArrayList(); //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 

Questa è una soluzione molto semplice per stampare un albero. Non è carino, ma è davvero semplice:

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

Uscita di esempio:

       106
             105
 104
             103
                   102
                         101
       100

Avevo bisogno di stampare un albero binario in uno dei miei progetti, per questo ho preparato un TreePrinter class java, uno degli output di esempio è:

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

Ecco il codice per la class TreePrinter insieme alla class TextNode . Per stampare qualsiasi albero puoi semplicemente creare un albero equivalente con la class 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 - (nx + 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) nx = 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; } }
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 - (nx + 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) nx = 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; } } 

Finalmente ecco una class di test per stampare un campione dato:

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

Puoi usare un’applet per visualizzarla molto facilmente. È necessario stampare i seguenti elementi.

  1. Stampa i nodes come cerchi con un raggio visibile

    • Ottieni le coordinate per ciascun nodo.

    • La coordinata x può essere visualizzata come il numero di nodes visitati prima che il nodo venga visitato nel suo attraversamento inorder.

    • La coordinata y può essere visualizzata come la profondità del nodo particolare.


  1. Stampa le linee tra genitore e figli

    • Questo può essere fatto mantenendo le coordinate xey dei nodes e i genitori di ciascun nodo in liste separate.

    • Per ogni nodo tranne root, unisci ciascun nodo con il suo genitore prendendo le coordinate xey sia del bambino che del genitore.

 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 

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

funziona solo con numeri interi da 1 a 2 cifre (ero pigro per renderlo generico)

distorta pieno

Stampa in Console:

  500 700 300 200 400 

Codice semplice:

 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 rootsQueue = new LinkedList(); Queue levelQueue = new LinkedList(); 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; } } 

Ecco una stampante ad albero molto versatile. Non è il più bello, ma gestisce un sacco di casi. Sentiti libero di aggiungere barre se riesci a capirlo. inserisci la descrizione dell'immagine qui

 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> 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 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 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 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 pos_arr : this.nodesByRow){ String[] chars = this.getCharactersArray(pos_arr,max_chars); String line = ""; int empty_chars = 0; for (int i=0;i 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 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; } } 

Classe NodeInfo

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

C ++:

  struct node{ string key; struct node *left, *right; }; void printBFS(struct node *root){ std::queue 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"}; 

Produzione:

  gckaeimbdfhjln 

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.

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

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 so as to have access to Node ‘s left and right (children).

tree created with abego TreeLayout

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(""); if(left != null) left.printNode(output, "l"); if(right != null) right.printNode(output, "r"); output.append(""); } } 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(""); 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:

inserisci la descrizione dell'immagine qui