2371.cpp

来自「这些是我到目前在PKU上做出的题目」· C++ 代码 · 共 74 行

#define MAX_SIZE 100000


#include <stdio.h>
#include<iostream>

using namespace std;
int Root=0;     
int now_size=0; 
int key[MAX_SIZE];
int right_child[MAX_SIZE];
int left_child[MAX_SIZE];
int sort_result[MAX_SIZE];
int index=1;

void inorder_walk(int x)
{
    if(x==0)
        return;
    inorder_walk(left_child[x]);
    //cout<<key[x]<<" ";
    sort_result[index++]=key[x];
	inorder_walk(right_child[x]);
    
}

void tree_insert(int k)
{
    int index=++now_size;
    left_child[index]=0;
    right_child[index]=0;
    key[index]=k;
    int y=0;
    int x=Root;
    while(x!=0)
    {
        y=x;
        if(k>key[x])
            x=right_child[x];
        else
            x=left_child[x];
    }
    if(y==0)
        Root=index;
    else
    {
        if(k<=key[y])
            left_child[y]=index;
        else
            right_child[y]=index;
    }
}

int main()
{
    int i,num,k,n,j;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>num;
        tree_insert(num);
    }	
    inorder_walk(1);
	
    char s[5];
    cin>>s;
    cin>>k;
    for(i=1;i<=k;i++)
    {
        cin>>j;
	cout<<sort_result[j]<<endl;
    }
	return 0;
}