我如何在Java中打印一个二叉树，这样输出就像:
4
/ \
2 5
我的节点:
public class Node<A extends Comparable> {
Node<A> left, right;
A data;
public Node(A data){
this.data = data;
}
}
当前回答
根据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
其他回答
我为此做了一个改进的算法，可以很好地处理不同大小的节点。它使用行自上而下地打印。
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;
}
}
}
要在树中使用它，让Node类实现PrintableNode。
示例输出:
2952:0
┌───────────────────────┴───────────────────────┐
1249:-1 5866:0
┌───────────┴───────────┐ ┌───────────┴───────────┐
491:-1 1572:0 4786:1 6190:0
┌─────┘ └─────┐ ┌─────┴─────┐
339:0 5717:0 6061:0 6271:0
我需要在我的一个项目中打印一个二叉树，为此我准备了一个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));
}
}
试试这个:
public static void print(int[] minHeap, int minWidth) {
int size = minHeap.length;
int level = log2(size);
int maxLength = (int) Math.pow(2, level) * minWidth;
int currentLevel = -1 ;
int width = maxLength;
for (int i = 0; i < size; i++) {
if (log2(i + 1) > currentLevel) {
currentLevel++;
System.out.println();
width = maxLength / (int) Math.pow(2, currentLevel);
}
System.out.print(StringUtils.center(String.valueOf(minHeap[i]), width));
}
System.out.println();
}
private static int log2(int n) {
return (int) (Math.log(n) / Math.log(2));
}
这段代码片段的思想是用maxLength(即底线的长度)除以每一行的元素数量来得到块宽度。然后把元素放在每个块的中间。
参数minWidth表示底部行中块的长度。
用一张图片来说明想法并展示结果。
与垂直表示相比，水平表示有点复杂。垂直打印只是简单的RNL(右->节点->左或镜像的顺序)遍历，以便先打印右子树，然后打印左子树。
def printFullTree(root, delim=' ', idnt=[], left=None):
if root:
idnt.append(delim)
x, y = setDelims(left)
printFullTree(root.right, x, idnt, False)
indent2(root.val, idnt)
printFullTree(root.left, y, idnt, True)
idnt.pop()
def setDelims(left):
x = ' '; y='|'
return (y,x) if (left == True) else (x,y) if (left == False) else (x,x)
def indent2(x, idnt, width=6):
for delim in idnt:
print(delim + ' '*(width-1), end='')
print('|->', x)
output:
|-> 15
|-> 14
| |-> 13
|-> 12
| | |-> 11
| |-> 10
| |-> 9
|-> 8
| |-> 7
| |-> 6
| | |-> 4
|-> 3
| |-> 2
|-> 1
|-> 0
在水平表示中，显示由TreeMap的HashMap或HashMap<Integer, TreeMap<Integer, Object>> xy构建;其中HashMap包含节点的y轴/level_no作为Key, TreeMap作为value。Treemap内部保存同一级别的所有节点，按它们的x轴值排序，作为键，从最左端开始-ve，根=0，最右端=+ve。
如果使用自平衡树/Treap，则使用HashMap使算法在每个级别的O(1)查找中工作，并在O(logn)中使用TreeMap排序。
不过，在这样做的时候，不要忘记为空子存储占位符，例如' '/空格，这样树看起来就像预期的那样。
现在唯一剩下的就是计算水平节点的距离，这可以用一些数学计算来完成，
计算树的宽度和高度。 一旦完成，在显示节点时，根据计算的宽度，高度和倾斜信息(如果有的话)，以最佳距离呈现它们。
我已经创建了简单的二叉树打印机。您可以随心所欲地使用和修改它，但无论如何它都没有优化。我认为这里有很多东西可以改进;)
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
推荐文章
- 在流中使用Java 8 foreach循环移动到下一项
- 访问限制:'Application'类型不是API(必需库rt.jar的限制)
- 用Java计算两个日期之间的天数
- 如何配置slf4j-simple
- 在Jar文件中运行类
- 带参数的可运行?
- 我如何得到一个字符串的前n个字符而不检查大小或出界?
- 我可以在Java中设置enum起始值吗?
- Java中的回调函数
- c#和Java中的泛型有什么不同?和模板在c++ ?
- 在Java中，流相对于循环的优势是什么?
- Jersey在未找到InjectionManagerFactory时停止工作
- 在Java流是peek真的只是调试?
- Recyclerview不调用onCreateViewHolder
- 将JSON字符串转换为HashMap
