4933.二叉搜索树 I

## 题目描述

搜索树是一种支持动态集合操作的数据结构，包括插入、查找、删除等操作。因此，搜索树既可以作为字典使用，也可以作为优先队列使用。

二叉搜索树是最基础的搜索树之一，其存储的键值始终满足以下二叉搜索树性质：

设x为二叉搜索树中的一个节点。若$y$是$x$左子树中的节点，则$y.key\lex.key$；若$y$是$x$右子树中的节点，则$x.key\ley.key$。

下图展示了一个二叉搜索树的示例:

例如，位于包含键值$80$的节点左子树中的所有节点键值都小于或等于$80$，而右子树中的节点键值都大于或等于$80$。二叉搜索树这一特性使得我们可以通过中序遍历以升序形式输出树中所有键值。

二叉搜索树的实现必须确保在插入或删除节点后，其性质仍然保持。树可采用链式数据结构表示，其中每个节点均为对象。除键值字段和卫星数据外，每个节点还包含三个指针字段：$left$（指向左子节点）、$right$（指向右子节点）以及$p$（指向父节点）。

要将新值$v$插入二叉搜索树$T$中，可采用如下伪代码所示的插入过程。该过程接收一个节点$z$作为参数，其中$z.key=v，z.left=NIL，z.right=NIL$。插入过程会修改树$T$及节点$z$的若干字段，从而将$z$安置到树中的合适位置。

```
1 insert(T, z)
2     y = NIL // x 的父节点
3     x = 'the root of T'
4     while x ≠ NIL
5         y = x // 设置父节点
6         if z.key < x.key
7             x = x.left // 移动到左子节点
8         else
9             x = x.right // 移动到右子节点
10    z.p = y
11
12    if y == NIL // 树 T 为空
13        'the root of T' = z
14    else if z.key < y.key
15        y.left = z // z 作为 y 的左子节点
16    else
17        y.right = z // z 作为 y 的右子节点
```

编写一个程序对二叉搜索树 $T $执行以下操作：

- insert k：向树 $T $中插入一个键值为$ k$ 的节点。
- print：分别按中序遍历和前序遍历输出二叉搜索树的所有键值。

初始状态下，树$ T$ 为空。插入操作需使用上述伪代码实现。

## 输入格式

第一行输入操作的总数 $m$。

接下来的 $m$ 行，每行给出一个操作，格式为 `insert k`（插入键值 $k$）或 `print`（输出遍历结果）。

## 输出格式

对于每个 $print$操作，分别在一行中输出中序遍历和前序遍历得到的键值列表。每个键值前需用空格隔开。

## 数据范围

- 操作的总数$\le500,000$。
	其中 print 操作的次数 $\le 10$。
	每个键值的取值范围为 $-2,000,000,000 \le key \le 2,000,000,000$。
	若使用上述伪代码实现插入操作，二叉搜索树的高度不会超过 $100$。
	二叉搜索树中的所有键值均互不相同。

## 输入
```in1
8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print
```

## 输出
```out1
 1 12 17 20 25 30 88
 30 12 1 20 17 25 88
```