生成二叉树的工具，参考：构建二叉树
1. 打印满二叉树
1）打印满二叉树工具类
public class BinaryTreePrinter {
public static void print(TreeNode root) {
Map<Integer, List<TreeNode>> levels = new HashMap<>();
traverse(root, 1, levels);
final int maxLevel = levels.size();
System.out.println("maxLevel: " + maxLevel);
// 定义，叶子节点的宽度
final int leafNodeWidth = 4;
levels.forEach((level, nodes) -> {
// level 层节点的宽度 = 2^(maxLevel - level) * 叶子节点的宽度
int nodeWidth = (int)Math.pow(2, maxLevel- level) * leafNodeWidth;
String levelInfo = String.format("level[%s] 节点宽度[%2d]", level, nodeWidth);
System.out.print(levelInfo);
System.out.print("===| ");
nodes.forEach(node -> {
System.out.print(getNodeText(node, nodeWidth));
});
System.out.println();
// 中文比英文更宽，所以多加 3 个空格，以便对齐
System.out.print(String.join("", Collections.nCopies(levelInfo.length() + 3, " ")));
System.out.print("===| ");
if (level != maxLevel) {
nodes.forEach(node -> {
System.out.print(getEdgeText(nodeWidth));
});
System.out.println();
}
});
}
private static String getNodeText(TreeNode node, int nodeWidth) {
int leftLength = nodeWidth / 2;
String val = String.valueOf(node.val);
int rightLeght = nodeWidth - leftLength - val.length();
String left = String.join("", Collections.nCopies(leftLength, " "));
String right = String.join("", Collections.nCopies(rightLeght, " "));
// 得到长度为 nodeWidth 的表示节点的字符串
return left + val + right;
}
private static String getEdgeText(int nodeWidth) {
int edgeWidth = nodeWidth / 2;
String left = "┌" + String.join("", Collections.nCopies(edgeWidth / 2 - 1, "─"));
String right = String.join("", Collections.nCopies(edgeWidth / 2 - 1, "─")) + "┐";
String edge = left + "┴" + right;
String leftPadding = String.join("", Collections.nCopies(edgeWidth / 2, " "));
int rightPaddingLength = nodeWidth - edge.length() - leftPadding.length();
String rightPadding = String.join("", Collections.nCopies(rightPaddingLength, " "));
// 得到长度为 nodeWidth 的表示树的两个边的字符串
return leftPadding + edge + rightPadding;
}
public static void traverse(TreeNode root, int level, Map<Integer, List<TreeNode>> levels) {
if (root == null) return;
levels.computeIfAbsent(level, ArrayList::new).add(root);
traverse(root.left, level+1, levels);
traverse(root.right, level+1, levels);
}
}
2）生成满二叉树，并打印
public class BinaryTreeDemo {
public static void main(String[] args) {
TreeNode root = new BinaryTreeBuilder(3).build();
BinaryTreePrinter.print(root);
}
}
控制台输出：
maxLevel: 3
level[1] 节点宽度[ 16]===| 1
===| ┌───┴───┐
level[2] 节点宽度[ 8]===| 2 5
===| ┌─┴─┐ ┌─┴─┐
level[3] 节点宽度[ 4]===| 3 4 6 7
打印任意二叉树
1）打印满二叉树工具类
public class BinaryTreePrinter {
public static void print(TreeNode root) {
final int maxLevel = getDepth(root);
System.out.println("maxLevel: " + maxLevel);
// 满二叉树节点数为 2^maxLevel - 1;
TreeNode[] nodes = new TreeNode[(int)Math.pow(2, maxLevel)];
traverse(root, 1, nodes);
// 定义，叶子节点的宽度
final int leafNodeWidth = 4;
for (int level = 1; level <= maxLevel; ++ level) {
// level 层节点的宽度 = 2^(maxLevel - level) * 叶子节点的宽度
int nodeWidth = (int) Math.pow(2, maxLevel - level) * leafNodeWidth;
String levelInfo = String.format("level[%s] 节点宽度[%3d]", level, nodeWidth);
System.out.print(levelInfo);
System.out.print("===| ");
int beginIndex = (int) Math.pow(2, level - 1);
int endIndex = beginIndex * 2 - 1;
for (int i = beginIndex; i <= endIndex; ++i) {
System.out.print(getNodeText(nodes[i], nodeWidth));
}
System.out.println();
// 最后一层不需要 edge 了
if (level == maxLevel) break;
// 中文比英文更宽，所以多加 3 个空格，以便对齐
System.out.print(String.join("", Collections.nCopies(levelInfo.length() + 3, " ")));
System.out.print("===| ");
for (int i = beginIndex; i <= endIndex; ++i) {
System.out.print(getEdgeText(nodeWidth, nodes, i));
}
System.out.println();
}
}
private static String getNodeText(TreeNode node, int nodeWidth) {
int leftLength = nodeWidth / 2;
String val = (node == null ? "" : String.valueOf(node.val));
int rightLeght = nodeWidth - leftLength - val.length();
String left = String.join("", Collections.nCopies(leftLength, " "));
String right = String.join("", Collections.nCopies(rightLeght, " "));
// 得到长度为 nodeWidth 的表示节点的字符串
return left + val + right;
}
private static String getEdgeText(int nodeWidth, TreeNode[] nodes, int index) {
TreeNode leftNode = nodes[index * 2];
TreeNode rightNode = nodes[index * 2 + 1];
// 左右子树都为空
if (leftNode == null && rightNode == null) {
return String.join("", Collections.nCopies(nodeWidth, " "));
}
int edgeWidth = nodeWidth / 2;
String edge = getEdge(edgeWidth, leftNode, rightNode);
String leftPadding = String.join("", Collections.nCopies(edgeWidth / 2, " "));
int rightPaddingLength = nodeWidth - edge.length() - leftPadding.length();
String rightPadding = String.join("", Collections.nCopies(rightPaddingLength, " "));
// 得到长度为 nodeWidth 的表示树的两个边的字符串
return leftPadding + edge + rightPadding;
}
private static String getEdge(int edgeWidth, TreeNode leftNode, TreeNode rightNode) {
// 左子树为空
if (leftNode == null) {
String left = String.join("", Collections.nCopies(edgeWidth / 2, " "));
String right = String.join("", Collections.nCopies(edgeWidth / 2 - 1, "─")) + "┐";
return left + "└" + right;
}
// 右子树为空
if (rightNode == null) {
String left = "┌" + String.join("", Collections.nCopies(edgeWidth / 2 - 1, "─"));
String right = String.join("", Collections.nCopies(edgeWidth / 2, " "));
return left + "┘" + right;
}
String left = "┌" + String.join("", Collections.nCopies(edgeWidth / 2 - 1, "─"));
String right = String.join("", Collections.nCopies(edgeWidth / 2 - 1, "─")) + "┐";
return left + "┴" + right;
}
public static int getDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
}
public static void traverse(TreeNode root, int index, TreeNode[] nodes) {
if (root == null) return;
// System.out.println("index:" + index);
nodes[index] = root;
traverse(root.left, index*2 , nodes);
traverse(root.right, index*2+1, nodes);
}
}
2）生成任意二叉树，并打印
public class BinaryTreeDemo {
public static void main(String[] args) {
TreeNode root = new BinaryTreeBuilder(4, 0.8, 0.7).build();
BinaryTreePrinter.print(root);
}
}
控制台输出：
maxLevel: 4
level[1] 节点宽度[ 32]===| 1
===| ┌───────┴───────┐
level[2] 节点宽度[ 16]===| 2 5
===| └───┐ ┌───┴───┐
level[3] 节点宽度[ 8]===| 3 6 8
===| ┌─┘ └─┐ ┌─┴─┐
level[4] 节点宽度[ 4]===| 4 7 9 10
网友评论