#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

typedef struct node{
	char tel[8];
	int tel_num;
	int balance;		//平衡因子
	struct node *left;
	struct node *right;
}STDTEL, *PSTDTEL;

void  inorder(PSTDTEL  root){
	if(root!=NULL){
		inorder(root->left);
		if(root->tel_num > 1){
			for(int i=0;i<3;i++)
				printf("%c",root->tel[i]);
			printf("-%s %d\n",&root->tel[3],root->tel_num);		
		}
		inorder(root->right);
	}
}

void LeftRotate(PSTDTEL * Ptr){
	PSTDTEL tmp=(*Ptr)->right;
	(*Ptr)->right=tmp->left;
	tmp->left=*Ptr;
	*Ptr=tmp;
}

void RightRotate(PSTDTEL * Ptr)
{   PSTDTEL tmp=(*Ptr)->left;
     (*Ptr)->left=tmp->right;
	 tmp->right=*Ptr;
	 *Ptr=tmp;
}

void LeftRightRotate(PSTDTEL *  Ptr)
{
	LeftRotate(&(*Ptr)->left);
	RightRotate(Ptr);
}

void RightLeftRotate(PSTDTEL * Ptr)
{
	RightRotate(&(*Ptr)->right);
	LeftRotate(Ptr);
}

int Insert(PSTDTEL *root,char* temptel)
{
	//返回值表明树是否长高
	int taller;
	if(*root==NULL){
		*root=(PSTDTEL)malloc(sizeof(STDTEL));
		strcpy((*root)->tel,temptel);
		(*root)->left = NULL;
		(*root)->right = NULL;
		(*root)->tel_num=1;
		(*root)->balance=0;
		return 1;
	}else if(strcmp(temptel,(*root)->tel) == 0){
		(*root)->tel_num ++;
	}else if(strcmp(temptel,(*root)->tel)>0){
		taller=Insert(&(*root) ->right,temptel);
		if(taller==1)//右子树长高了
			switch((*root)->balance)
			{
				case  0:
					(*root)->balance=1;
					break;
				case  -1:
					(*root)->balance=0;
					taller=0;
					break;
				case  1: //应该左旋或者先右后左双旋
                    if((*root)->right->balance==1){//应该左旋，并调整平衡因子
						LeftRotate(root);
						(*root)->balance=0;
						(*root)->left->balance=0;
					} else if((*root)->right->balance==-1) {  //应该双旋，并调整平衡因子
						if((*root)->right->left->balance==1){
							(*root)->balance=-1;
							(*root)->right->balance=0;
						} else {
							(*root)->balance=0;
							(*root)->right->balance=1;
						} 
						(*root)->right->left->balance=0;
						RightLeftRotate(root);
					}
					taller=0;
					break;//平衡了,没长高  
		}//switch
		return taller;
	} else  if(strcmp(temptel,(*root)->tel)<0){
		taller=Insert(&(*root)->left,temptel);
        if(taller==1)//左子树长高了
			switch((*root)->balance){
				case  0:
					(*root)->balance=-1;
					break;
				case  1:
					(*root)->balance=0;
					taller=0;
					break;
				case  -1: //应该右旋或者先左后右双旋
					if((*root)->left->balance==-1) {
						RightRotate(root);
						(*root)->balance=0;
						(*root)->right->balance=0;
					} else if((*root)->left->balance==1){
						if((*root)->left->right->balance==1) {
							(*root)->balance=0;
							(*root)->left->balance=-1;
						}else {
							(*root)->balance=1;
							(*root)->left->balance=0;
						}
						(*root)->left->right->balance=0;
						LeftRightRotate(root);
					}
					taller=0;
					break;//平衡了，没长高
		}//switch
		return taller;
	}
	return 0;
}

int main()
{
	int case_num,headchange = 0;
	int i,j,k;
	char tels[20], temptel[8];
	PSTDTEL telroot = NULL;

	scanf("%d",&case_num);

	for(i=0;i<case_num;i++){
		scanf("%s",tels);

		k = 0;
		for(j=0;j<strlen(tels);j++){
			if(tels[j] == '-')
				continue;

			if(tels[j] >= 'A' && tels[j] <= 'P'){
				temptel[k++] = (tels[j]-'A')/3+'2';
				continue;
			}
			if(tels[j] >= 'R' && tels[j] <= 'Y'){
				temptel[k++] = (tels[j]-'A'-1)/3+'2';
				continue;
				
			}else
				temptel[k++] = tels[j];
		}
		temptel[7] = 0;
		Insert(&telroot,temptel);
	

	}
	inorder(telroot);
	return 0;
}

• Re:请问高手这个为什么会runtime error (46) test1809 2005-03-23 22:04:35