Poj 1002 487-3279(二叉搜索树)

题目链接：http://poj.org/problem?id=1002

思路分析：先对输入字符进行处理，转换为标准形式；插入标准形式的电话号码到查找树中，若有相同号码计数器增加1，再中序遍历查找树。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>struct TreeNode;
typedef char ElementType[];
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
struct TreeNode
{
    int Count;
    ElementType Element;
    SearchTree Left;
    SearchTree Right;
};void StrToNum( char *str , char * Tel );
SearchTree MakeEmpty( SearchTree T );
SearchTree Insert( ElementType X, SearchTree T );
void PrintTel( SearchTree T );
int flag = ;int main()
{
    int n;
    char Str[], Tel[];
    SearchTree T = NULL;    menset( Tel, , sizeof(Tel) );    scanf( "%d", &n );
    for ( int i = ; i < n; ++i )
    {
        scanf( "%s", Str );
        StrToNum( Str, Tel );
        T = Insert( Tel, T );
    }    PrintTel( T );
    if ( flag ==  )
        printf( "No duplicates.\n" );    return ;
}void PrintTel( SearchTree T )
{
    if ( T != NULL )
    {
        PrintTel( T->Left );
        if ( T->Count >  )
        {
            printf( "%s %d\n", T->Element, T->Count );
            flag = ;
        }
        PrintTel( T->Right );
    }
}SearchTree MakeEmpty( SearchTree T )
{
    if ( T != NULL )
    {
        MakeEmpty( T->Left );
        MakeEmpty( T->Right );
        free( T );
    }
    return NULL;
}SearchTree Insert( ElementType X, SearchTree T )
{
    if ( T == NULL )
    {
        T = ( Position )malloc( sizeof( struct TreeNode ) );
        if ( T == NULL )
        {
            printf( "Out of space" );
            return NULL;
        }
        else
        {
            strcpy( T->Element, X );
            T->Left = T->Right = NULL;
        }
    }
    else
    if ( strcmp(X, T->Element) <  )
        T->Left = Insert( X, T->Left );
    else
    if ( strcmp(X, T->Element) >  )
        T->Right = Insert( X, T->Right);    return T;
}void StrToNum( char *str , char * Tel )
{
    int i, j;    for ( i = j = ; str[i] != '\0'; i++ )
    {
        if ( str[i] == '-' );
        else
        if ( '' <= str[i] && str[i] <= '' )
            Tel[j++] = str[i];
        else
        if ( str[i] < 'Q' )
            Tel[j++] = ( str[i] - 'A' ) /  +  + '';
        else
            Tel[j++] = ( str[i] - 'A' -  ) /  +  + '';        if ( j ==  )
            Tel[j++] = '-';
    }
}