Java 按照树形结构打印二叉树

发表于 分类于 ， Valine：

在我们完成一棵树的构建之后，如果我们想要看这棵树的结构，不像数组或者 List 等数据结构，我们可以非常方便地用各种方式将其中的所有元素打印出来，对于树而言，这个过程要麻烦得多，我们可以用各种遍历方式得到这棵树的结构，但是终究还是不够直观。

如果我们可以按照树的结构，将其打印出来就好了，那么本文就是一种实现这个目标的思路以供参考。

树的结构

本文中所用的树的结构是 LeetCode 上所用的树的结构，其定义如下：

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

打印树思路

总体思路是，用一个二维的字符串数组来储存每个位置应该打印什么样的输出。

首先，先确定树的形状。为了美观，我设定在最后一行的每个数字之间的间隔为 3 个空格，而在之上的每一层的间隔，有兴趣的同学可以自己推算一下，总之，越往上，间隔是越大的，而且是一个简单的线性增加的关系。

为了绘制出这样的形状，首先，我们需要获得树的层数（用一个简单的递归即可得到），根据树的层数，确定我们的二维数组的大小，即高度和宽度。之后，用先序遍历的方式，遍历树的每个节点，并进行相对应的写入操作。

实现代码

public class TreeNodeShow {

    // 用于获得树的层数
    private static int getTreeDepth(TreeNode root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
    }

    private static void writeArray(TreeNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) return;
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = String.valueOf(currNode.val);

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.right != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }


    public static void show(TreeNode root) {
        if (root == null){
            System.out.println("EMPTY!");
            return;
        }
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i++) {
            for (int j = 0; j < arrayWidth; j++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth / 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line : res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

测试用例

测试一

TreeNode q = TreeNodeUtil.arrayToTreeNode(new Integer[]{2,null,4,9,8,null,null,4});
TreeNodeShow.show(q);

打印结果：

        2            
           \         
              4      
            /   \    
          9       8  
                 /   
                4

表示树：

image-20210304160524113

测试二

TreeNode q = TreeNodeUtil.arrayToTreeNode(new Integer[]{3,1,4,3,null,1,5});
TreeNodeShow.show(q);

打印结果：

      3      
    /   \    
  1       4  
 /       / \ 
3       1   5

表示树：

image-20210304155514565

特别说明

由于本方法的思路是基于字符串的数组的，所以并不可能完美适配所有情况，比如当树的高度很高以后，可能看起来会很奇怪。

还有一个问题就是，虽然已经做了自适应处理，但是，如果出现超过 5 位的数字（比如 123123），其所在的行可能会有一点向右的偏移，若偏的不多，是不影响观察的，但若偏的多了就有点影响了。不过这里已经做了处理，所以出现三位或者四位数的时候是没有问题的。

不过，在日常的应用中，应该是完全够用的，希望这段代码能为大家带来便利。

相关文章