技术难点

以树状形式打印二叉树的关键难点在于，如何计算和控制每个节点的打印位置

解决思路

将二叉树的所有节点从左往右全部打印出来，正好和二叉树中序遍历的结果是一样的

利用这个特点，我们就可以通过中序遍历结果，来反推每个节点位置，再按广度优先遍历算法，逐行打印即可

具体方案和流程图如下

二叉树

中序遍历

每个字符间要保持一定间隔，所以加上占位符

广度优先遍历

保持每个节点横向位置不变，根据广度优先遍历调整节点层次位置

将占位符替换为连接符和空白字符

这样就大功告成了，思路有了，实现就不难了

注意细节

• 为了保证所有字符等宽，可将字符转为全角字符
• 连接符可以用横杠竖杠等字符来代替
• 每个节点的字符串可能不止一个字符，因此实现时还要考虑节点字符串的长度

实现代码

这里我们只讲解怎么打印二叉树，测试数据的构建，我们直接借用上一章的二叉搜索树

	@SuppressWarnings("all")
	public class BinaryNode<T extends Comparable> {
	
	    T value;
	
	    BinaryNode<T> left;
	    BinaryNode<T> right;
	
	    public int getChildCount() {
	        if (left == null && right == null)
	            return 0;
	        if (left != null && right != null)
	            return 2;
	        return 1;
	    }
	
	    @Override
	    public String toString() {
	        return String.valueOf(value);
	    }
	}

	import java.util.LinkedHashMap;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Map;
	
	@SuppressWarnings("all")
	public class BinaryPrinter {
	
	    BinaryNode root;
	
	    //中序遍历和广度遍历结果
	    final List<BinaryNode> inorderTraverseList = new LinkedList();
	    final List<BinaryNode> breadthTraverseList = new LinkedList();
	
	    //所有节点的坐标
	    final Map<BinaryNode, Integer> xMap = new LinkedHashMap();
	    final Map<BinaryNode, Integer> yMap = new LinkedHashMap();
	
	    //整个输出矩阵中的所有字符
	    final List<List<Character>> charForm = new LinkedList();
	
	    //下个节点的坐标
	    int nextX;
	    int nextY;
	
	    public void setRootNode(BinaryNode root) {
	        this.root = root;
	    }
	
	    public void Print() {
	        //清空旧数据
	        inorderTraverseList.clear();
	        breadthTraverseList.clear();
	        xMap.clear();
	        yMap.clear();
	        charForm.clear();
	        nextX = 0;
	        nextY = 0;
	        //如果节点为空，直接结束
	        if (root == null) {
	            System.out.println("Empty Tree");
	            return;
	        }
	        //中序遍历，计算出每个节点的横向X坐标
	        InorderTraverse(root);
	        //层次遍历，计算出每个节点的纵向Y坐标
	        List<BinaryNode> levelNodeList = new LinkedList();
	        levelNodeList.add(root);
	        BreadthTraverse(levelNodeList);
	        //生成最终的二维字符数组
	        FillCharForm();
	        //打印结果
	        for (List<Character> row : charForm) {
	            for (Character cell : row)
	                System.out.print(cell);
	            System.out.println();
	        }
	    }
	
	    //中序遍历
	    private void InorderTraverse(BinaryNode node) {
	        if (node.left != null)
	            InorderTraverse(node.left);
	        inorderTraverseList.add(node);
	        xMap.put(node, nextX);
	        nextX = nextX + String.valueOf(node.value).length() + 1;
	        if (node.right != null)
	            InorderTraverse(node.right);
	    }
	
	    //层次遍历，当前层次的所有节点
	    private void BreadthTraverse(List<BinaryNode> levelNodeList) {
	        if (levelNodeList.isEmpty())
	            return;
	        for (BinaryNode node : levelNodeList)
	            yMap.put(node, nextY);
	        breadthTraverseList.addAll(levelNodeList);
	        nextY = nextY + 1;
	        List<BinaryNode> nextLevelNodeList = new LinkedList();
	        for (BinaryNode node : levelNodeList) {
	            if (node.left != null)
	                nextLevelNodeList.add(node.left);
	            if (node.right != null)
	                nextLevelNodeList.add(node.right);
	        }
	        BreadthTraverse(nextLevelNodeList);
	    }
	
	    //生成最终的二维字符数组
	    private void FillCharForm() {
	        //填充占位符
	        for (int y = 0; y <= nextY - 1; y++) {
	            List<Character> row = new LinkedList();
	            charForm.add(row);
	            for (int x = 0; x <= nextX - 2; x++) {
	                char character = toFullWidth(' ');
	                row.add(character);
	            }
	        }
	        //填充节点字符串
	        for (BinaryNode node : breadthTraverseList) {
	            int x = xMap.get(node);
	            int y = yMap.get(node);
	            String value = String.valueOf(node.value);
	            for (int i = 0; i < value.length(); i++)
	                setChar(x + i, y, value.charAt(i));
	        }
	        //填充连接符
	        for (BinaryNode node : breadthTraverseList) {
	            if (node.left != null) {
	                int x1 = xMap.get(node.left);
	                int x2 = xMap.get(node);
	                int y = yMap.get(node);
	                setChar(x1, y, '|');
	                for (int i = x1 + 1; i < x2; i++)
	                    setChar(i, y, '-');
	            }
	            if (node.right != null) {
	                int x1 = xMap.get(node);
	                int x2 = xMap.get(node.right);
	                int y = yMap.get(node);
	                setChar(x2, y, '|');
	                String value = String.valueOf(node.value);
	                for (int i = x1 + value.length(); i < x2; i++)
	                    setChar(i, y, '-');
	            }
	        }
	    }
	
	    //设置指定位置的字符
	    protected void setChar(int x, int y, char halfChar) {
	        char fullChar = toFullWidth(halfChar);
	        charForm.get(y).set(x, fullChar);
	    }
	
	    //半角字符转全角字符
	    private char toFullWidth(char halfChar) {
	        if (halfChar == 32)
	            return (char) 12288;
	        if (halfChar < 127)
	            return (char) (halfChar + 65248);
	        return halfChar;
	    }
	}

	@SuppressWarnings("all")
	public class Demo {
	
	    public static void main(String[] args) {
	        BinarySearchTree bst = new BinarySearchTree();
	        bst.Insert(90);
	        bst.Insert(30);
	        bst.Insert(99);
	        bst.Insert(20);
	        bst.Insert(50);
	        bst.Insert(40);
	        bst.Insert(70);
	        bst.Insert(60);
	        bst.Insert(80);
	        BinaryPrinter printer = new BinaryPrinter();
	        printer.setRootNode(bst.root);
	        printer.Print();
	    }
	}

运行结果如下

效果还是相当可以的，大功告成！