두 갈래 찾기 나무, 균형 두 갈래 나무

         —— 

Time Limit: 1000MS Memory Limit: 65536KB Problem Description 트리 구조에서 특수한 두 갈래 트리를 정렬 두 갈래 트리라고 하는데 직관적인 이해는 바로 (1)이다.각 노드에는 관건적인 값이 포함되어 있습니다 (2).임의의 노드의 왼쪽 트리 (존재한다면) 의 키 값은 이 노드의 키 값보다 작습니다 (3).임의의 노드의 오른쪽 트리 (존재한다면) 의 관건값은 이 노드의 관건값보다 크다.현재 한 조의 데이터를 지정합니다. 이 조의 데이터에 대해 주어진 순서에 따라 정렬 두 갈래 트리를 만들고 그 중의 정렬 결과를 출력하십시오.
Input 입력에는 다음과 같은 형식의 여러 데이터 세트가 포함되어 있습니다.첫 번째 줄은 정수 n을 포함하고 관건적인 값의 개수를 포함하며 관건적인 값은 정수로 표시한다.(n<=1000) 두 번째 줄은 n개의 정수를 포함하고 모든 정수가 int 범위 내에 있음을 보증합니다.Output은 주어진 데이터를 정렬하는 두 갈래 트리를 만들고 그 결과를 출력합니다. 출력마다 한 줄을 차지합니다.
Example Input
1 2 2 1 20
Example Output
2 1 20
Hint
Author Jolien 코드 구현:

#include 
#include 
#include 
struct node
{
  int data;
  struct node * left, *right;
};
int ans[3000], top;
struct node * creat(struct node * root, int k)
{
   if(root==NULL)
   {
      root = (struct node *)malloc(sizeof(struct node));
      root->data = k;
      root->left = NULL;
      root->right = NULL;
      return root;
   }
   if(root->data>k)
   {//kdata, 
   root->left = creat(root->left, k);
   }
   else
   root->right = creat(root->right, k);// ， 
   return root;
}
void mid(struct node* root)// 
{
   if(root)
   {
     mid(root->left);
     ans[top++] = root->data;// 
     mid(root->right);
   }
}
int main()
{
   int n,m, i;
   while(~scanf("%d", &n))
   {
     struct node * root;
     root = (struct node *)malloc(sizeof(struct node));
     root = NULL;
     for(i=0;iscanf("%d", &m);
       root = creat(root, m);
     }
     top = 0;// （ ， top 0 ）
     mid(root);
     for(i=0;i1;i++)
     printf("%d ", ans[i]);
     printf("%d
", ans[i]);
   }
    return 0;
}

예제 2: 잃어버린 검색 트리 시간 제한: 1000MS Memory Limit: 65536KB Problem 설명
샤오루는 우연한 일치로 두 갈래 검색 트리를 얻었다. 이 두 갈래 검색 트리는 마침 n개의 노드가 있고 각 노드는 하나의 권한이 있다. 각 노드의 권한은 [1,n] 이 구간 안에 있고 두 개의 노드가 다르다. 정말 아름다운 성질이다.
하지만 운명의 불공평함은 그녀를 이 두 갈래 수색 나무를 잃게 했다
다행히도 그녀는 자신이 잃어버린 두 갈래 검색 트리의 앞순서를 기억하고 있었다.
두 갈래를 잃어버리고 나무를 수색한 후, 샤오루는 그녀의 이 나무의 뒷부분을 더없이 그리워했다.
그럼 문제가 생겼어요. 똑똑한 당신은 이 두 갈래 수색 나무의 앞뒤를 샅샅이 훑어보는 서열을 알고 있는 상황에서 이 두 갈래 수색 나무의 뒷부분을 찾아줄 수 있을까요?Input
다중 그룹 입력, 파일로 끝
각 그룹의 데이터 첫 번째 행위는 정수 n으로 이 두 갈래 검색 트리의 노드 개수를 대표한다(1<=n<=100)
다음 줄 n개의 정수, 이 두 갈래 검색 트리의 앞 순서를 나타내는 Output
출력 n 개 정수
이 두 갈래 나무의 뒷순서를 나타내는 시퀀스 Example Input
5 4 2 1 3 5
Example Output
1 3 2 5 4
Hint
두 갈래 찾기 나무는 빈 나무이거나 다음과 같은 성질을 가진 두 갈래 나무이다.
만약 그것의 왼쪽 트리가 비어 있지 않다면, 왼쪽 트리의 모든 결점의 값은 그것의 뿌리 결점의 값보다 작다
오른쪽 트리가 비어 있지 않으면 오른쪽 트리의 모든 결점 값이 루트 결점 값보다 큽니다.
그것의 왼쪽, 오른쪽 자수도 각각 두 갈래 정렬 트리 Author 2016 여름방학 합숙 훈련 경기 by QAQ 코드 구현:

#include 
#include 
#include 
struct node
{
  int data;
  struct node * left, *right;
};
struct node * creat(struct node * root, int a)
{
   if(root==NULL)
   {
      root = (struct node *)malloc(sizeof(struct node));
      root->data = a;
      root->left = NULL;
      root->right = NULL;
      return root;
   }
   if(root->data>a)
   {
   root->left = creat(root->left, a);
   }
   else
   root->right = creat(root->right, a);
   return root;
}
int ans[150], top, a[150];
void qian(struct node * root)// 
{
   if(root)
   {
      qian(root->left);
      qian(root->right);
      ans[top++] = root->data;
   }
}
int main()
{
    int n, i;
    while(~scanf("%d", &n))
    {
    struct node * root;
    root = (struct node*)malloc(sizeof(struct node));
    for(int i=0;iscanf("%d", &a[i]);
    root = creat(root, a[i]);
    }
    top = 0;
    qian(root);
    for(i=0;i1;i++)
    printf("%d ", ans[i]);
    printf("%d
", ans[i]);
    }
    return 0;
}

오늘의 큰 요리!!!예제 3: 데이터 구조 실험의 찾기 2: 균형 트리 시간 제한: 400MS Memory Limit: 65536KB Problem 설명
주어진 입력 서열에 따라 균형 두 갈래 나무를 만들어 균형 두 갈래 나무의 뿌리를 구한다.Input
테스트 데이터 세트를 입력합니다.데이터의 첫 번째 줄은 정수 N(n<=20)을 제시하고 N은 입력 서열의 원소 개수를 나타낸다.두 번째 줄은 N개의 정수를 제시하고 데이터가 정해진 순서에 따라 균형 트리를 세운다.Output
균형 잡힌 두 갈래 나무의 뿌리를 출력합니다.Example Input
5 88 70 61 96 120
Example Output
칠십
Hint
Author xam 코드 구현: (C++)

#include<iostream>
#include<stdio.h>
using namespace std;
typedef struct node
{
    int data,deep;
    struct node *l,*r;
}st;
int height(st *root)
{
    if(root==NULL)
        return -1;
    return root->deep;
}
st *LLchange(st *root)
{
    st *p;
    p=root->l;
    root->l=p->r;
    p->r=root;
    p->deep=max(height(p->l),height(p->r))+1;
    root->deep=max(height(root->l),height(root->r))+1;
    return p;
}
st *RRchange(st *root)
{
    st *p;
    p=root->r;
    root->r=p->l;
    p->l=root;
    p->deep=max(height(p->l),height(p->r))+1;
    root->deep=max(height(root->l),height(root->r))+1;
    return p;
}
st *LRchange(st *root)
{
    root->l=RRchange(root->l);
    return LLchange(root);
}
st *RLchange(st *root)
{
    root->r=LLchange(root->r);
    return RRchange(root);
}
st *Push(st *root,int k)
{
    if(root==NULL)
    {
        root=new st;
        root->data=k;
        root->deep=0;
        root->l=root->r=NULL;
    }
    else if(k<root->data)
    {
        root->l=Push(root->l,k);
        if(height(root->l)-height(root->r)==2)
        {
            if(k<root->l->data)
                root=LLchange(root);
            else
                root=LRchange(root);
        }
    }
    else if(k>root->data)
    {
        root->r=Push(root->r,k);
        if(height(root->r)-height(root->l)==2)
        {
            if(k<root->r->data)
                root=RLchange(root);
            else
                root=RRchange(root);
        }
    }
    root->deep=max(height(root->l),height(root->r))+1;
    return root;
}
int main()
{
    int n,k;
    while(~scanf("%d", &n))
    {
        st *root=NULL;
        while(n--)
        {
            scanf("%d", &k);
            root=Push(root,k);
        }
        printf("%d
",root->data);
    }
    return 0;
}

코드 구현: (C)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
    int data;
    int deep;
    struct node *left;
    struct node *right;
};
int max(int a, int b)
{
  if(a>=b)
  return a;
  else
  return b;
}
int height(struct node *root)
{
    if(root==NULL)
        return -1;
    return root->deep;
}
struct node *LLchange(struct node *root)
{
    struct node *p;
    p=root->left;
    root->left=p->right;
    p->right=root;
    p->deep=max(height(p->left),height(p->right))+1;
    root->deep=max(height(root->left),height(root->right))+1;
    return p;
}
struct node *RRchange(struct node *root)
{
    struct node *p;
    p=root->right;
    root->right=p->left;
    p->left=root;
    p->deep=max(height(p->left),height(p->right))+1;
    root->deep=max(height(root->left),height(root->right))+1;
    return p;
}
struct node *LRchange(struct node*root)
{
    root->left=RRchange(root->left);
    return LLchange(root);
}
struct node *RLchange(struct node *root)
{
    root->right=LLchange(root->right);
    return RRchange(root);
}
struct node *Push(struct node *root,int k)
{
    if(root==NULL)
    {
        root=(struct node *)malloc(sizeof(struct node));
        root->data=k;
        root->deep=0;
        root->left=root->right=NULL;
    }
    else if(k<root->data)
    {
        root->left=Push(root->left,k);
        if(height(root->left)-height(root->right)==2)
        {
            if(k<root->left->data)
                root=LLchange(root);
            else
                root=LRchange(root);
        }
    }
    else if(k>root->data)
    {
        root->right=Push(root->right,k);
        if(height(root->right)-height(root->left)==2)
        {
            if(k<root->right->data)
                root=RLchange(root);
            else
                root=RRchange(root);
        }
    }
    root->deep=max(height(root->left),height(root->right))+1;
    return root;
}
int main()
{
    int n,k;
    while(~scanf("%d", &n))
    {
        struct node *root=NULL;
        while(n--)
        {
            scanf("%d", &k);
            root=Push(root,k);
        }
        printf("%d
",root->data);
    }
    return 0;
}