출력이 다음과 같이되도록 Java로 이진 트리를 인쇄하는 방법은 무엇입니까?
4
/ \
2 5 내 노드 :
public class Node<A extends Comparable> {
Node<A> left, right;
A data;
public Node(A data){
this.data = data;
}
}답변
간단한 이진 트리 프린터를 만들었습니다. 원하는대로 사용하고 수정할 수 있지만 어쨌든 최적화되지 않았습니다. 나는 여기에 많은 것들이 향상 될 수 있다고 생각합니다.)
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 답변
[큰] 나무를 한 줄씩 인쇄하십시오.
출력 예 :
z
├── c
│ ├── a
│ └── b
├── d
├── e
│ └── asdf
└── f암호:
public class TreeNode {
final String name;
final List<TreeNode> children;
public TreeNode(String name, List<TreeNode> children) {
this.name = name;
this.children = children;
}
public String toString() {
StringBuilder buffer = new StringBuilder(50);
print(buffer, "", "");
return buffer.toString();
}
private void print(StringBuilder buffer, String prefix, String childrenPrefix) {
buffer.append(prefix);
buffer.append(name);
buffer.append('\n');
for (Iterator<TreeNode> it = children.iterator(); it.hasNext();) {
TreeNode next = it.next();
if (it.hasNext()) {
next.print(buffer, childrenPrefix + "├── ", childrenPrefix + "│ ");
} else {
next.print(buffer, childrenPrefix + "└── ", childrenPrefix + " ");
}
}
}
}추신이 답변은 “이진”나무에 초점을 맞추지 않고 모든 종류의 나무를 인쇄합니다. 해결책은 리눅스의 “tree”명령에서 영감을 얻은 것입니다.
답변
나는 이것을 위해 향상된 크기의 알고리즘을 만들었습니다. 줄을 사용하여 하향식으로 인쇄합니다.
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;
}
}
}이것을 Tree에 사용하려면 Node클래스를 구현하십시오 PrintableNode.
출력 예 :
2952:0
┌───────────────────────┴───────────────────────┐
1249:-1 5866:0
┌───────────┴───────────┐ ┌───────────┴───────────┐
491:-1 1572:0 4786:1 6190:0
┌─────┘ └─────┐ ┌─────┴─────┐
339:0 5717:0 6061:0 6271:0 답변
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의 답변에서 변형 된 것입니다.
답변
에서 적응 Vasya Novikov 보낸 사람 의 대답하는 것이 더 만들기 위해 바이너리 및을 사용 StringBuilder효율 (합치 String자바에서 함께 오브젝트은 일반적으로 비효율적이다).
public StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) {
if(right!=null) {
right.toString(new StringBuilder().append(prefix).append(isTail ? "│ " : " "), false, sb);
}
sb.append(prefix).append(isTail ? "└── " : "┌── ").append(value.toString()).append("\n");
if(left!=null) {
left.toString(new StringBuilder().append(prefix).append(isTail ? " " : "│ "), true, sb);
}
return sb;
}
@Override
public String toString() {
return this.toString(new StringBuilder(), true, new StringBuilder()).toString();
}산출:
│ ┌── 7
│ ┌── 6
│ │ └── 5
└── 4
│ ┌── 3
└── 2
└── 1
└── 0답변
michal.kreuzman 좋은 말 하나.
나는 이것이 스스로 도움이되는 것을 발견했을 때 스스로 프로그램을 만들고 그물에 코드를 검색하는 게으른 느낌이었습니다.
그러나 공백이 아닌 탭을 사용하지 않고 구조가 잘못 배치되고 프로그램의 사용이 느슨해지기 때문에 두 자리 이상을 사용하는 것처럼 한 자리에서만 작동한다는 것을 두려워합니다.
내 나중에 코드에 관해서는 더 큰 입력이 필요했습니다 (적어도 10 이상).
그것은 지금 약간의 버그가 있습니다. 다시 한 번 나는 그것을 교정하는 게으른 느낌이 들지만 매우 아름답게 인쇄되고 노드는 큰 가치를 취할 수 있습니다.
나무는 질문에서 언급했듯이 270도 회전합니다. 🙂
public static void printBinaryTree(TreeNode root, int level){
if(root==null)
return;
printBinaryTree(root.right, level+1);
if(level!=0){
for(int i=0;i<level-1;i++)
System.out.print("|\t");
System.out.println("|-------"+root.val);
}
else
System.out.println(root.val);
printBinaryTree(root.left, level+1);
} 이 기능을 사용자가 지정한 TreeNode와 함께 배치하고 처음에는 레벨을 0으로 유지하고 즐기십시오!
다음은 몇 가지 샘플 출력입니다.
| | |-------11
| |-------10
| | |-------9
|-------8
| | |-------7
| |-------6
| | |-------5
4
| |-------3
|-------2
| |-------1
| | | |-------10
| | |-------9
| |-------8
| | |-------7
|-------6
| |-------5
4
| |-------3
|-------2
| |-------1문제는 확장 가지에만 있습니다. 최대한 빨리 문제를 해결하려고 노력하지만 그때까지도 사용할 수 있습니다.
답변
나무는 각 레이어마다 두 배의 거리가 필요합니다.
ㅏ
/ \
/ \
/ \
/ \
기원전
/ \ / \
/ \ / \
Defg
/ \ / \ / \ / \
Hijklmno
깊이에 따라 하나의 배열로 배열을 배열로 저장할 수 있습니다.
[[a], [b, c], [d, e, f, g], [h, i, j, k, l, m, n, o]]
트리가 가득 차지 않은 경우 해당 배열에 빈 값을 포함해야합니다.
ㅏ
/ \
/ \
/ \
/ \
기원전
/ \ / \
/ \ / \
Defg
/ \ \ / \ \
힐 크모
[[a], [b, c], [d, e, f, g], [h, i,, k, l, m,, o]]
그런 다음 배열을 반복하여 트리를 인쇄하고 첫 번째 요소 앞의 간격을 인쇄하고 깊이에 따라 요소 사이를 인쇄하고 다음 레이어에 대한 배열의 해당 요소가 채워 졌는지에 따라 선을 인쇄 할 수 있습니다. 값이 2자를 초과 할 수있는 경우 배열 표현을 작성하는 동안 가장 긴 값을 찾아 모든 너비와 행 수를 곱해야합니다.
