#include <stdio.h>
#include <stdlib.h>
//-----------------------------------------------------------------
#define MAXBUF 256
#define UP_DISP 3 /* 上位番号表示数 */
#define DW_DISP 3 /* 下位番号表示数 */
//-----------------------------------------------------------------
typedef struct Node Node;
struct Node {
    int data,leftp,rightp;
    Node *left, *right;
};
Node *g_lower_node = NULL;
int Sort_Data[3000];
int data_count=0;
int g_lower_level=0;
//-----------------------------------------------------------------
void swapvalue(int* v1,int* v2);
void simple_sort(int* a,int n);
Node **find(Node **p, int x);
void insert(Node **p, int x);
void print_tree(Node *p, int level);
void delete_tree(Node *p);
//-----------------------------------------------------------------

int main(int argc, char *argv[])
{
    int x,i;
    FILE *fp = stdin;
    Node *tree = NULL;
    char buf[MAXBUF]; 
    
    if(!(fp = fopen("btree.dat", "r"))){
        fprintf(stderr, "file open error");
        return 0;
    }
    // データを格納
    while(fgets(buf,MAXBUF,fp)){
        sscanf(buf,"%d",&x);
        insert(&tree, x);
    }
    // 表示
    printf("\n\n");
    print_tree(tree, 0);
    simple_sort(Sort_Data,data_count);
    // 下位何人
    printf("\ndown:\n");
    for(i=0;i<DW_DISP;i++){
        fprintf(stdout,"%d\n",Sort_Data[i]);
    }
    // 上位何人
    printf("\nup:\n");
    for(i=data_count-UP_DISP;i<data_count;i++){
        fprintf(stdout,"%d\n",Sort_Data[i]);
    }
    // 最下のノードの情報を表示
    if(g_lower_node){ 
        Node *p = g_lower_node;
        printf("\nlower node\n");
        printf("data = %d\n",p->data);
        printf("level = %d\n",g_lower_level);
    }
    // 後片付け
    delete_tree(tree);
    return 0;
}

void simple_sort(int* a,int n)
{
    int i,j;
    for(i=0;i<n;i++){
        for(j=i;j<n;j++){
            if(a[j] < a[i]) swapvalue(&a[j],&a[i]);
        }
    }
}

void swapvalue(int* v1,int* v2)
{
    int tmp=*v2;*v2=*v1; *v1=tmp;
}

Node **find(Node **p, int x)
{
    Node *q;

    while (q = *p, q != NULL)
        if (q->data > x){
            q->leftp++;
            p = &q->left;
        } else if (q->data < x) {
            q->rightp++;
            p = &q->right;
        } else {
            break;
        }
    return p;
}

void insert(Node **p, int x)
{
    p = find(p, x);
    if (*p == NULL) {
        Node *ken = malloc(sizeof(Node)); /*動的メモリブロックの確保*/
            if (ken == NULL)
                fprintf(stderr, "out of memory"), exit(1);
        ken->data = x;
        ken->left = ken->right = NULL; /* 初期化*/ 
        ken->leftp = ken->rightp = 0; /* 初期化*/
        *p = ken;
    }
}

void print_tree(Node *p, int level)
{
    if (p == NULL) return;

    if ( g_lower_level < level ) { /*さらに深ければ代入する*/
        g_lower_level = level;
        g_lower_node = p;
    }

    print_tree(p->left, level + 1);
    printf("%*s%d: %d <%d, %d>\n", level, "", level, 
           p->data, p->leftp, p->rightp);
    print_tree(p->right, level + 1);
    Sort_Data[data_count++] = p->data;
}

void delete_tree(Node *p)
{
    if (p == NULL) return;

    delete_tree(p->left);
    delete_tree(p->right);
    free(p);
}