#include <stdio.h>
#include <stdlib.h>
??
struct node{
????struct node *right;
????struct node *left;
????struct node *parent;
????int key;
};
??
typedef struct node * Node;
??
#define NIL NULL
??
void insert(int);
void inorder(Node);
void preorder(Node);
??
Node root;
??
int main(){
??
????int n, i, x;
??
????scanf("%d", &n);
??
????for ( i = 0; i < n; i++ ){
??????printf("insert ");
????????????scanf("%d", &x);
????????????insert(x);

????????????inorder(root);
????????????printf("\n");
????????????preorder(root);
????????????printf("\n");
????????
????}
??
????return 0;
}
??
void insert(int k){
??
????Node y = NIL;
????Node x = root;
????Node z;
??
????z = malloc(sizeof(struct node));
????z->key = k;
????z->left = NIL;
????z->right = NIL;
??
????
????while(x != NIL){
??
????????y = x;
??
????????if(z->key < x->key){
????????????x = x->left;
????????}
??
????????else{
????????????x = x->right;
????????}
????}
??
????z->parent = y;
??
????if(y == NIL){
????????root = z;
????}
??
????else if(z->key < y->key){
????????y->left = z;
????}
??
????else y->right = z;
??
}
??
void inorder(Node u){
??
????if(u != NIL){
????????inorder(u->left);
????????printf(" %d", u->key);
????????inorder(u->right);
????}
??
}
??
void preorder(Node u){
??
????if(u != NIL){
????????printf(" %d",u->key);
????????preorder(u->left);
????????preorder(u->right);
????}
??
}