我如何在Java中打印一个二叉树，这样输出就像:
4
/ \
2 5
我的节点:
public class Node<A extends Comparable> {
Node<A> left, right;
A data;
public Node(A data){
this.data = data;
}
}
当前回答
你的树每一层需要两倍的距离:
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]]
然后你可以遍历数组来打印你的树，根据深度打印第一个元素之前和元素之间的空格，根据下一层数组中对应的元素是否被填充打印行。 如果您的值可以超过一个字符长，您需要在创建数组表示时找到最长的值，并相应地乘以所有宽度和行数。
其他回答
试试这个:
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排序。
不过，在这样做的时候，不要忘记为空子存储占位符，例如' '/空格，这样树看起来就像预期的那样。
现在唯一剩下的就是计算水平节点的距离，这可以用一些数学计算来完成，
计算树的宽度和高度。 一旦完成，在显示节点时，根据计算的宽度，高度和倾斜信息(如果有的话)，以最佳距离呈现它们。
https://github.com/AharonSambol/PrettyPrintTreeJava
我知道我迟到了。但是我做了这个解决方案，不仅适用于简单的树，也适用于更复杂的树(如多行字符串)
示例输出:
我已经创建了简单的二叉树打印机。您可以随心所欲地使用和修改它，但无论如何它都没有优化。我认为这里有很多东西可以改进;)
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
推荐文章
- 在流中使用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
