美文网首页
打印二叉树

打印二叉树

作者: 蓝笔头 | 来源:发表于2021-09-09 09:51 被阅读0次

生成二叉树的工具,参考:构建二叉树

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

参考

相关文章

  • JZ-022-从上往下打印二叉树

    从上往下打印二叉树 题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印。题目链接: 从上往下打印二叉树...

  • 二叉树的遍历

    从上往下打印二叉树 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 按之字形顺序打印二叉树 请实现一个函数...

  • [剑指offer]刷题笔记

    按之字顺序打印二叉树 把二叉树打印成多行 按之字顺序打印二叉树【树】【常考!!!】 题目描述:请实现一个函数按照之...

  • 算法(3)层次顺序遍历二叉树

    问题:按照层次顺序遍历二叉树,每层换行打印 1、普通的按层打印二叉树只需要使用队列就可以了2、按层打印二叉树,需要...

  • 算法与数据结构

    二叉树 1. 二叉树打印练习题 有一棵二叉树,请设计一个算法,按照层次打印这棵二叉树。给定二叉树的根结点root,...

  • 23 从上到下遍历二叉树 树的层次遍历

    从上往下打印二叉树 题目描述: 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 解题思路: 经典题目,树的...

  • 剑指offer(Java版)day05:从上往下打印二叉树|二叉

    1从上往下打印二叉树 【题目】从上往下打印出二叉树的每个节点,同层节点从左至右打印。 【考察点】举例让抽象具体...

  • 【直通BAT】剑指Offer-经典试题整理(4)

    32.1 不分行从上往下打印二叉树 题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 解法 先将根...

  • BFS的分层(利用queue)

    层序遍历二叉树,并且每层换行打印 有一棵二叉树,请设计一个算法,按照层次打印这棵二叉树。给定二叉树的根结点root...

  • 剑指offer-22-从上往下打印二叉树

    从上往下打印二叉树: 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 思路:利用bfs思想,构建一个队列,...

网友评论

      本文标题:打印二叉树

      本文链接:https://www.haomeiwen.com/subject/cyrvwltx.html