1898.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1898 on 2006-06-15 at 10:26:53 */ 
#include <cstdio>
#include <cstring>

class BST {
public:
	char key[11], value[11];
	BST *left, *right;
	BST(char*, char*);
	BST* search(char*);
	void insert(BST*);   
};
BST::BST(char *inv, char *ink) {
	strcpy(key, ink);
	strcpy(value, inv);
	left = right = NULL;
}
BST* BST::search(char* key) {
	BST *p = this;
	while(true) {
		int i = strcmp(key, p->key);
		if(i < 0) {
			if(p->left != NULL) p = p->left;
			else return NULL;
		} else if(i > 0) {
			if(p->right != NULL) p = p->right;
			else return NULL;
		} else return p;
	}
}
void BST::insert(BST* node) {
	BST *p = this;
	while(true) {
		int i = strcmp(node->key, p->key);
		if(i < 0) {
			if(p->left != NULL) p = p->left;
			else { p->left = node; break; }    
		} else if(i > 0) {
			if(p->right != NULL) p = p->right;
			else { p->right = node; break; }
		} else break;
	}
} 

int main()
{
	BST *node, *root, *p;
	char key[11], value[11], line[32];
	int i;

	for(i = 0; gets(line)[0] != 0; i++) {
		sscanf(line, "%s %s", value, key);
		if(i == 0) root = new BST(value, key);
      else { 
			node = new BST(value, key);
			root->insert(node);
		}
	}
	while(gets(value) != NULL) {
		p = root->search(value);
		printf("%s\n", p == NULL ? "eh" : p->value);
	}
}