두 갈래 정렬 트 리

원본 링크:http://acm.pku.edu.cn/JudgeOnline/problem?id=2418
해법: 두 갈래 정렬 트 리 는 모든 트 리 종 류 를 저장 한 다음 출력 결 과 를 중간 순서 로 옮 겨 다 니 면 됩 니 다.
코드 (c 언어):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 10001
//     ，    

int root=0;//   ，0  NULL
int curr_size=0;//         
int num_trees=0;//    
//      ，   1  ，0  NULL
char key[MAXSIZE][31];
int value[MAXSIZE];
int left_child[MAXSIZE];
int right_child[MAXSIZE];
//       ，     ,  0，      （    1），  -1,           
int search(int node, char* k)
{
    int parent=0;
    int current=node;
    while(current!=0)
    {
        parent=current;
        int tmp = strcmp(key[current],k);
        if(tmp == 0)
        {
            value[current]++;
            return -1;
        }else if(tmp<0)
        {
            current = right_child[current];
        }else
        {
            current = left_child[current];
        }
    }
    return parent;
}
//     
int insert(int node,char* k)
{
    //         ，     
    int tmp = strcmp(key[node],k);
    if(tmp==0)
        return 0;
    int new_node = ++curr_size;//     
    strcpy(key[new_node],k);
    value[new_node]=1;
    left_child[new_node]=0;
    right_child[new_node]=0;
    if(new_node==1)//   
        root = 1;
    if(tmp>0)
        left_child[node] = new_node;
    else
        right_child[node] = new_node;
    return 1;
}
void build_tree()
{
    //freopen("in.txt","r",stdin);
    char buf[31];
    while(gets(buf))
    {
        num_trees++;
        int index = search(root,buf);
        if(index>=0)
        {
            insert(index,buf);
        }
    }
}
//    
void inorder_tree(int root)
{
    if(!root)
        return ;
    inorder_tree(left_child[root]);
    printf("%s %.4f
",key[root] ,value[root]*100.0/num_trees);
    inorder_tree(right_child[root]);
}

int main()
{
    build_tree();
    inorder_tree(root);
    return 0;
}