我如何在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;
}
}
当前回答
这是水平视图最简单的解决方案。我举了很多例子。很适合我的目的。更新自@ ntin -k的回答。
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
其他回答
迈克尔。克鲁兹曼,我不得不说,这人不错。这很有用。
然而,上面的方法只适用于个位数:如果您要使用多个数字,结构将会错位,因为您使用的是空格而不是制表符。
至于我后来的代码,我需要更多的数字,所以我自己编写了一个程序。
它现在有一些bug,现在我感觉很懒去纠正它们,但它打印得非常漂亮,节点可以接受更大数量的数字。
这棵树不会像问题提到的那样,但它旋转了270度:)
public static void printBinaryTree(TreeNode root, int level){
if(root==null)
return;
printBinaryTree(root.right, level+1);
if(level!=0){
for(int i=0;i<level-1;i++)
System.out.print("|\t");
System.out.println("|-------"+root.val);
}
else
System.out.println(root.val);
printBinaryTree(root.left, level+1);
}
将此函数与您自己指定的TreeNode一起放置,并保持初始级别为0,并享受!
以下是一些输出示例:
| | |-------11
| |-------10
| | |-------9
|-------8
| | |-------7
| |-------6
| | |-------5
4
| |-------3
|-------2
| |-------1
| | | |-------10
| | |-------9
| |-------8
| | |-------7
|-------6
| |-------5
4
| |-------3
|-------2
| |-------1
唯一的问题是延伸的分支;我会尽快解决这个问题,但在此之前你也可以使用它。
public static class Node<T extends Comparable<T>> {
T value;
Node<T> left, right;
public void insertToTree(T v) {
if (value == null) {
value = v;
return;
}
if (v.compareTo(value) < 0) {
if (left == null) {
left = new Node<T>();
}
left.insertToTree(v);
} else {
if (right == null) {
right = new Node<T>();
}
right.insertToTree(v);
}
}
public void printTree(OutputStreamWriter out) throws IOException {
if (right != null) {
right.printTree(out, true, "");
}
printNodeValue(out);
if (left != null) {
left.printTree(out, false, "");
}
}
private void printNodeValue(OutputStreamWriter out) throws IOException {
if (value == null) {
out.write("<null>");
} else {
out.write(value.toString());
}
out.write('\n');
}
// use string and not stringbuffer on purpose as we need to change the indent at each recursion
private void printTree(OutputStreamWriter out, boolean isRight, String indent) throws IOException {
if (right != null) {
right.printTree(out, true, indent + (isRight ? " " : " | "));
}
out.write(indent);
if (isRight) {
out.write(" /");
} else {
out.write(" \\");
}
out.write("----- ");
printNodeValue(out);
if (left != null) {
left.printTree(out, false, indent + (isRight ? " | " : " "));
}
}
}
将打印:
/----- 20
| \----- 15
/----- 14
| \----- 13
/----- 12
| | /----- 11
| \----- 10
| \----- 9
8
| /----- 7
| /----- 6
| | \----- 5
\----- 4
| /----- 3
\----- 2
\----- 1
对于输入
8 4 12 2 6 10 14 1 3 5 7 9 11 13 20 15
这是@anurag回答的一个变体——看到额外的|让我很烦
这是一个非常多功能的树打印机。不是最好看的,但能处理很多案子。如果你能弄清楚,可以随意添加斜杠。
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类
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类
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);
}
}
最后是节点接口
package com.tomac120.NodePrinter;
/**
* Created by elijah on 6/28/16.
*/
public interface PrintableNode {
PrintableNodeInfo _getPrintableNodeInfo();
PrintableNode _getLeftChild();
PrintableNode _getRightChild();
}
根据VasyaNovikov的回答。改进了一些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
一个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)
}
}