1 问题描述

问题描述

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

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

比如，10 8 5 7 12 4 的输入顺序，应该建成二叉树如下图所示，其中.表示空白。

...|-12

10-|

...|-8-|

.......|...|-7

.......|-5-|

...........|-4

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

输入格式

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

输入数据中没有重复的数字。

输出格式

输出该排序二叉树的横向表示。为了便于评卷程序比对空格的数目，请把空格用句点代替：

样例输入1

10 5 20

样例输出1

...|-20

10-|

...|-5

样例输入2

5 10 20 8 4 7

样例输出2

.......|-20

..|-10-|

..|....|-8-|

..|........|-7

5-|

..|-4

2 解决方案

下面代码详解请见参考资料。

具体代码如下：

import java.util.Scanner;public class Main {    public static int root;    public static point[] tree = new point[10005];        static class point {        public int value;   //自身节点编号        public int father;  //父母节点编号        public int left;    //左孩子节点编号        public int right;   //右孩子节点编号                public point() {            this.value = 0;            this.father = 0;            this.left = 0;            this.right = 0;        }    }        public void dfs(int start, String s, int n, String s1) {        if(tree[start].value == root)            s = s + tree[start].value;        else {            s = s + "-|-";            s = s + tree[start].value;        }        if(tree[start].right > 0) {            s1 = s1 + "1";            dfs(tree[start].right, s, n + 1, s1);            s1 = s1.substring(0, s1.length() - 1);        }        int len = s.length();        int cot = 0;        for(int i = 0;i < len;i++) {            if(s.charAt(i) == '|') {                if(s1.length() <= cot + 1 || s1.charAt(cot) != s1.charAt(cot + 1))                    System.out.print("|");                else                    System.out.print(".");                cot++;            } else if(cot < n) {                System.out.print(".");            } else {                System.out.print(s.charAt(i));            }        }        if(tree[start].left > 0 || tree[start].right > 0)            System.out.print("-|");        System.out.println();        if(tree[start].left > 0) {            s1 = s1 + "0";            dfs(tree[start].left, s, n + 1, s1);            s1 = s1.substring(0, s1.length() - 1);        }    }        public static void main(String[] args) {        Main test = new Main();        Scanner in = new Scanner(System.in);        String A = in.nextLine();        String[] arrayA = A.split(" ");        root = Integer.valueOf(arrayA[0]);        for(int i = 0;i < tree.length;i++)            tree[i] = new point();        for(int i = 0;i < arrayA.length;i++) {            int a = Integer.valueOf(arrayA[i]);            tree[a].value = a;        }        for(int i = 1;i < arrayA.length;i++) {            int a = Integer.valueOf(arrayA[i]);            int temp = root;            while(true) {                if(a > temp) {                    if(tree[temp].right == 0) {                        tree[temp].right = a;                        break;                    } else                        temp = tree[temp].right;                }                else {                    if(tree[temp].left == 0) {                        tree[temp].left = a;                        break;                    } else                         temp = tree[temp].left;                }            }        }        String s = "";        String s1 = "";        test.dfs(root, s, 0, s1);    }}