我如何在Java中打印一个二叉树，这样输出就像:
4
/ \
2 5
我的节点:
public class Node<A extends Comparable> {
Node<A> left, right;
A data;
public Node(A data){
this.data = data;
}
}
当前回答
试试这个:
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表示底部行中块的长度。
用一张图片来说明想法并展示结果。
其他回答
你的树每一层需要两倍的距离:
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]]
然后你可以遍历数组来打印你的树，根据深度打印第一个元素之前和元素之间的空格，根据下一层数组中对应的元素是否被填充打印行。 如果您的值可以超过一个字符长，您需要在创建数组表示时找到最长的值，并相应地乘以所有宽度和行数。
我已经创建了简单的二叉树打印机。您可以随心所欲地使用和修改它，但无论如何它都没有优化。我认为这里有很多东西可以改进;)
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
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
这是水平视图最简单的解决方案。我举了很多例子。很适合我的目的。更新自@ 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
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回答的一个变体——看到额外的|让我很烦
推荐文章
- javac和Eclipse编译器之间的区别是什么?
- 工厂模式和策略模式之间的区别是什么?
- 在Java中使用正则表达式提取值
- 如何允许所有网络连接类型HTTP和HTTPS在Android(9)馅饼?
- Intellij IDEA Java类在保存时不能自动编译
- 何时使用Mockito.verify()?
- 在maven中安装mvn到底做什么
- 不可变与不可修改的集合
- 如何在JSON中使用杰克逊更改字段名
- GSON -日期格式
- 如何从线程捕获异常
- 无法解析主机"<URL here>"没有与主机名关联的地址
- 如何在Java中打印二叉树图?
- String.format()在Java中格式化双重格式
- com.jcraft.jsch.JSchException： UnknownHostKey
