【数据结构与算法】【14】以树状形式打印二叉树

技术难点

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

解决思路

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

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

具体方案和流程图如下

二叉树

中序遍历

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

广度优先遍历

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

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

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

注意细节

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

实现代码

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

	@SuppressWarnings("all")
	public class BinaryNode {
	
	    T value;
	
	    BinaryNode left;
	    BinaryNode 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 inorderTraverseList = new LinkedList();
	    final List breadthTraverseList = new LinkedList();
	
	    //所有节点的坐标
	    final Map xMap = new LinkedHashMap();
	    final Map yMap = new LinkedHashMap();
	
	    //整个输出矩阵中的所有字符
	    final List 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 levelNodeList = new LinkedList();
	        levelNodeList.add(root);
	        BreadthTraverse(levelNodeList);
	        //生成最终的二维字符数组
	        FillCharForm();
	        //打印结果
	        for (List 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 levelNodeList) {
	        if (levelNodeList.isEmpty())
	            return;
	        for (BinaryNode node : levelNodeList)
	            yMap.put(node, nextY);
	        breadthTraverseList.addAll(levelNodeList);
	        nextY = nextY + 1;
	        List 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