横向打印二叉树

第四届蓝桥杯决赛 java高职高专组第四题

横向打印二叉树

二叉树可以用于排序。其原理很简单：对于一个排序二叉树添加新节点时，先与根节点比较，若小则交给左子树继续处理，否则交给右子树。

当遇到空子树时，则把该节点放入那个位置。

比如，10 8 5 7 12 4 的输入顺序，应该建成二叉树如图1所示。

本题目要求：根据已知的数字，建立排序二叉树，并在标准输出中横向打印该二叉树。

输入数据为一行空格分开的N个整数。 N<100，每个数字不超过10000。
输入数据中没有重复的数字。

输出该排序二叉树的横向表示。对应上例中的数据，应输出：

|-12
10-|
|-8-|
| |-7
|-5-|
|-4

为了便于评卷程序比对空格的数目，请把空格用句点代替：
...|-12
10-|
...|-8-|
.......|...|-7
.......|-5-|
...........|-4

例如：
用户输入：
10 5 20
则程序输出：
...|-20
10-|
...|-5

再例如：
用户输入：
5 10 20 8 4 7
则程序输出：
.......|-20
..|-10-|
..|....|-8-|
..|........|-7
5-|
..|-4

资源约定：
峰值内存消耗（含虚拟机） < 64M
CPU消耗 < 1000ms

  1 import java.util.Scanner;
  2 
  3 
  4 public class 横向打印二叉树 {
  5     /**
  6      * 节点
  7      */
  8     static class Node{
  9         //值
 10         int data;
 11         Node left;
 12         Node right;
 13         //输出的值
 14         String s;
 15         public Node(int e){
 16             this.data=e;
 17         }
 18     }
 19     
 20     public static void main(String[] args) {
 21         //int[] n = { 34, 31, 36, 47, 23, 35, 41, 14, 12, 15, 7, 10, 8, 5, 12, 7, 3, 6 };
 22         int[] n=getInput();
 23         Node root=new Node(n[0]);
 24         root.s=root.data+"-|";
 25         
 26         for(int i=1;i<n.length;i++){
 27             Node node=new Node(n[i]);
 28             if(node.data>root.data){
 29                 addRight(node, root,0);
 30             }else{
 31                 addLeft(node,root,0);
 32             }
 33         }
 34         
 35         print(root);
 36     }
 37     /**
 38      * 接收输入
 39      * @return
 40      */
 41     public static int[] getInput(){
 42         Scanner scan=new Scanner(System.in);
 43         String s=scan.nextLine();
 44         String[] ss=s.split(" ");
 45         int[] nn=new int[ss.length];
 46         for(int i=0;i<ss.length;i++){
 47             nn[i]=Integer.parseInt(ss[i]);
 48         }
 49         return nn;
 50     }
 51     /**
 52      * 打印
 53      * @param node 根节点
 54      */
 55     public static void print(Node node){
 56         //始终先打印右节点，然后打印本身，最后打印左节点
 57         if(node.right!=null){
 58             print(node.right);
 59         }
 60         //如果没有子节点，就不打印后面的"-|“
 61         if(node.left==null&&node.right==null){
 62             System.out.println(node.s.substring(0, node.s.length()-2));
 63         }else{
 64             System.out.println(node.s);
 65         }
 66         if(node.left!=null){
 67             print(node.left);
 68         }
 69     }
 70     /**
 71      * 添加右节点
 72      * @param node 子节点
 73      * @param root 父节点
 74      * @param flag 括号层数（0 只有一层括号，1 有多层括号）
 75      */
 76     public static void addRight(Node node,Node root,int flag){
 77         if(root.right==null){
 78             node.s=root.s.replaceAll("[0-9]|-", ".").substring(0, root.s.length()-1);
 79             if(flag==0){
 80                 int index=node.s.lastIndexOf("|");
 81                 if(index!=-1){
 82                     node.s=node.s.substring(0,index)+"."+node.s.substring(index+1);
 83                 }
 84             }
 85             node.s+="|-"+node.data+"-|";
 86             
 87             root.right=node;
 88         }else if(node.data>root.right.data){
 89             addRight(node, root.right,0);
 90         }else{
 91             addLeft(node,root.right,1);
 92         }
 93     }
 94     /**
 95      * 添加左节点
 96      * @param node 子节点
 97      * @param root 父节点
 98      * @param flag 括号层数（0 只有一层括号，1 有多层括号）
 99      */
100     public static void addLeft(Node node,Node root,int flag){
101         if(root.left==null){
102             node.s=root.s.replaceAll("[0-9]|-", ".").substring(0, root.s.length()-1);
103             if(flag==0){
104                 int index=node.s.lastIndexOf("|");
105                 if(index!=-1){
106                     node.s=node.s.substring(0,index)+"."+node.s.substring(index+1);
107                 }
108             }
109             node.s+="|-"+node.data+"-|";
110             root.left=node;
111         }else if(node.data>root.left.data){
112             addRight(node, root.left,1);
113         }else{
114             addLeft(node,root.left,0);
115         }
116     }
117 }

横向打印二叉树

第四届蓝桥杯决赛 java高职高专组 第四题

横向打印二叉树

第四届蓝桥杯决赛 java高职高专组第四题