J7 例题-5 二叉搜索树

题目描述

输入一系列整数，利用所给数据建立一个二叉搜索树，并输出其前序、中序和后序遍历序列。

输入格式

第一行一个整数 $n$，表示输入整数数量。

第二行包含 $n$ 个整数。

输出格式

共三行，第一行输出前序遍历序列，第二行输出中序遍历序列，第三行输出后序遍历序列。

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

样例输入

5
1 6 5 9 8

样例输出

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

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据，$1≤n≤100000$，输入元素取值范围 $[1,1000000]$。