我正在应对以下代码挑战：
是一个没有平衡的简单二叉搜索树。 它可能包含通过PrintableTree方法添加的 int 值。 主要的挑战是通过add方法漂亮地打印树。这意味着应该将整棵树转换为表示其内部结构的字符串，从较小的值到较大的值。此外，您必须使用方框图字符来显示节点连接。prettyPrint例子：
元素：123 11 200 1 100 150 2000
漂亮的印刷树：
┌1 ┌11┤ │ └100 123┤ │ ┌150 └200┤ └2000另一个例子（不那么平衡的树）：
元素：931 39 196 385 388 207 185 955 957 542 904 498 394
漂亮的印刷树：
┌39┐ │ │ ┌185 │ └196┤ │ │ ┌207 │ └385┤ │ └388┐ │ │ ┌394 │ │ ┌498┘ │ └542┤ │ └904 931┤ └955┐ └957你的类应该实现这个接口
public interface PrintableTree { void add(int i); String prettyPrint(); static PrintableTree getInstance() { return new PrettyPrintableTree(); } }
我写了这个实现：
public class PrettyPrintableTree implements PrintableTree {
private static class Node {
private final int data;
private Node left = null;
private Node right = null;
public Node(int data) {
this.data = data;
}
public int getSize() {
return Integer.toString(data).length();
}
}
private Node root = null;
private StringBuilder mainSB = new StringBuilder();
@Override
public void add(int i) {
root = add(root, i);
}
private Node add(Node node, int value) {
if (node == null) {
return new Node(value);
} else if (value < node.data) {
node.left = add(node.left, value);
} else {
node.right = add(node.right, value);
}
return node;
}
private void printSimple(Node node) {
if (node != null) {
printSimple(node.left);
System.out.println(node.data);
printSimple(node.right);
}
}
@Override
public String prettyPrint() {
printTree(root,0, false);
System.out.println(mainSB);
return mainSB.toString();
}
private void printTree(Node node, int space, boolean isRight)
{
if (node == null) return;
space += node.getSize() + 1;
printTree(node.left, space, false);
if (node == root) {
space = space - root.getSize() - 1;
}
if (node == root.left) {
space = root.getSize();
}
if (node == root.right) {
space = root.getSize();
}
mainSB.append(" ".repeat(Math.max(0, space)));
if (node.right == null && node.left == null) {
if (node == root)
mainSB.append(node.data).append("\n");
else
mainSB.append(isRight ? "└" : "┌").append(node.data).append("\n");
}
else if (node.right != null && node.left != null) {
if (node == root)
mainSB.append(node.data).append("┤").append("\n");
else
mainSB.append(isRight ? "└" : "┌").append(node.data).append("┤").append("\n");
}
else if (node.right == null) {
if (node == root)
mainSB.append(node.data).append("┘").append("\n");
else
mainSB.append(isRight ? "└" : "┌").append(node.data).append("┘").append("\n");
}
else {
if (node == root)
mainSB.append(node.data).append("┐").append("\n");
else
mainSB.append(isRight ? "└" : "┌").append(node.data).append("┐").append("\n");
}
printTree(node.right, space, true);
}
}
但是我有一些问题：
我不知道如何添加“|”字符 so 连接垂直距离相距很远的节点。水平间距也存在一些问题。
您可以在上述代码产生的以下输出中看到这些问题：
元素：123 11 200 1 100 150 2000
┌1
┌11┤
└100
123┤
┌150
└200┤
└2000
元素：931 39 196 385 388 207 185 955 957 542 904 498 394
┌39┐
┌185
└196┤
┌207
└385┤
└388┐
┌394
┌498┘
└542┤
└904
931┤
└955┐
└957
您可以使用第二个 StringBuilder 来维护应该只出现在one 行上的内容，这样您就可以跟踪应该在树中更高（更左边）绘制的垂直线。
然后用它的副本扩展主 StringBuilder。
注意：我不会使用实例变量来维护该 StringBuilder。似乎更好的做法是为此使用局部变量，将其作为参数传递。
以下是您可以定义的函数：
public void prettyPrint() {
System.out.println(prettyString());
}
public String prettyString() {
StringBuilder treeSB = new StringBuilder();
prettyString(root, new StringBuilder("\n"), treeSB);
return treeSB.substring(1); // Omit initial '\n'
}
private void prettyString(Node node, StringBuilder lineSB, StringBuilder treeSB)
{
if (node == null) return;
int dataSize = node.getSize(); // Integer.toString(node.data).length();
int depth = lineSB.length();
int i = "\n │".indexOf(lineSB.charAt(depth - 1));
int j = (node.left != null ? 2 : 0) + (node.right != null ? 1 : 0);
lineSB.append(" ".repeat(dataSize + 1));
prettyString(node.left, lineSB, treeSB);
lineSB.setLength(depth - 1);
treeSB.append(lineSB);
treeSB.append("\n┌└".charAt(i));
treeSB.append(node.data);
treeSB.append(" ┐┘┤".charAt(j));
lineSB.append("\n│ ".charAt(i));
lineSB.append(" ".repeat(dataSize));
lineSB.append(" │ │".charAt(j));
prettyString(node.right, lineSB, treeSB);
}