我如何在Java中打印一个二叉树,这样输出就像:
4
/ \
2 5
我的节点:
public class Node<A extends Comparable> {
Node<A> left, right;
A data;
public Node(A data){
this.data = data;
}
}
我如何在Java中打印一个二叉树,这样输出就像:
4
/ \
2 5
我的节点:
public class Node<A extends Comparable> {
Node<A> left, right;
A data;
public Node(A data){
this.data = data;
}
}
当前回答
这是打印树的一个非常简单的解决方案。它不是那么漂亮,但它真的很简单:
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
其他回答
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位整数(我懒得让它通用)
你的树每一层需要两倍的距离:
a / \ / \ / \ / \ b c / \ / \ / \ / \ d e f g / \ / \ / \ / \ h i j k l m n o
你可以将你的树保存在一个数组的数组中,每个数组对应一个深度:
[[a],[b,c],[d,e,f,g],[h,i,j,k,l,m,n,o]]
如果你的树没有满,你需要在数组中包含空值:
a / \ / \ / \ / \ b c / \ / \ / \ / \ d e f g / \ \ / \ \ h i k l m o [[a],[b,c],[d,e,f,g],[h,i, ,k,l,m, ,o]]
然后你可以遍历数组来打印你的树,根据深度打印第一个元素之前和元素之间的空格,根据下一层数组中对应的元素是否被填充打印行。 如果您的值可以超过一个字符长,您需要在创建数组表示时找到最长的值,并相应地乘以所有宽度和行数。
我需要在我的一个项目中打印一个二叉树,为此我准备了一个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));
}
}
我已经创建了简单的二叉树打印机。您可以随心所欲地使用和修改它,但无论如何它都没有优化。我认为这里有很多东西可以改进;)
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BTreePrinterTest {
private static Node<Integer> test1() {
Node<Integer> root = new Node<Integer>(2);
Node<Integer> n11 = new Node<Integer>(7);
Node<Integer> n12 = new Node<Integer>(5);
Node<Integer> n21 = new Node<Integer>(2);
Node<Integer> n22 = new Node<Integer>(6);
Node<Integer> n23 = new Node<Integer>(3);
Node<Integer> n24 = new Node<Integer>(6);
Node<Integer> n31 = new Node<Integer>(5);
Node<Integer> n32 = new Node<Integer>(8);
Node<Integer> n33 = new Node<Integer>(4);
Node<Integer> n34 = new Node<Integer>(5);
Node<Integer> n35 = new Node<Integer>(8);
Node<Integer> n36 = new Node<Integer>(4);
Node<Integer> n37 = new Node<Integer>(5);
Node<Integer> n38 = new Node<Integer>(8);
root.left = n11;
root.right = n12;
n11.left = n21;
n11.right = n22;
n12.left = n23;
n12.right = n24;
n21.left = n31;
n21.right = n32;
n22.left = n33;
n22.right = n34;
n23.left = n35;
n23.right = n36;
n24.left = n37;
n24.right = n38;
return root;
}
private static Node<Integer> test2() {
Node<Integer> root = new Node<Integer>(2);
Node<Integer> n11 = new Node<Integer>(7);
Node<Integer> n12 = new Node<Integer>(5);
Node<Integer> n21 = new Node<Integer>(2);
Node<Integer> n22 = new Node<Integer>(6);
Node<Integer> n23 = new Node<Integer>(9);
Node<Integer> n31 = new Node<Integer>(5);
Node<Integer> n32 = new Node<Integer>(8);
Node<Integer> n33 = new Node<Integer>(4);
root.left = n11;
root.right = n12;
n11.left = n21;
n11.right = n22;
n12.right = n23;
n22.left = n31;
n22.right = n32;
n23.left = n33;
return root;
}
public static void main(String[] args) {
BTreePrinter.printNode(test1());
BTreePrinter.printNode(test2());
}
}
class Node<T extends Comparable<?>> {
Node<T> left, right;
T data;
public Node(T data) {
this.data = data;
}
}
class BTreePrinter {
public static <T extends Comparable<?>> void printNode(Node<T> root) {
int maxLevel = BTreePrinter.maxLevel(root);
printNodeInternal(Collections.singletonList(root), 1, maxLevel);
}
private static <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) {
if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
return;
int floor = maxLevel - level;
int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
int firstSpaces = (int) Math.pow(2, (floor)) - 1;
int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;
BTreePrinter.printWhitespaces(firstSpaces);
List<Node<T>> newNodes = new ArrayList<Node<T>>();
for (Node<T> node : nodes) {
if (node != null) {
System.out.print(node.data);
newNodes.add(node.left);
newNodes.add(node.right);
} else {
newNodes.add(null);
newNodes.add(null);
System.out.print(" ");
}
BTreePrinter.printWhitespaces(betweenSpaces);
}
System.out.println("");
for (int i = 1; i <= endgeLines; i++) {
for (int j = 0; j < nodes.size(); j++) {
BTreePrinter.printWhitespaces(firstSpaces - i);
if (nodes.get(j) == null) {
BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
continue;
}
if (nodes.get(j).left != null)
System.out.print("/");
else
BTreePrinter.printWhitespaces(1);
BTreePrinter.printWhitespaces(i + i - 1);
if (nodes.get(j).right != null)
System.out.print("\\");
else
BTreePrinter.printWhitespaces(1);
BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
}
System.out.println("");
}
printNodeInternal(newNodes, level + 1, maxLevel);
}
private static void printWhitespaces(int count) {
for (int i = 0; i < count; i++)
System.out.print(" ");
}
private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
if (node == null)
return 0;
return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
}
private static <T> boolean isAllElementsNull(List<T> list) {
for (Object object : list) {
if (object != null)
return false;
}
return true;
}
}
输出1:
2
/ \
/ \
/ \
/ \
7 5
/ \ / \
/ \ / \
2 6 3 6
/ \ / \ / \ / \
5 8 4 5 8 4 5 8
输出2:
2
/ \
/ \
/ \
/ \
7 5
/ \ \
/ \ \
2 6 9
/ \ /
5 8 4
一个Scala解决方案,改编自Vasya Novikov的答案,专门用于二叉树:
/** 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)
}
}