如何在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 + " "); } } } }
PS:这个答案并不完全针对“二叉树”,而是打印各种树。解决方案的灵感来自Linux中的“ tree”命令。