Jobdu-1201.Binary Sort Tree

Posted on | In

Jobdu-1201-二叉排序树

Question

题目描述：

输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。

输入：

输入第一行包括一个整数n(1<=n<=100)。    接下来的一行包括n个整数。

输出：

可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。    每种遍历结果输出一行。每行最后一个数据之后有一个空格。

样例输入：

51 6 5 9 8

样例输出：

1 6 5 9 8 1 5 6 8 9 5 8 9 6 1

提示：

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import java.util.Scanner;
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Main {
    static class Node{
        int val;
        Node left;
        Node right;
        public Node(int value) {
            this.val = value;
        }
    }
    public static void preOrder(Node node){
        System.out.print(node.val + " ");
        if(node.left != null)
            preOrder(node.left);
        if(node.right != null)
            preOrder(node.right);
    }
    public static void midOrder(Node node){
        if(node.left != null)
            midOrder(node.left);
        System.out.print(node.val + " ");
        if(node.right != null)
            midOrder(node.right);
    }
    public static void postOrder(Node node){
        if(node.left != null)
            postOrder(node.left);
        if(node.right != null)
            postOrder(node.right);
        System.out.print(node.val + " ");
    }
    public static void insert(int value, Node root){
        Node node = new Node(value);
        Node temp = root;
        System.out.println(root.val);
        while(true){
            if(node.val < temp.val){
                System.out.println("small");
                if(temp.left == null){
                    temp.left = node;
                    break;
                }else
                    temp = temp.left;
            }else if(node.val > temp.val){
                System.out.println("large");
                if(temp.right == null){
                    temp.right = node;
                    break;
                }
                else
                    temp = temp.right;
            }
            // for case "equal"
            else
                break;
        }
    }
    public static Node makeBinaryTree(int[] arr){
        Node root = new Node(arr[0]);
        for(int i = 1; i < arr.length; i++) {
            int value = arr[i];
            insert(value, root);
        }
        return root;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] arr = new int[num];
        for(int i = 0; i < num; i++){
            arr[i] = sc.nextInt();
        }
        // Make binary tree
        Node root = new Node(arr[0]);
        for(int i = 1; i < num; i++) {
            int value = arr[i];
            insert(value, root);
        }
//        Node root = makeBinaryTree(arr);
        // Print tree
        preOrder(root);
        System.out.println();
        midOrder(root);
        System.out.println();
        postOrder(root);
    }
}