我如何在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;
}
}
当前回答
试试这个:
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表示底部行中块的长度。
用一张图片来说明想法并展示结果。
其他回答
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回答的一个变体——看到额外的|让我很烦
using map...
{
Map<Integer,String> m = new LinkedHashMap<>();
tn.printNodeWithLvl(node,l,m);
for(Entry<Integer, String> map :m.entrySet()) {
System.out.println(map.getValue());
}
then....method
private void printNodeWithLvl(Node node,int l,Map<Integer,String> m) {
if(node==null) {
return;
}
if(m.containsKey(l)) {
m.put(l, new StringBuilder(m.get(l)).append(node.value).toString());
}else {
m.put(l, node.value+"");
}
l++;
printNodeWithLvl( node.left,l,m);
printNodeWithLvl(node.right,l,m);
}
}
下面是可视化树的另一种方法:将节点保存为xml文件,然后让浏览器显示层次结构:
class treeNode{
int key;
treeNode left;
treeNode right;
public treeNode(int key){
this.key = key;
left = right = null;
}
public void printNode(StringBuilder output, String dir){
output.append("<node key='" + key + "' dir='" + dir + "'>");
if(left != null)
left.printNode(output, "l");
if(right != null)
right.printNode(output, "r");
output.append("</node>");
}
}
class tree{
private treeNode treeRoot;
public tree(int key){
treeRoot = new treeNode(key);
}
public void insert(int key){
insert(treeRoot, key);
}
private treeNode insert(treeNode root, int key){
if(root == null){
treeNode child = new treeNode(key);
return child;
}
if(key < root.key)
root.left = insert(root.left, key);
else if(key > root.key)
root.right = insert(root.right, key);
return root;
}
public void saveTreeAsXml(){
StringBuilder strOutput = new StringBuilder();
strOutput.append("<?xml version=\"1.0\" encoding=\"UTF-8\"?>");
treeRoot.printNode(strOutput, "root");
try {
PrintWriter writer = new PrintWriter("C:/tree.xml", "UTF-8");
writer.write(strOutput.toString());
writer.close();
}
catch (FileNotFoundException e){
}
catch(UnsupportedEncodingException e){
}
}
}
下面是测试它的代码:
tree t = new tree(1);
t.insert(10);
t.insert(5);
t.insert(4);
t.insert(20);
t.insert(40);
t.insert(30);
t.insert(80);
t.insert(60);
t.insert(50);
t.saveTreeAsXml();
输出如下所示:
根据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
与垂直表示相比,水平表示有点复杂。垂直打印只是简单的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排序。
不过,在这样做的时候,不要忘记为空子存储占位符,例如' '/空格,这样树看起来就像预期的那样。
现在唯一剩下的就是计算水平节点的距离,这可以用一些数学计算来完成,
计算树的宽度和高度。 一旦完成,在显示节点时,根据计算的宽度,高度和倾斜信息(如果有的话),以最佳距离呈现它们。