Comment imprimer un diagramme d'arbre binaire?
21 réponses
j'ai créé une simple imprimante binaire. Vous pouvez l'utiliser et la modifier comme vous voulez, mais il n'est pas optimisé de toute façon. Je pense que beaucoup de choses peuvent être améliorées ici ;)
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;
}
}
sortie 1:
2
/ \
/ \
/ \
/ \
7 5
/ \ / \
/ \ / \
2 6 3 6
/ \ / \ / \ / \
5 8 4 5 8 4 5 8
sortie 2:
2
/ \
/ \
/ \
/ \
7 5
/ \ \
/ \ \
2 6 9
/ \ /
5 8 4
imprimer un [grand] arbre par des lignes.
exemple de sortie:
└── 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. M. Désolé, cette réponse ne se concentre pas vraiment sur les arbres "binaires". Il est juste googlé lorsque vous demandez un peu pour l'impression d'un arbre. Solution s'inspire de la commande" tree " de linux.
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 ? " | " : " "));
}
}
}
affichera:
/----- 20
| \----- 15
/----- 14
| \----- 13
/----- 12
| | /----- 11
| \----- 10
| \----- 9
8
| /----- 7
| /----- 6
| | \----- 5
\----- 4
| /----- 3
\----- 2
\----- 1
pour l'entrée
8 Quatre Douze Deux Six Dix Quatorze Un Trois Cinq Sept Neuf Onze Treize Vingt 15
c'est une variante de la réponse de @anurag - il m'ennuyait de voir le |S supplémentaire
j'ai fait un algorithme amélioré pour cela, qui gère bien les noeuds avec des tailles différentes. Il imprime de haut en bas en utilisant des lignes.
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;
}
}
}
pour utiliser ceci pour votre arbre, laissez votre Node classe implémenter PrintableNode .
exemple de sortie:
2952:0
┌───────────────────────┴───────────────────────┐
1249:-1 5866:0
┌───────────┴───────────┐ ┌───────────┴───────────┐
491:-1 1572:0 4786:1 6190:0
┌─────┘ └─────┐ ┌─────┴─────┐
339:0 5717:0 6061:0 6271:0
adapté de Vasya Novikov 's réponse pour le rendre plus binaire , et utiliser un StringBuilder pour l'efficacité (concaténer String objets ensemble en Java est généralement inefficace).
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();
}
sortie:
│ ┌── 7
│ ┌── 6
│ │ └── 5
└── 4
│ ┌── 3
└── 2
└── 1
└── 0
michal.kreuzman agréable je dois dire. Je me sentais paresseux pour faire un programme par moi-même et la recherche de code sur le net quand j'ai trouvé cela il m'a vraiment aidé. Mais j'ai peur de voir qu'il ne fonctionne que pour un seul chiffre, comme si vous allez utiliser plus d'un chiffre, puisque vous utilisez des espaces et pas les onglets de la structure va obtenir égaré et le programme va perdre son utilisation. Quant à mes derniers codes, j'ai eu besoin de quelques entrées plus importantes (au moins plus de 10) cela n'a pas fonctionné pour moi, et après avoir cherché beaucoup sur le net quand je n'ai rien trouvé, j'ai fait un programme moi-même. Il a quelques bugs maintenant, à nouveau en ce moment je me sens paresseux pour les corriger mais il imprime le très magnifiquement et les noeuds peuvent prendre n'importe quelle grande valeur.
l'arbre ne va pas être comme la question mentionne, mais il est de 270 degrés tournés :)
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);
}
placez cette fonction avec votre propre TreeNode spécifié et gardez le niveau initialy 0.
et d'en profiter. Voici quelques exemples de résultats.
| | |-------11
| |-------10
| | |-------9
|-------8
| | |-------7
| |-------6
| | |-------5
4
| |-------3
|-------2
| |-------1
| | | |-------10
| | |-------9
| |-------8
| | |-------7
|-------6
| |-------5
4
| |-------3
|-------2
| |-------1
Seul problème, c'est le prolongement des branches, je vais essayer de résoudre le problème dès que possible, mais en attendant vous pouvez l'utiliser aussi.
votre arbre aura besoin de deux fois la distance pour chaque couche:
a
/ \
/ \
/ \
/ \
b c
/ \ / \
/ \ / \
d e f g
/ \ / \ / \ / \
h i j k l m n o
, Vous pouvez enregistrer votre arbre dans un tableau de tableaux, un tableau pour chaque profondeur:
[[a],[b,c],[d,e,f,g],[h,i,j,k,l,m,n,o]]
Si l'arbre n'est pas complet, vous devez inclure des valeurs vides dans ce tableau:
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]]
alors vous pouvez itérer sur le tableau pour imprimer votre arbre, en imprimant des espaces avant le premier élément et entre les éléments en fonction de la profondeur et impression des lignes selon que les éléments correspondants dans le tableau pour la couche suivante sont remplis ou non. Si vos valeurs peuvent avoir plus d'un caractère de long, vous devez trouver la valeur la plus longue tout en créant la représentation du tableau et multiplier toutes les largeurs et le nombre de lignes en conséquence.
J'ai trouvé la réponse de VasyaNovikov très utile pour imprimer un grand arbre général, et l'ai modifié pour un arbre binaire
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);
}
}
}
sortie de L'échantillon:
\-- 7
|-- 3
| |-- 1
| | \-- 2
| \-- 5
| |-- 4
| \-- 6
\-- 11
|-- 9
| |-- 8
| \-- 10
\-- 13
|-- 12
\-- 14
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
Une solution Scala de la langue, analogue à ce j'ai écrit en 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
}
}
exemple de sortie:
vasya
├── frosya
│ ├── petya
│ │ └── masha
│ └── kolya
└── frosya2
par rapport à la solution java, il n'a pas l'indentation de base non nécessaire et les contaténates String -s un peu mieux ( StringBuilder sous le capot). Il peut encore causer une exception de débordement des piles pour un arbre profondément imbriqué. Place à l'amélioration.;- )
c'est une solution très simple pour imprimer un arbre. Ce n'est pas si joli, mais c'est vraiment 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);
}
sortie de L'échantillon:
106
105
104
103
102
101
100
je sais que vous avez tous une excellente solution; je veux juste partager la mienne - peut-être que ce n'est pas la meilleure façon, mais il est parfait pour moi-même!
Avec python et pip , il est vraiment très simple! BOOM!
Sur Mac ou Ubuntu (le mien est mac)
- ouvrir un terminal
-
$ pip install drawtree -
$python, entrez dans la console python; vous pouvez le faire d'une autre manière -
from drawtree import draw_level_order -
draw_level_order('{2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}')
fait!
2
/ \
/ \
/ \
1 3
/ \ / \
0 7 9 1
/ / \ / \
2 1 0 8 8
/
7
le suivi de la Source:
avant de voir ce post, je suis allé google "arbre binaire texte de plaine"
et j'ai trouvé ce https://www.reddit.com/r/learnpython/comments/3naiq8/draw_binary_tree_in_plain_text / , dirigez-moi vers ce https://github.com/msbanik/drawtree
j'avais besoin d'imprimer un arbre binaire dans un de mes projets, pour cela j'ai préparé une classe java TreePrinter , l'un des exemples de sortie est:
[+]
/ \
/ \
/ \
/ \
/ \
[*] \
/ \ [-]
[speed] [2] / \
[45] [12]
voici le code pour la classe TreePrinter avec la classe TextNode . Pour imprimer n'importe quel arbre, vous pouvez simplement créer un arbre équivalent avec la classe 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;
}
}
enfin voici une classe d'essai pour l'impression d'un échantillon donné:
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));
}
}
vous pouvez utiliser une applet pour visualiser ce très facilement. Vous devez imprimer les articles suivants.
-
imprimer les noeuds en cercles avec un certain rayon visible
-
obtenez les coordonnées de chaque noeud.
-
la coordonnée x peut être visualisée comme le nombre de noeuds visités avant que le noeud soit visité dans son ordre transversal.
-
La coordonnée y peut être visualisée comme la profondeur du nœud particulier.
-
-
imprimer les lignes entre le parent et l'enfant
-
cela peut être fait en maintenant les coordonnées x et y des noeuds et des parents de chaque noeud dans des listes séparées.
-
pour chaque noeud sauf root joindre chaque noeud avec son parent en prenant les coordonnées x et y de l'enfant et le parent.
-
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(""151900920"", 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
ne fonctionne que pour les entiers de 1 à 2 chiffres (j'ai été paresseux de le rendre Générique)
Imprimer dans la Console:
500
700 300
200 400
code Simple:
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;
}
}
voici une imprimante à arbre très polyvalente. Pas le meilleur, mais il gère un grand nombre de cas. N'hésitez pas à ajouter des barres obliques si vous pouvez comprendre cela.
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();
}
}
classe de Nodéposition
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);
}
}
et, enfin, 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<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;
}
}
entrée:
arbre équilibré créé à partir de:
string a[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n"};
sortie:
g
c k
a e i m
b d f h j l n
- créer un ArrayList de noeuds de liste liés.
- Faire au niveau de la commande traversée à l'aide de la file d'attente(première recherche de la largeur).
- pour obtenir tous les noeuds à chaque niveau, avant de sortir un noeud de la file d'attente, stockez la taille de la file d'attente dans une variable, dites que vous l'appelez comme levelNodes.
- maintenant alors que les codes > 0, sortez les noeuds et imprimez - le et ajoutez leurs enfants dans la file d'attente.
- après cela pendant que boucle mettre une rupture de ligne.
une solution Scala, adaptée de la réponse de Vassia Novikov et spécialisée pour les arbres binaires:
/** 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)
}
}
Voir aussi ces réponses .
en particulier, il n'était pas trop difficile d'utiliser abego TreeLayout pour produire les résultats affichés ci-dessous avec les paramètres par défaut.
si vous essayez cet outil, notez cette mise en garde: il imprime les enfants dans l'ordre où ils ont été ajoutés. Pour un TSB où les questions de gauche par rapport à droite j'ai trouvé cette bibliothèque être inappropriée sans modification.
aussi, la méthode pour ajouter des enfants prend simplement un noeud parent et child comme paramètres. (Donc pour traiter un tas de noeuds, vous devez prendre le premier séparément pour créer une racine.)
j'ai fini par utiliser cette solution ci-dessus, en la modifiant pour prendre le type <Node> afin d'avoir accès à Node gauche et droite (enfants).
Voici une autre façon de visualiser votre arborescence: sauvegardez les noeuds sous forme de fichier xml, puis laissez votre navigateur vous afficher la hiérarchie:
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){
}
}
}
voici le code pour le tester:
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();
Et la sortie ressemble à ceci:
