链表允许我们添加、删除、搜索数据，这种数据结构会在执行时申请必要的内存空间，便于管理动态集合。但是链表的时间复杂度为O(n）。相比之下，使用动态树结构能更加有效地添加、删除和搜索数据。

搜索树是一种可以进行动态插入、搜索、删除等操作的数据结构，可以用作字典或优先级队列。二叉搜索树属于最基本的搜索树。

二叉搜索树的各结点都拥有键值，且满足二叉搜索树的性质：

　　设x为二叉搜索树的结点。如果y为x左子树中的结点，那么y的键值≤x的键值。另外，如果z为x右子树中的结点，那么x的键值≤z的键值。

以上图键值为80的结点为例，它的左子树中所有结点的键值都不超过80，右子树中所有结点的键值都不小于80。如果对二叉搜索树执行中序遍历，我们会得到一个按升序排列的键值序列。

实现二叉搜索树时，要保证数据经过插入或者删除操作后，所有结点仍然保持上述性质。与表一样，我们通过指针将结点连接成一棵树，各结点内包含值（键值）以及指向父结点、左子结点、右子结点的指针。

 

 

Binary Search Tree I

Search trees are data structures that support dynamic set operations including insert, search, delete and so on. Thus a search tree can be used both as a dictionary and as a priority queue.

Binary search tree is one of fundamental search trees. The keys in a binary search tree are always stored in such a way as to satisfy the following binary search tree property:

• Let xx be a node in a binary search tree. If yy is a node in the left subtree of xx, then y.key≤x.keyy.key≤x.key. If yy is a node in the right subtree of xx, then x.key≤y.keyx.key≤y.key.

The following figure shows an example of the binary search tree.

 

For example, keys of nodes which belong to the left sub-tree of the node containing 80 are less than or equal to 80, and keys of nodes which belong to the right sub-tree are more than or equal to 80. The binary search tree property allows us to print out all the keys in the tree in sorted order by an inorder tree walk.

A binary search tree should be implemented in such a way that the binary search tree property continues to hold after modifications by insertions and deletions. A binary search tree can be represented by a linked data structure in which each node is an object. In addition to a key field and satellite data, each node contains fields left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively.

To insert a new value vv into a binary search tree TT, we can use the procedure insert as shown in the following pseudo code. The insert procedure is passed a node zzfor which z.key=vz.key=v, z.left=NILz.left=NIL, and z.right=NILz.right=NIL. The procedure modifies TT and some of the fields of zz in such a way that zz is inserted into an appropriate position in the tree.

1 insert(T, z)2     y = NIL // parent of x3     x = 'the root of T'4     while x ≠ NIL5         y = x // set the parent6         if z.key < x.key7             x = x.left // move to the left child8         else 9             x = x.right // move to the right child10    z.p = y1112    if y == NIL // T is empty13        'the root of T' = z14    else if z.key < y.key15        y.left = z // z is the left child of y16    else 17        y.right = z // z is the right child of y

Write a program which performs the following operations to a binary search tree TT.

• insert kk: Insert a node containing kk as key into TT.
• print: Print the keys of the binary search tree by inorder tree walk and preorder tree walk respectively.

You should use the above pseudo code to implement the insert operation. TT is empty at the initial state.

Input

In the first line, the number of operations mm is given. In the following mm lines, operations represented by insert kk or print are given.

Output

For each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key.

Constraints

• The number of operations ≤500,001≤500,001
• The number of print operations ≤10≤10.
• −2,000,000,000≤key≤2,000,000,000−2,000,000,000≤key≤2,000,000,000
• The height of the binary tree does not exceed 100 if you employ the above pseudo code.
• The keys in the binary search tree are all different.

Sample Input 1

8insert 30insert 88insert 12insert 1insert 20insert 17insert 25print

Sample Output 1

1 12 17 20 25 30 88 30 12 1 20 17 25 88

#include
     
      #include
      
       #include
       
        using namespace std;struct Node{    int key;    Node *right, *left, *parent;};Node *root;void insert(int k){    Node *y = NULL;    Node *x = root;//    Node *z;    z = (Node *)malloc(sizeof(Node));    z->key = k;    z->left = NULL;    z->right = NULL;    while (x)    {        y = x;//设置父结点        if (z->key
        
          key)            x = x->left;//移动至左结点        else            x = x->right;//移动至右结点    }    z->parent = y;    if (y == NULL)//树为空树时        root = z;    else        if (z->key
         
          key)            y->left = z;//将z定为y的左子结点        else            y->right = z;//将z定为y的右子结点}void inorder(Node *u)//中序遍历{    if (u == NULL)        return;    inorder(u->left);    cout << " " << u->key;    inorder(u->right);}void preorder(Node *u)//前序遍历{    if (u == NULL)        return;    cout << " " << u->key;    preorder(u->left);    preorder(u->right);}int main(){    int n;    cin >> n;    string com;    for (int i = 0; i
          
           > com; if (com == "insert") { int x; cin >> x; insert(x); } else if (com == "print") { inorder(root); cout << endl; preorder(root); cout << endl; } } return 0;}